Equivalence relations

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

Motivation

The equivalence relation is a kind of refinement of the equality relation. We can always decide that two elements of a set are equal, i.e., that a = a. But sometimes it is useful to see if two elements are only similar, not necessarily equal. Or - whether they have the same essential property. For example, two books can be considered similar if they have the same genre - or by equivalence: two books are equivalent if they have the same genre.

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

We would probably expect that if we measure the similarity of two words that they come out similar. So it must be true for all words that they are similar/equivalent to themselves. In relational language: the equivalence relation must be reflexive.

Further, if the word "brook" is similar/equivalent to the word "Agatha", then surely we expect the word "Agatha" to be equivalent to the word "brook". In other words, the order does not matter. In relational language: the equivalence relation must be symmetric.

Finally, if the word "death" is similar/equivalent to the word "bird", and the word "bird" is equivalent to the word "foot", then we expect pairs of the words "death" and "foot" to be equivalent as well. Thus, the equivalence relation must also be transitive.

We expect nothing more from equivalence.

Examples

More examples of equivalences:

• Live in the same city. Jirka certainly lives in the same city as Jirka (reflexivity). If Jirka lives in the same city as Ondra, then Ondra lives in the same city as Jirka (symmetry). And if Ondra lives in the same city as Martin, then Jirka lives in the same city as Martin (transitivity).
• Songs with the same author. The song "The Furious Monologue of the Son of the Hatch" certainly has the same author as the song "The Furious Monologue of the Son of the Hatch" (reflexivity). If the songs "The Furious Monologue of the Son of the Hatch" and "War on the Rags" have the same author, then "War on the Rags" and "The Furious Monologue of the Son of the Hatch" have the same author (symmetry). And if "The War on Staves" and "The Quest for the Truth of Filth" have the same author, then "The Furious Monologue of the Son of the Hatch" and "The Quest for the Truth of Filth" have the same author (transitivity).
• [a, b] ∈ R Just when a − b is an even number; a, b are whole numbers. Reflexivity: a − a = 0, zero is an even number. Symmetry: denote c = a − b. Then b − a = −(a − b) = −c. If c is even, then −c must be even. Transitivity: denote p = a − b, then q = b − c. We know that p and q are both even numbers. Now we have to prove that a − c is an even number. We substitute c = b − q: a−(b − q), which equals a − b + q, into this equation after c. From the assumptions, we know that a − b is an even number. If we add another even number to the even number q, we get an even number again.
• Equality. Equality is equivalence, it is also the smallest equivalence on any set M.

Trivial equivalence

We have a nonempty set M. What is the smallest possible equivalence of 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 equivalence conditions?

It is certainly symmetric, since the session R has no elements, the symmetry condition is automatically and trivially satisfied. Similarly, transitivity. The problem is with reflexivity. The definition says that for all elements x of the set M, it is true that [x, x] ∈ R. Is this satisfied? The set M is nonempty, so it contains some element, for example q. Is the pair [q, q] in the session R? It is not. Thus the session R is not reflexive.

What is the smallest session satisfying reflexivity? An equality session. A session R must contain at least the pair [x, x] for all elements of M. Which is just an identity session. Is such a session symmetric? It is easy to see that it is. Similarly, it is easy to see that it is transitive. Thus the smallest equivalence relation on the set M is an identity relation, denoted id_M, and contains the pairs [x, x] for all x ∈ M.

What is the largest possible equivalence on the set M? The largest subset is the entire set M × M. Does it satisfy the equivalence conditions? It is probably trivial to see that it does.

Equivalence class

Each equivalence partitions the set M into a system of disjunctive sets, which we then call equivalence classes.

Consider the set of all words M and the equivalence R of the same word length. That is, [a, b] ∈ R just when the words a and b have the same length. This equivalence splits the set of words into several smaller sets that will always contain words of the same length. We can distinguish the different equivalence classes by using a subscript that will also distinguish the length of the words in the set:

• M₁ = {a, i, o, e, …}
• M₂ = {ve, do, se, my, mi, …}
• M₃ = {ale, bez, ten, tam, …}
• M₄ = {smrt, park, lest, niva, …}
• ...

Notice two things: 1) the individual sets are disjunctive, having no common element. 2) all elements in each individual set are equivalent to each other. All words in the set M₃ are equivalent to each other because all words are of length three, the same length, which is the equivalence condition.

In doing so, each element uniquely defines its equivalence class. We usually write this using the notation M[x], where x ∈ M. If we were to write M[ale], we would be unambiguously defining the equivalence class, which we have already marked as M₃.

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

For M[ale], we would go through all the words in M and store in M₃ those words that are of length three.

Equivalence class definition and properties

We could define an equivalence class as follows. Consider the set M and the equivalence R defined on it. Then the decomposition class that contains the element x ∈ M, we understand:

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

The definition says that these are all y that are equivalent to the specified element x. Since the equivalence relation is reflexive, the element x gets there this way - since x is equivalent to itself.

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

Basic properties of equivalence classes:

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

Examples of equivalence decompositions

First example, odd and even numbers:

Consider the simple equivalence R defined on the natural numbers N. [a, b] ∈ R just when a and b are both odd or a and b are both even. Examples of elements: [1, 7], [13, 9], [4, 6], [8, 136]. Let us now determine the decomposition of this equivalence into equivalence classes.

We will start sequentially. What will the class N[1] be equal to ? We need to find all the numbers that are equivalent to one. According to the equivalence condition, these are all odd numbers, so N[1] = {1, 3, 5, 7, 9, …}.

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

Now N[3]. What numbers are equivalent to three? All odd numbers. But this gives us the set N[1], which we calculated in the previous paragraph. Similarly for N[4], there again the set of even numbers.

We can see that from here on, the same sets would keep repeating. This can be seen also from the fact that whatever other natural number n, we take, it will already be true that n ∈ N[1] or n ∈ N[2]. We have no natural numbers other than odd and even numbers, so these two sets form an equivalence decomposition.

This is similar to imagining equivalence on the set of people a i b is a man or a i b is a woman. Then we would get a set of women and a set of men as a decomposition.

Second example, absolute value:

Let's have an equivalence R on the set of integers Z defined as follows: [a, b] ∈ R just if |a| = |b|. (The vertical lines are the absolute value.) Again, we'll go sequentially:

• Z[0] = {0}. Zero is in a relation with zero only.
• Z[1] = {−1, 1}. One is in a relation with one and minus one because |1| = |−1|.
• Z[2] = {−2, 2}. Two is in a relation with two and with minus two.
• Z[3] = {−3, 3}.
• ...

I guess it's clear how this is going to go. So the whole decomposition would be a set of classes:

$${{a, -a}; a \in \mathbb{Z}_0^+}$$

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