21.1. Definition of 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, the professor sets the stage for learning about equivalence relations. After discussing various types of mathematical relations in a previous lecture, we now focus on a special type of relation—equivalence relations. An equivalence relation is a way of grouping elements such that certain properties hold.

Think of equivalence relations like a club where members share common characteristics. Just as club members might both enjoy sports or music, elements in an equivalence relation share a specific property that links them together.

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 by three key properties: reflexivity, symmetry, and transitivity. Reflexivity means every element is related to itself. Symmetry means if one element is related to another, the second is also related to the first. Transitivity means if one element relates to a second, and that second relates to a third, then the first and third must relate. If any of these properties fail to hold, the relation cannot be considered an equivalence relation.

Consider a family relationship. If you think of being a sibling as a relation, it is reflexive (a sibling is a sibling to themselves), symmetric (if A is a sibling to B, then B is a sibling to A), and transitive (if A is a sibling to B and B is a sibling to C, then A is also a sibling to C).

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.

The example provided uses integers and a modulus (m). Two integers a and b are considered equivalent if they give the same remainder when divided by m. This means that they are congruent under modulo m conditions. To understand this in mathematical terms, we express it as a ≡ b (mod m).

Imagine you have a clock that resets every 12 hours. If it's 10 o’clock now, in 14 hours, it will show 12 o’clock. In this example, 10 and 12 are equivalent times on a 12-hour clock, similar to how integers can be equivalent under modulo conditions.

Now my claim is that this relation R is an equivalence relation. It satisfies the property of reflexive relation. So, let us prove that. So, let us check: a is congruent to a modulo m, which gives us (a - a) ≡ 0 (mod m). Thus, every integer a is always congruent to itself modulo m, fulfilling the reflexivity requirement.

In proving that our relation is reflexive, we check if an integer a is always related to itself. By the definition of equivalence relations, since (a - a) equals zero, it shows that every integer has a congruence with itself when considered under any modulus m. This confirms the reflexivity property.

Think of this as looking in a mirror. Just as your reflection shows you exactly as you are, each integer reflects back to itself in this congruence relation. You always recognize yourself!

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). This means if a is related to b, then b must also be related to a, satisfying the symmetry condition.

To show that the relation is symmetric, we take two integers, a and b. If a is congruent to b (which means they give the same remainder when divided by m), then under the same modulus, b must also give the same remainder when divided by m with respect to a. Therefore, the symmetry condition holds.

Imagine two friends borrowing books from each other. If Alice lends a book to Bob, it’s reasonable to say that Bob can lend a book back to Alice. Their relationship (the borrowing of books) reflects this symmetry beautifully.

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 a is related to c. If (a - b) and (b - c) are both divisible by m, then (a - c) must also be divisible by m.

To prove transitivity, we consider three integers a, b, and c. If a is related to b (a ≡ b (mod m)), and b is related to c (b ≡ c (mod m)), then by adding these two relationships, we also find that a is related to c (a ≡ c (mod m)). This is essential to confirming that our relation qualifies as an equivalence relation.

Take a chain of friendships. If Alice is friends with Bob, and Bob is friends with Charlie, it follows that Alice and Charlie are part of the same social circle. The friendships create a chain, reflecting the transitive nature of relationships.

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 this notation you have the square bracket and within that you have the element a. So, the equivalence class of [a] = {b:(a,b) ∈ R}, consist of all the elements from the set A which are related to this element a as per the relation R.

An equivalence class gathers all elements that share a particular relationship defined by R with a specific element a. Denoted as [a], the class includes every element related to a under the equivalence relation. This set is a collection of all elements considered equivalent to a.

Think of this as a club of people (the equivalence class) who share the same interest (the membership condition). If a is a member of a cooking club, then all the other members who love cooking too are in the equivalence class [a].

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. This element is the element a itself. Because the element a is always related as per the relation R due to reflexivity.

This property reaffirms that every equivalence class must contain at least the element a itself since equivalence relations are reflexive. Thus, no equivalence class will ever be empty; it will always have the representative element of the class.

In an art class, every student has a distinct style (their uniqueness), but they all belong to the same art class. Thus, no student can be part of a class without being themselves—they embody their belonging, just like the equivalence class contains its defining element.

--