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