10.1 Equivalence relations and partition of sets
There are many situations in maths where we have different objects that we want to “consider the same”, often because they share a desired property. The requirement that two objects are exactly equal is often too restrictive, so we generalise this concept to be broader (this theory is applied to many branches of mathematics).
A relation \(\sim\) on a nonempty set \(X\) is a subset \(R\subseteq X\times X\). We say \(x\) is related to \(y\), denoted by \(x\sim y\), when \((x,y)\in R\).
A relation \(\sim\) is reflexive if for all \(x\in X\), \(x\sim x\).
A relation \(\sim\) is symmetric if for all \(x,y\in X\) we have \(x\sim y\) implies \(y\sim x\).
A relation \(\sim\) is transitive if for all \(x,y,z\in X\), if \(x\sim y\) and \(y\sim z\) then \(x\sim z\).
We use the notation \(x\not\sim y\) to say \(x\) is not related to \(y\).
We negate the above three properties to say that:
A relation \(\sim\) is not reflexive if there exists \(x\in X\) such that \(x\not\sim x\).
A relation \(\sim\) is not symmetric if there exists \(x,y\in X\) such that \(x\sim y\) and \(y\not\sim x\).
A relation \(\sim\) is not transitive if there exists \(x,y,z\in X\), such that \(x\sim y\) and \(y\sim z\) and \(x\not\sim z\).
A relation \(\sim\) on a nonempty set \(X\) is an equivalence relation if it is reflexive, symmetric and transitive.
In such case we read \(x\sim y\) as “\(x\) is equivalent to \(y\)”.
Reflexive comes from the Latin re meaning “back” and flectere meaning “to bend”. This gave rise to words like “reflect” (where an object is bent back through a mirror) and “reflection”. A relationship is reflexive if it reflects every element (i.e., every element is in relation with itself).
Symmetric comes from the Greek sun meaning “together with” and metron meaning “a measure”. Given a point “together with a distance (from a line of symmetry)”, then you have found the image of the point using that symmetry.
We’ve seen the word transitive before ( (O2) ) - transitive comes from the Latin trans meaning “across, beyond” and the verb itus/ire meaning “to go”. A transitive relationship is one where knowing \(x\sim y\) and \(y\sim z\) allows us to go from \(x\) beyond \(y\) all the way to \(z\).
Equivalence comes from the Latin oequus meaning “even, level” and valere meaning “to be strong, to have value”. Two elements are equivalent if they are level (i.e., equal) in their value. One can be substituted for the other (notice this has the same roots as the word equal).Since we claim that equivalence relations are a generalisation of \(=\), let us show that \(=\) is indeed an equivalence relation. Define a relation \(\sim\) on \(\mathbb{R}\) via \(x\sim y\) if and only if \(x=y\). We show \(\sim\) is an equivalence relation.
Let \(x\in \mathbb{R}\). Since \(x=x\), we have \(x\sim x\). This is true for all \(x\in\mathbb{R}\), hence \(\sim\) is reflexive.
Let \(x,y\in \mathbb{R}\) be such that \(x\sim y\). By definition, this means \(x=y\), which means \(y=x\), i.e. \(y\sim x\). This is true for all \(x,y \in\mathbb{R}\), hence \(\sim\) is symmetric.
Let \(x,y,z\in \mathbb{R}\) be such that \(x\sim y\) and \(y\sim z\). This means \(x=y\) and \(y=z\), so \(x=y=z\), i.e. \(x=z\). So \(x\sim z\). This is true for all \(x,y,z \in\mathbb{R}\), hence \(\sim\) is transitive.
Since \(\sim\) is reflexive, symmetric and transitive, we have that \(\sim\) is an equivalence relation.Notice how in the above example each distinct equivalence class did not intersect each other. This is true in general.
Suppose \(\sim\) is an equivalence relation on a (nonempty) set \(X\). Then for any \(x,y\in X\), \([x]\neq[y]\) if and only if \([x]\cap[y]=\emptyset.\)
Take \(x,y\in X\).
\(\Rightarrow\)). First, we will show that if \([x]\neq[y]\) then \([x]\cap[y]=\emptyset\) by using the contrapositive. That is will prove that if \([x]\cap [y]\not=\emptyset\), then \([x]=[y]\).
So suppose that \([x]\cap[y]\not=\emptyset\). Then there exists some \(z\in[x]\cap[y]\). Hence, \(z\in[x]\), so \(z\sim x\). Similarly, \(z\in[y]\), so \(z\sim y\). Since \(\sim\) is symmetric, we have that \(x\sim z\). Since \(\sim\) is transitive, we have that \(x\sim y\). Now, choose \(w\in[x]\). Then \(w\sim x\), and since \(x\sim y\) and \(\sim\) is transitive, we have that \(w\sim y\). Hence, \(w\in[y]\). Since \(w\in[x]\) is arbitrary, we have that \([x]\subseteq [y]\). Similarly, we can show that, for any \(w\in[y]\), we have \(w\in[x]\), so \([y]\subseteq[x]\). Hence \([x]=[y].\)
\(\Leftarrow\)). Second, we will show that if \([x]\cap[y]=\emptyset\) then \([x]\not=[y]\) by using the contrapositive. So we will show that if \([x]=[y]\), then \([x]\cap[y]\not=\emptyset\).
So suppose that \([x]=[y]\). Since \(\sim\) is reflexive, we know that \(x\in[x]\). Hence, \(x\in[x]=[x]\cap[y]\), so \([x]\cap[y]\not=\emptyset.\)
Summarising, we have that \([x]\not=[y]\) if and only if \([x]\cap[y]=\emptyset.\)□
The above set-up leads us to the following definition which breaks a set into “parts”.
A partition of a non-empty set \(X\) is a collection \(\{A_i: i\in I \}\) of non-empty subsets of \(X\) such that
\(\forall\,x\in X\), \(\exists\,i\in I\) such that \(x\in A_i\), and
\(\forall\,x\in X\) and \(\forall\,i,j\in I\), if \(x\in A_i\cap A_j\), then \(A_i=A_j\ \).
The above two conditions can be rephrased as follows:
\(X = \bigcup_{i\in I} A_i\), and
\(A_i \cap A_j \neq \emptyset\) if and only if \(A_i = A_j\).
The above remark and Proposition 10.4 suggests a strong link between equivalence relations and partitions of sets, as we explore in the next two theorems.
Suppose \(\sim\) is an equivalence relation on a (non-empty) set \(X\). Then \[\Pi=\left\{[x]:\ x\in X\right\}\] is a partition of \(X\).
Take \(a\in X\). Then \(a \in [a]\in\Pi\). Hence, every element of \(X\) is in one of the equivalence classes in \(\Pi\). Furthermore, by Proposition 10.4 we have that \([x]\neq[y]\) if and only if \([x]\cap[y]=\emptyset.\), i.e. (by the contrapositive) \([x]\cap[y]\neq\emptyset\) if and only if \([x]=[y]\) as required.
□
Furthermore, given a partition of a set, we can construct an equivalence relation.
Suppose \(\Pi=\{A_i:\ i\in I\ \}\) is a partition of a (nonempty) set \(X\), for some indexing set \(I\). For \(x,y\in X\), define \(x\sim y\) if and only if there exists an \(i\in I\) such that \(x,y\in A_i\). Then \(\sim\) is an equivalence relation on \(X\).
We show \(\sim\) is reflexive. Take \(x\in X\). Since \(\Pi\) is a partition of \(X\), there exists some \(i\in I\) such that \(x\in A_i\). Hence, \(x\sim x\).
We show \(\sim\) is symmetric. Suppose \(x,y\in X\) such that \(x\sim y\). Then there exists some \(i\in I\) such that \(x,y\in A_i\). It follows that \(y,x\in A_i\), so \(y\sim x\).
We show \(\sim\) is transitive. Suppose that \(x,y,z\in X\) are such that \(x\sim y\) and \(y\sim z\). Then there exists some \(i\in I\) such that \(x,y\in A_i\) and there exists some \(j\in I\) such that \(y,z\in A_j\). Hence, we have that \(y\in A_i\) and \(y\in A_j\). Since \(\Pi\) is a partition, we must have that \(A_i = A_j\). It follows that \(x,z\in A_i\), so \(x\sim z\).
Summarising, we have that \(\sim\) is an equivalence relation on \(X\).□
Let us take the previous example further. Define a relation \(\sim\) on \(\mathbb{Z}\) via \(x\sim y\) if and only if either \(x=y\) or \(xy>0\). This is an equivalence relation. We have that \(\sim\) partitions \(\mathbb{Z}\) into three sets, \([-1]=\mathbb{Z_{-}}\), \([0]=\{0\}\) and \([1]=\mathbb{Z}_{+}\).
We will construct \(\mathbb{Q}\) from \(\mathbb{Z}\) by partitioning the set \(\mathbb{Z} \times \mathbb{Z}_+\).
We define the relation \(\sim\) on \(\mathbb{Z} \times \mathbb{Z}_+\) via \((a,b) \sim (c,d)\) if and only if \(a\cdot d=b\cdot c\). We check this is an equivalence relation.:
Let \((a,b) \in \mathbb{Z} \times \mathbb{Z}_+\). Since \(a\cdot b=b\cdot a\), we have that \((a,b) \sim (a,b)\) and \(\sim\) is reflexive.
Let \((a,b),(c,d) \in \mathbb{Z} \times \mathbb{Z}_+\) be such that \((a,b) \sim (c,d)\). Then we have \(a\cdot d=b\cdot c\), which can be re-written as \(c\cdot b=d\cdot c\), so \((c,d) \sim (a,b)\) and \(\sim\) is symmetric.
Let \((a,b), (c,d), (f,g) \in \mathbb{Z} \times \mathbb{Z}_+\) be such that \((a,b) \sim (c,d)\) and \((c,d) \sim (f,g)\). Then we have \(a\cdot d=b\cdot c\) and \(c\cdot g=d\cdot f\). Multiplying the first equation by \(g\) we get \(adg=cbg\), and using the second equation we can write it as \(adg=bdf\). Since we have \(d \neq 0\) (as \(d\in \mathbb{Z}_+\)) we can divide through to give \(ag=bf\) which means that \((a,b)\sim (f,g)\) and \(\sim\) is transitive.
Therefore \(\sim\) is reflexive, symmetric and transitive, and so it is an equivalence relation.
We define elements of \(\mathbb{Q}\), which we denote \(\frac{a}{b}\) to be the equivalence classes \([(a,b)]=\{(a,b),(2a,2b),\dots\}\).
We will not try to summarise the interesting 2019 article by Amir Asghari on the history of equivalence relation (separating the definition from when the notion was first used), but we would recommend it as something worth reading just to showcase how ideas can be used before they are formalised, and how the mathematics we do today is different from how mathematics used to be done. The full reference is Asghari, A. Equivalence: an attempt at a history of the idea. Synthese 196, 4657–4677 (2019). https://doi.org/10.1007/s11229-018-1674-2