Equivalence relation

An equivalence relation is a binary relation on a set that is reflexive, symmetric and transitive.

Motivation

An equivalence relation is a sort of refinement of equality. We can always decide whether two elements of a set are the same, that is whether a = b. But sometimes it is useful to find out whether two elements are merely similar, not necessarily the same. In other words, whether they share some essential property. For example, we can consider two books similar if they have the same genre – or, using equivalence, two books are equivalent if they have the same genre.

What would we expect from such an equivalence? Let’s take another example. Two words are similar/equivalent if they have the same length.

We would probably expect that if we measure the similarity of two identical words, we find that they are similar. So every word must be similar/equivalent to itself. In the language of relations: an equivalence relation must be reflexive.

Next, if the word “brook” is similar/equivalent to the word “Alice”, then we certainly expect that the word “Alice” is equivalent to the word “brook”. In other words, the order does not matter. In the language of relations: an equivalence relation must be symmetric.

And finally, if the word “dust” is similar/equivalent to the word “bird” and the word “bird” is equivalent to the word “foot”, then we expect the pair of words “dust” and “foot” to be equivalent too. So an equivalence relation must also be transitive.

We expect nothing else from an equivalence.

Examples

Some more examples of equivalences:

• Living in the same town. Oliver certainly lives in the same town as Oliver (reflexivity). If Oliver lives in the same town as Harry, then Harry lives in the same town as Oliver (symmetry). And if Harry lives in the same town as George, then Oliver lives in the same town as George (transitivity).
• Songs by the same songwriter. The song “Angry Monologue of a Drain Cover” certainly has the same songwriter as the song “Angry Monologue of a Drain Cover” (reflexivity). If the songs “Angry Monologue of a Drain Cover” and “War on the Doorstep” have the same songwriter, then “War on the Doorstep” and “Angry Monologue of a Drain Cover” have the same songwriter (symmetry). And if “War on the Doorstep” and “Quest for the Truth About Dirt” have the same songwriter, then “Angry Monologue of a Drain Cover” and “Quest for the Truth About Dirt” have the same songwriter (transitivity).
• (a, b) ∈ R if and only if a − b is an even number; a, b are integers. Reflexivity: a − a = 0, and zero is an even number. Symmetry: let c = a − b. Then b − a = −(a − b) = −c. If c is even, then −c must be even too. Transitivity: let p = a − b and q = b − c. We know that both p and q are even numbers. Now we have to prove that a − c is an even number. In this expression we substitute for c, using c = b − q: a − (b − q), which equals a − b + q. By our assumptions, a − b is an even number. If we add another even number q to an even number, we again get an even number.
• Equality. Equality is an equivalence, and it is also the smallest equivalence on any set M.

Trivial equivalence

We have a non-empty set M. What is the smallest possible equivalence R on the set M? The smallest possible subset of the Cartesian product M × M is the empty set ∅. Does the empty set satisfy the conditions of an equivalence?

It is certainly symmetric: since the relation R has no elements, the condition of symmetry is automatically and trivially satisfied. Transitivity is the same. The problem is reflexivity. The definition says that for all elements x of the set M we have (x, x) ∈ R. Is this satisfied? The set M is non-empty, so it contains some element, say q. Is the pair (q, q) in the relation R? It is not. So the relation R is not reflexive.

What is the smallest relation that satisfies reflexivity? The relation of equality. The relation R must contain at least the pairs (x, x) for all elements of M. That is exactly the identity relation. Is such a relation symmetric? It is easy to see that it is. It is just as easy to see that it is transitive. The smallest equivalence relation on a set M is therefore the identity relation, which we denote id_M, and it contains the pairs (x, x) for all x ∈ M.

What is the largest possible equivalence on the set M? The largest subset is the whole set M × M. Does it satisfy the conditions of an equivalence? It is probably obvious that it does.

Equivalence class

Every equivalence splits the set M into a system of disjoint sets, which we call equivalence classes.

Let M be the set of all words and R the equivalence “words of the same length”. That is, (a, b) ∈ R if and only if the words a and b have the same length. This equivalence splits the set of words into several smaller sets, each of which always contains words of the same length. We can tell the individual equivalence classes apart by a subscript, which also indicates the length of the words in the given set:

• M₁ = {a, I, …}
• M₂ = {we, do, so, my, me, …}
• M₃ = {and, but, the, tap, …}
• M₄ = {dust, park, lift, farm, …}
• …

Notice two things: 1) the individual sets are disjoint, with no element in common. 2) all the elements in any one set are equivalent to each other. All the words in the set M₃ are equivalent to each other, because they all have length three, that is the same length, which is the condition for equivalence.

Each element also uniquely determines its equivalence class. We usually write this using the notation M[x], where x ∈ M. If we write M[and], we uniquely specify the equivalence class that we have already called M₃.

How do we actually find the equivalence class if we know some x ∈ M? We go through all the elements of M and find out which of them are equivalent to the element x. Those will be all the elements that belong to the equivalence class M[x].

For M[and] we would go through all the words in M and keep in M₃ those words that have length three.

Definition and properties of an equivalence class

We can define an equivalence class like this. Let M be a set with an equivalence R defined on it. Then the equivalence class containing the element x ∈ M is:

$$M[x]=\{y\in M;(x,y)\in R\}$$

The definition says that it consists of all y that are equivalent to the given element x. Because an equivalence relation is reflexive, the element x itself is included too – since x is equivalent to itself.

The partition given by an equivalence is then the set of all equivalence classes. So the partition of the set of all words would be the set {M₁, M₂, M₃, …}.

Basic properties of equivalence classes:

• (a, b) ∈ R if and only if M[a] = M[b]. If we have two elements a, b that are equivalent, then their equivalence classes must be equal.
• Conversely, if (a, b) ∈ R does not hold, then also M[a] ≠ M[b], or more precisely M[a] ∩ M[b] = ∅. If we have two elements that are not equivalent, then their classes are disjoint.
• The union of all equivalence classes must give the original set M: M₁ ∪ M₂ ∪ … ∪ M_n = M. (This notation is only for a finite number of equivalence classes, but in general there may be infinitely many.)

Examples of partitions given by an equivalence

The first example, odd and even numbers:

Let R be a simple equivalence defined on the positive integers ℤ⁺. (a, b) ∈ R if and only if both a and b are odd or both a and b are even. Examples of pairs: (1, 7), (13, 9), (4, 6), (8, 136). Now let’s work out the partition into equivalence classes given by this equivalence.

We start step by step. What is the class ℤ⁺[1] equal to? We have to find all the numbers that are equivalent to the number one. By the condition of the equivalence these are all the odd numbers, so ℤ⁺[1] = {1, 3, 5, 7, 9, …}.

What is the class ℤ⁺[2] equal to? We find all the numbers that are equivalent to two. These are all the even numbers: ℤ⁺[2] = {2, 4, 6, 8, 10, …}.

Now ℤ⁺[3]. Which numbers are equivalent to three? All the odd numbers. But that gives us the set ℤ⁺[1], which we worked out two paragraphs ago. Similarly for ℤ⁺[4], which again gives the set of even numbers.

We can see that from here on the same sets would keep repeating. This is also clear from the fact that whichever further positive integer n we take, either n ∈ ℤ⁺[1] or n ∈ ℤ⁺[2]. We have no positive integers other than odd and even ones, so these two sets form the partition given by the equivalence.

It is similar to imagining an equivalence on a set of people where both a and b are men or both a and b are women. The partition would then be the set of women and the set of men.

The second example, absolute value:

Let R be an equivalence on the set of integers ℤ defined as follows: (a, b) ∈ R if and only if |a| = |b|. (Those vertical lines mean the absolute value.) Again we go step by step:

• ℤ[0] = {0}. Zero is related only to zero.
• ℤ[1] = {−1, 1}. One is related to one and to minus one, because |1| = |−1|.
• ℤ[2] = {−2, 2}. Two is related to two and to minus two.
• ℤ[3] = {−3, 3}.
• …

It is probably clear how this continues. The whole partition would therefore be the set of classes:

$$\{\{a,-a\};a\in {\mathbb{N}}_0\}$$

(That is, all the pairs a, −a, where a is a non-negative integer.) You can see that there are infinitely many classes.