21.2. Example of an Equivalence Relation

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 is not satisfied, the relation will not be called as an equivalence Relation.

An equivalence relation is defined based on three key properties: reflexivity, symmetry, and transitivity. Reflexivity means that every element relates to itself. Symmetry means if one element is related to another, then the second is related to the first. Transitivity means if one element is related to a second, and that second to a third, then the first is also related to the third. These properties must all hold for a relation to be considered an equivalence relation.

Imagine a classroom setting. If all students must agree on being friends (reflexive), if if student A is friends with student B, then B is friends with A (symmetric), and if student A is friends with B and B is friends with C, then A is also friends with C (transitive), then we can say that these friendships represent an equivalence relation.

So, let us see an example. I define a relation over ℤ here and by relation here is that an integer a will be related to integer b if a ≡ b (mod m). We say an integer a and integer b are congruent with respect to modulo m if the remainder obtained by dividing a by m is exactly the same as the remainder obtained by dividing b by m.

This chunk describes a specific equivalence relation among integers called congruence modulo m. Two integers a and b are said to be congruent modulo m, denoted as a ≡ b (mod m), if when each integer is divided by m, they leave the same remainder. For example, if m is 3, then 4 and 7 are congruent modulo 3 because both leave a remainder of 1 when divided by 3.

Consider a clock that operates on a 12-hour cycle. If it is 3 o'clock now and after 10 hours it will be 1 o'clock, you can think of the time wrapping around like congruences in modular arithmetic. Here, 3 is equivalent to 1 mod 12, as they are in the same equivalence class.

Now my claim is that this relation R is an equivalence relation. It satisfies the property of reflexive relation, Symmetric relation and transitive relation. So, let us prove that...

The lecture goes on to prove that the relation R is indeed reflexive, symmetric, and transitive. For reflexivity, for any integer a, the condition a ≡ a holds because (a - a) is 0, which is divisible by any m. For symmetry, if a ≡ b, then (b - a) must also be divisibly related to m. For transitivity, if a ≡ b and b ≡ c, then a must also be congruent to c, completing the proof that R is an equivalence relation.

Imagine a group of siblings discussing who is taller. If sibling A is taller than sibling B, and sibling B is taller than sibling C, then sibling A is taller than sibling C—a clear relationship that can extend through other siblings. This mirrors the transitive property in equivalence relations.

So, now let us define equivalence classes. Imagine R is an equivalence relation over some set A. And now consider an element a ∈ A. Then the equivalence class of A which is denoted by [a] consists of all the elements from the set A which are related to this element a as per the relation R.

An equivalence class groups all elements of set A that are related to a given element a under relation R. This is denoted as [a] and includes all elements in A that have the same relationship (in this case, the same remainder when divided by m). Importantly, equivalence classes exhibit the property that they are non-empty as they always include the element a itself because of reflexivity.

Using the sibling analogy again, if setting A represents the ages of all siblings, each sibling belongs to an equivalence class determined by their relationship to others based on if they share the same birth month, reinforcing that not only are there groups based on age but they also relate through shared experiences during those months.

Let me demonstrate what exactly equivalence class looks like with an example. So, I consider this relation R over set of integers ℤ where an integer is related if a ≡ b (mod 3). So, [0] = {…,−9,−6,−3,0,3,6,9,…}, and [1] = {…,−8,−5,−2,1,4,7,10,…}.

This section uses specific integers to elucidate what equivalence classes look like in practical terms. For the relation R where congruences are modulo 3, the equivalence class of 0 includes all multiples of 3, while the equivalence class for 1 contains integers that give a remainder of 1 when divided by 3. Such classes clarify how integers can be grouped.

Think of these equivalence classes like color groups in an art class where all similar colored artworks are placed together. The artwork might all appear blue, for example, belonging to the equivalence class of 'blue artwork', as they represent a shared characteristic—just as integers grouped by their remainders do.

it turns out that the two equivalence classes are either the same or they are completely disjoint. For instance, if I consider [0] and [1], there will be no common element between them as per the relation R.

This chunk explains a key property of equivalence classes: they do not overlap. If two equivalence classes are equal, they contain the same elements; if they are not equal, they share no elements whatsoever, which helps in visualizing and organizing sets in mathematics.

Picture clubs in a school where students can only belong to one club, like a sports club or an art club. If a student is in the sports club, they cannot be in the art club, illustrating the idea that equivalence classes (clubs) don't share members (elements).

--