21. Equivalence Relation

Hello everyone, welcome to this lecture on equivalence Relations. And just to recap in the last lecture we discussed some special types of relations like Reflexive Relations, Symmetric Relations, Asymmetric relations, Anti Symmetric Relations, Transitive Relations. So, in this lecture we will introduce a special type of relation called as equivalence Relation and we will see the definition of equivalence classes.

In this introduction, we are setting the stage for discussing equivalence relations as a specific type of relation in mathematics. It builds on previous lectures about various relations such as reflexive, symmetric, and transitive. An equivalence relation is a combination of three key properties: reflexivity, symmetry, and transitivity. This lecture will aim to define what an equivalence relation is and what equivalence classes are.

Think of equivalence relations as a type of friendship criteria among people. If one person sees another as a friend (reflexivity), that person sees them as a friend back (symmetry), and if one person is friends with two people, then these two people are friends with each other (transitivity).

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 strictly by three properties. For a relation R on a set A to be classified as an equivalence relation, it must satisfy the following: 1) Reflexive: for every element a in A, a is related to itself. 2) Symmetric: if a is related to b, then b must also be related to a. 3) Transitive: if a is related to b and b is related to c, then a must also be related to c. If any of these properties fail, then R cannot be considered an equivalence relation.

Imagine a group of friends. If you consider friendships as a relation, each person (friend) must be friends with themselves (reflexive), if you're friends with someone they should also be friends with you (symmetric), and if you're friends with two people, those two friends should know each other as well (transitive). If any of these conditions don't hold, it's not a true friendship group.

So, let us see an example. So, 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, they 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.

This example introduces the concept of congruence in integers as an equivalence relation. Here, two integers a and b are considered equivalent (or congruent modulo m) if they leave the same remainder when divided by m. For example, if m = 3, then 6 and 9 are congruent because both leave a remainder of 0 when divided by 3. This congruence relation is a fundamental equivalence relation in number theory.

Think of a clock: All times that are exactly 3 hours apart (like 1:00 PM and 4:00 PM) can be seen as equal or the same (congruent) because they can be represented on the same 12-hour cycle. So, measuring time in hours mirrors the concept of equivalences in integers.

So, let us prove that so is the relation R reflexive? Answer is yes. Because, (a - a) ≡ 0 (mod m). You divide a whatever remainder you obtain by dividing a by m the same remainder you obtained by dividing a again by m. So, in that sense a is always congruent to a modulo m.

To show that the relation R is reflexive, we demonstrate that every integer a is congruent to itself. When we look at the expression (a - a), it equals 0, which is divisible by any integer m. Hence, by definition, a is congruent to a under modulo m, satisfying the reflexivity condition of equivalence relations.

Imagine a school where every student has their student ID number. Reflexivity means that every student is always equal to themselves. Just like every student verifies their own ID number against the school's record; it's always a match.

The relation R is also symmetric, we can prove that. For proving the symmetric property, I assume that consider an arbitrary pair of integers (a, b) where a ≡ b (mod m) → b ≡ a (mod m).

To prove the symmetry of the relation R, we assume that a is related to b (a ≡ b mod m). According to this property, if (a - b) is divisible by m, then, naturally, (b - a) must also be divisible by m. Therefore, if a is related to b, then b must also be related back to a, validating the symmetric property.

Consider a friendship where if person A says they are friends with person B, then person B also states they are friends with person A. The relations are bidirectional, just like symmetry in equivalence relations.

Now let us prove that the relation R is transitive as well. So, for proving the transitivity property I have to show that, if I have a related to b in my relation and b related to c in the relation, then I have to show that the integer a is related to integer c.

Transitivity means that if a is congruent to b and b is congruent to c, then a must be congruent to c. This can be proven mathematically by starting from the assumptions of congruencies and showing that adding/subtracting them leads to another congruency, completing the transitive link.

Let's say a is a friend of b, and b is a friend of c. By the principle of transitivity, a is also a friend of c. In various relationships, if you connect through someone, it holds true that you share that relationship indirectly.

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, now let us define equivalence classes.

Equivalence classes partition the set based on the equivalence relation. Given an equivalence relation R on a set A, the equivalence class of an element a is the set of all elements in A that are related to a by R. This forms subsets where each subset contains elements that are equivalent to one another.

Think of equivalence classes as different categories of books in a library. All books on a similar subject (like science fiction) are grouped together. Each category represents an equivalence class where the books within are equivalent in themes or genres.

The first trivial thing to check here is verify here is that you take the equivalence class of any element, it will be non- empty. There will be at least one element which is always guaranteed to be present in the equivalence class of any element a...

It is important to note that equivalence classes are never empty. By definition, each equivalence class for an element a will always contain a itself since a is reflexively related to itself. This property ensures that every equivalence class has at least one member.

Returning to our library analogy, every category of books must contain at least one book. You can never have an empty shelf in a library category because there must always be at least one book that matches that genre precisely.

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 to integer b if a ≡ b (mod 3).

This example demonstrates specific equivalence classes for integers under the modulo 3 relation. The equivalence class of an integer contains all integers congruent to it modulo 3, forming distinct groups of classes such as [0], [1], and [2], where each integer is grouped based on its value when divided by 3.

Imagine classifying fruits into categories based on their color. All red fruits (like strawberries and apples) form one equivalence class; all yellow fruits (like bananas) form another. Each fruit belongs to one class based on their color, similar to how integers are grouped by their remainders.

So, what we are observing here is that even though we have equivalence class of every integer possible here. So, these are the various equivalence classes. And this is an infinite list. It turns out that if we closely look here we find that the two equivalence classes in this sequence are either same or they are completely disjoint.

Here, we have established that equivalence classes are mutually exclusive, meaning two classes cannot intersect unless they are identical. For example, the equivalence classes [0] and [1] do not share any elements. This property of disjoint or identical classes is crucial in understanding how equivalence relations structure sets.

Imagine two different clubs that are either the same (like a book club that also has cooking activities) or completely separate (like a book club and a swimming club). There can't be a member who belongs to both clubs unless the clubs are the same.

That brings me to the end of this lecture. Just to recap, in this lecture we introduced the notion of equivalence relation and we also introduced the notion of equivalence classes.

In conclusion, we have delved into equivalence relations, defining their properties, providing examples, and discussing the consequential equivalence classes formed by these relations. This foundation allows for a deeper understanding of more complex mathematical structures.

Just like how in life we categorize relationships based on similarity, the concept of equivalence relations helps us define mathematical relationships in a structured way. It lays the groundwork for understanding larger concepts such as group theory in mathematics.

--