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).

Definition 10.1:

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.

Remark:

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.

Definition 10.2:

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”.
Etymology:

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).

Example:

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.
Example:
Define a relation \sim on \mathbb{R} via x\sim y if and only if x\leq y. We have that \sim is not an equivalence relation because it is not symmetric. Indeed let x=1 and y=2, we have 1\leq 2 so 1\sim 2 but 2\not\leq 1 so 2\not\sim 1. (The relation is however reflexive and transitive).
Example:
We define a relation \sim on the set of all subsets of \mathbb{R} via X\sim Y if and only if there exists a bijection f:X\to Y. Remark 7.2 proved that \sim is reflexive, symmetric and transitive Hence \sim is an equivalence relation. (and the reason why we could define Cardinality in a way that makes sense)
Example:
Define a relation \cong on the set of groups via G\cong H if and only if G is isomorphic to H. This is reflexive (since G is isomorphic to itself via the identity function), Proposition 9.15 shows that \cong is symmetric, and Proposition 9.17 proved that \cong is transitive. So \cong is an equivalence relation (and hence the rationale for why we care about groups “up to isomorphism”).
Definition 10.3:
Suppose \sim is an equivalence relation on a (nonempty) set X. For x\in X, we define the equivalence class of x, denoted by [x], to be [x]=\{y\in X:\ y\sim x \}.
Example:
Let X = \{-1,0,1,2\} and define a relation \sim on X via x\sim y if and only if either x=y or xy>0. One can check this is an equivalence relation (it takes a bit of work to show \sim is transitive). We have the following equivalence classes: Hence, we have three distinct equivalence classes, namely [-1], [0] and [1].

Notice how in the above example each distinct equivalence class did not intersect each other. This is true in general.

Proposition 10.4:

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.

Proof.

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”.

Definition 10.5:

A partition of a non-empty set X is a collection \{A_i: i\in I \} of non-empty subsets of X such that

  1. \forall\,x\in X, \exists\,i\in I such that x\in A_i, and

  2. \forall\,x\in X and \forall\,i,j\in I, if x\in A_i\cap A_j, then A_i=A_j\ .

Remark:

The above two conditions can be rephrased as follows:

  1. X = \bigcup_{i\in I} A_i, and

  2. 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.

Theorem 10.6:

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.

Proof.

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.

Theorem 10.7:

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.

Proof.

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.

Example:

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}_{+}.

Example:

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\}.
History:

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