1.2.4: Equivalence Relations

\(\def\Assign#1#2{ { #1^{\Struct{#2}} } }\)
\(\def\Atom#1#2{ { \mathord{#1}(#2) } }\)
\(\def\Bin{ {\mathbb{B}} }\)
\(\def\cardeq#1#2{ { #1 \approx #2 } }\)
\(\def\cardle#1#2{ { #1 \preceq #2 } }\)
\(\def\cardless#1#2{ { #1 \prec #2 } }\)
\(\def\cardneq#1#2{ { #1 \not\approx #2 } }\)
\(\def\comp#1#2{ { #2 \circ #1 } }\)
\(\def\concat{ { \;\frown\; } }\)
\(\def\Cut{ { \text{Cut} } }\)
\(\def\Discharge#1#2{ { [#1]^#2 } }\)
\(\def\DischargeRule#1#2{ { \RightLabel{#1}\LeftLabel{\scriptsize{#2} } } }\)
\(\def\dom#1{ {\operatorname{dom}(#1)} }\)
\(\def\Domain#1{ {\left| \Struct{#1} \right|} }\)
\(\def\Elim#1{ { {#1}\mathrm{Elim} } }\)
\(\newcommand{\Entails}{\vDash}\)
\(\newcommand{\EntailsN}{\nvDash}\)
\(\def\eq[#1][#2]{ { #1 = #2 } }\)
\(\def\eqN[#1][#2]{ { #1 \neq #2 } }\)
\(\def\equivclass#1#2{ { #1/_{#2} } }\)
\(\def\equivrep#1#2{ { [#1]_{#2} } }\)
\(\def\Exchange{ { \text{X} } }\)
\(\def\False{ { \mathbb{F} } }\)
\(\def\FalseCl{ { \lfalse_C } }\)
\(\def\FalseInt{ { \lfalse_I } }\)
\(\def\fCenter{ { \,\Sequent\, } }\)
\(\def\fdefined{ { \;\downarrow } }\)
\(\def\fn#1{ { \operatorname{#1} } }\)
\(\def\Frm[#1]{ {\operatorname{Frm}(\Lang #1)} }\)
\(\def\fundefined{ { \;\uparrow } }\)
\(\def\funimage#1#2{ { #1[#2] } }\)
\(\def\funrestrictionto#1#2{ { #1 \restriction_{#2} } }\)
\(\newcommand{\ident}{\equiv}\)
\(\newcommand{\indcase}[2]{#1 \ident #2\text{:}}\)
\(\newcommand{\indcaseA}[2]{#1 \text{ is atomic:}}\)
\(\def\indfrm{ { A } }\)
\(\def\indfrmp{ { A } }\)
\(\def\joinrel{\mathrel{\mkern-3mu}}\)
\(\def\lambd[#1][#2]{\lambda #1 . #2}\)
\(\def\Lang#1{ { \mathcal{#1} } }\)
\(\def\LeftR#1{ { {#1}\mathrm{L} } }\)
\(\def\len#1{ {\operatorname{len}(#1)} }\)
\(\def\lexists#1#2{ { \exists #1\, #2 } }\)
\(\def\lfalse{ {\bot} }\)
\(\def\lforall#1#2{ { \forall#1\, #2 } }\)
\(\newcommand{\lif}{\rightarrow}\)
\(\newcommand{\liff}{\leftrightarrow}\)
\(\def\Log#1{ { \mathbf{#1} } }\)
\(\def\ltrue{ {\top} }\)
\(\def\Id#1{ {\operatorname{Id}_#1} }\)
\(\def\Int{ {\mathbb{Z}} }\)
\(\def\Intro#1{ { {#1}\mathrm{Intro} } }\)
\(\def\mModel#1{ { \mathfrak{#1} } }\)
\(\newcommand{\mSat}[3][{}]{\mModel{#2}{#1}\Vdash{#3}}\)
\(\newcommand{\mSatN}[3][{}]{\mModel{#2}{#1}\nVdash{#3}}\)
\(\def\Nat{ {\mathbb{N}} }\)
\(\def\nicefrac#1#2{ {{}^#1/_#2} }\)
\(\def\num#1{ { \overline{#1} } }\)

\(\def\ran#1{ {\operatorname{ran}(#1)} }\)
\(\newcommand{\Obj}[1]{\mathsf{#1}}\)
\(\def\Rat{ {\mathbb{Q}} }\)
\(\def\Real{ {\mathbb{R}} }\)
\(\def\RightR#1{ { {#1}\mathrm{R} } }\)
\(\def\Part#1#2{ { \Atom{\Obj P}{#1, #2} } }\)
\(\def\pto{ { \hspace{0.1 cm}\to\hspace{-0.44 cm}\vcenter{\tiny{\hbox{|}}}\hspace{0.35 cm} } }\)
\(\def\PosInt{ {\mathbb{Z}^+} }\)
\(\def\Pow#1{ {\wp(#1)} }\)
\(\newcommand{\Proves}{\vdash}\)
\(\newcommand{\ProvesN}{\nvdash}\)
\(\def\Relbar{\mathrel{=}}\)
\(\newcommand{\Sat}[3][{}]{\Struct{#2}{#1}\vDash{#3}}\)
\(\newcommand{\SatN}[3][{}]{\Struct{#2}{#1}\nvDash{#3}}\)
\(\newcommand{\Sequent}{\Rightarrow}\)
\(\def\Setabs#1#2{ { \{#1:#2\} } }\)
\(\newcommand{\sFmla}[2]{#1\,#2}\)
\(\def\Struct#1{ {#1} }\)
\(\def\subst#1#2{ { #1/#2 } }\)
\(\def\Subst#1#2#3{ { #1[\subst{#2}{#3}] } }\)
\(\def\TMblank{ { 0 } }\)
\(\newcommand{\TMendtape}{\triangleright}\)
\(\def\TMleft{ { L } }\)
\(\def\TMright{ { R } }\)
\(\def\TMstay{ { N } }\)
\(\def\TMstroke{ { 1 } }\)
\(\def\TMtrans#1#2#3{ { #1,#2,#3 } }\)
\(\def\Trm[#1]{ {\operatorname{Trm}(\Lang #1)} }\)
\(\def\True{ { \mathbb{T} } }\)
\(\newcommand{\TRule}[2]{#2#1}\)
\(\def\tuple#1{ {\langle #1 \rangle} }\)
\(\newcommand{\Value}[3][\,]{\mathrm{Val}_{#1}^{#3}(#2)}\)
\(\def\Var{ { \mathrm{Var} } }\)
\(\newcommand{\varAssign}[3]{#1 \sim_{#3} #2}\)
\(\def\Weakening{ { \text{W} } }\)

The identity relation on a set is reflexive, symmetric, and transitive. Relations \(R\) that have all three of these properties are very common.

Definition \(\PageIndex{1}\): Equivalence relation

A relation \(R \subseteq A^2\) that is reflexive, symmetric, and transitive is called an equivalence relation. Elements \(x\) and \(y\) of \(A\) are said to be \(R\)-equivalent if \(Rxy\).

Equivalence relations give rise to the notion of an equivalence class. An equivalence relation “chunks up” the domain into different partitions. Within each partition, all the objects are related to one another; and no objects from different partitions relate to one another. Sometimes, it’s helpful just to talk about these partitions directly. To that end, we introduce a definition:

Definition \(\PageIndex{2}\)

Let \(R \subseteq A^2\) be an equivalence relation. For each \(x \in A\), the equivalence class of \(x\) in \(A\) is the set \(\equivrep{x}{R} = \Setabs{y \in A}{Rxy}\). The quotient of \(A\) under \(R\) is \(\equivclass{A}{R} = \Setabs{\equivrep{x}{R}}{x \in A}\), i.e., the set of these equivalence classes.

The next result vindicates the definition of an equivalence class, in proving that the equivalence classes are indeed the partitions of \(A\):

Proposition \(\PageIndex{1}\)

If \(R \subseteq A^2\) is an equivalence relation, then \(Rxy\) iff \(\equivrep{x}{R} = \equivrep{y}{R}\).

Proof. For the left-to-right direction, suppose \(Rxy\), and let \(z \in \equivrep{x}{R}\). By definition, then, \(Rxz\). Since \(R\) is an equivalence relation, \(Ryz\). (Spelling this out: as \(Rxy\) and \(R\) is symmetric we have \(Ryx\), and as \(Rxz\) and \(R\) is transitive we have \(Ryz\).) So \(z \in \equivrep{y}{R}\). Generalising, \(\equivrep{x}{R} \subseteq \equivrep{y}{R}\). But exactly similarly, \(\equivrep{y}{R} \subseteq \equivrep{x}{R}\). So \(\equivrep{x}{R} = \equivrep{y}{R}\), by extensionality.

For the right-to-left direction, suppose \(\equivrep{x}{R} = \equivrep{y}{R}\). Since \(R\) is reflexive, \(Ryy\), so \(y \in \equivrep{y}{R}\). Thus also \(y \in \equivrep{x}{R}\) by the assumption that \(\equivrep{x}{R} = \equivrep{y}{R}\). So \(Rxy\). ◻

Example \(\PageIndex{1}\)

A nice example of equivalence relations comes from modular arithmetic. For any \(a\), \(b\), and \(n \in \Nat\), say that \(a \equiv_n b\) iff dividing \(a\) by \(n\) gives remainder \(b\). (Somewhat more symbolically: \(a \equiv_n b\) iff \((\exists k \in \Nat)a - b = kn\).) Now, \(\equiv_n\) is an equivalence relation, for any \(n\). And there are exactly \(n\) distinct equivalence classes generated by \(\equiv_n\); that is, \(\equivclass{\Nat}{\equiv_n}\) has \(n\) elements. These are: the set of numbers divisible by \(n\) without remainder, i.e., \(\equivrep{0}{\equiv_n}\); the set of numbers divisible by \(n\) with remainder \(1\), i.e., \(\equivrep{1}{\equiv_n}\); …; and the set of numbers divisible by \(n\) with remainder \(n-1\), i.e., \(\equivrep{n-1}{\equiv_n}\).

Problem \(\PageIndex{1}\)

Show that \(\equiv_n\) is an equivalence relation, for any \(n \in \Nat\), and that \(\equivclass{\Nat}{\equiv_n}\) has exactly \(n\) members.