21.4. Equivalence Classes

So, what is the formal definition of an equivalence relation? It is a relation R over a set A which satisfies three properties namely the relation should be reflexive, the relation should be symmetric and the relation should be transitive. It should satisfy all these three properties. If any of these three properties are not satisfied, the relation will not be called an equivalence relation.

An equivalence relation is a specific type of relation defined on a set, which must satisfy three key properties: reflexivity, symmetry, and transitivity. Reflexivity means every element is related to itself (for example, a = a). Symmetry means if one element is related to another, then the second is related to the first (if a is related to b, then b is related to a). Transitivity indicates that if one element is related to a second, and that second is related to a third, then the first is related to the third (if a is related to b and b is related to c, then a is related to c). Only if all three conditions hold can we call the relation an equivalence relation.

Think of equivalence relations like friendship groups. If Alice is friends with Bob (symmetry), and if Bob is friends with Charlie (transitivity), then Alice is also friends with Charlie. Reflexivity is like saying you’re always friends with yourself. If someone doesn’t fulfill these friendship rules, they aren’t truly ‘friends’ in the same sense.

Now let’s see an example. So, I define a relation over $\mathbb{Z}$ here and by relation here is that an integer a will be related to integer b if $a \equiv b \ mod \ m$. We say an integer a and integer b are congruent with respect to modulo m if the remainder which I obtained by dividing a by the modulus m is exactly the same as the remainder which I obtained by dividing b by the modulus m.

In this example, we consider integers and a relation defined by congruence modulo m, which means two integers a and b are considered equivalent if dividing both by the same integer m results in the same remainder. For instance, if m is 3, both 6 and 9 yield a remainder of 0. Hence they are equivalent in terms of this relation. The equivalence relation satisfies reflexivity (an integer divided by itself gives the same remainder), symmetry (if a is equivalent to b, then b must be equivalent to a), and transitivity (if a is equivalent to b and b is equivalent to c, then a must be equivalent to c).

Imagine you're organizing a sports tournament. If teams can only play other teams that have the same number of wins (which represent their remainders when counting wins), then teams with the same win number can be grouped together, similar to how integers are grouped in equivalence classes based on their remainders.

Imagine R is an equivalence relation over some set A. And now consider an element a ∈ A. The equivalence class of A which is denoted by this notation you have the square bracket and within that you have the element a. So, the equivalence class of [a] consists of all the elements from the set A which are related to this element a as per the relation R.

The equivalence class of an element a, denoted [a], includes all elements in set A that are related to a through the equivalence relation R. Importantly, each equivalence class is a subset of A. A crucial property of equivalence classes is that they are always non-empty; the element a itself is always included in its class due to the reflexive property of the equivalence relation. This means, regardless of what R is, every element will at least belong to its own equivalence class.

Consider a classroom where students are grouped based on their favorite color. Everyone who likes blue forms the blue equivalence class. Even if some students have different shades of blue, every person who claims blue as their favorite is part of the same classification (the equivalence class of blue), and they definitely include themselves in the group.

So, what will be the equivalence class of 0? So, [0] will have all the elements b such that 0 is related to those integers b. And it easy to see that equivalence class of [0] will definitely include 0 itself, and other numbers which are multiples of 3, because they share the same remainder when divided by 3.

When looking at the equivalence class of 0 with respect to modulo 3, we find that it includes all integer multiples of 3 — ..., -6, -3, 0, 3, 6, ... — because all these numbers will give the same remainder (0) when divided by 3. The classes for other numbers, such as 1 or 2, will consist of numbers that fit that specific remainder category when considering modulo 3.

This can be compared to a program where employees are rewarded based on how many projects they completed under a deadline. If the deadline is flexible (like modulo), all employees who completed 0 projects are in one group, those who completed 1 are in another, and so forth. Each group represents an equivalence class based on the project completion remainder.

It turns out that the two equivalence classes in this sequence are either the same or they are completely disjoint. For instance, there will be no common element between [0] and [1], meaning no integer exists that can belong to two different equivalence classes simultaneously based on the established relation R.

The important property of equivalence classes is their mutual exclusivity: any two distinct equivalence classes do not share any elements. That is, if two equivalence classes are not equal, they do not overlap at all. This highlights a way of organizing elements into exclusive groups based on the equivalence relation.

Think of flavors in an ice cream shop. Each flavor represents an equivalence class; if you have vanilla (class) and chocolate (another class), you cannot have an ice cream cone that is both vanilla and chocolate at the same time (distinct and disjoint groups). You choose one or the other.

--