21.3. Properties of Equivalence Relations

An equivalence relation R over a set A satisfies three properties: reflexive, symmetric, and transitive. If any of these properties is not satisfied, the relation is not considered an equivalence relation.

An equivalence relation is a special type of mathematical relationship between elements of a set. There are three key properties that define it:

1. Reflexive: Every element is related to itself. For every a in set A, the relation R must include (a, a).

2. Symmetric: If one element is related to another, then the second must be related to the first. If (a, b) is in R, then (b, a) must also be in R.

3. Transitive: If one element is related to a second, and that second is related to a third, then the first is also related to the third. If (a, b) is in R and (b, c) is in R, then (a, c) must also be in R.

Think of equivalence relations like friendships between people. If Alice is friends with herself (reflexive), and if Alice is friends with Bob, then Bob is also friends with Alice (symmetric). Furthermore, if Alice is friends with Bob, and Bob is friends with Charlie, then Alice is also friends with Charlie (transitive).

Consider the relation R over integers ℤ where an integer a is related to integer b if a ≡ b (mod m). This means that a and b have the same remainder when divided by m.

This example introduces congruence modulo m as an equivalence relation. To say that a is equivalent to b modulo m means that when you divide both a and b by m, they leave the same remainder. For instance, if m=3, then:

• 4 ≡ 1 (mod 3) because both 4 and 1 leave a remainder of 1 when divided by 3.

A crucial step in this argument is to demonstrate that this relation is reflexive, symmetric, and transitive:

• Reflexive: For all integers a, a is congruent to itself.
• Symmetric: If a is congruent to b, then b is congruent to a.
• Transitive: If a is congruent to b and b is congruent to c, then a must be congruent to c.

Imagine you are at a park with friends, and you all have different types of snacks. If you and another friend both have granola bars (the same 'snack type'), you could say you're equivalent in terms of snacks. Now, if your other friend also has a granola bar, then all three of you can be said to be equivalent in terms of snacks, demonstrating the properties of equivalence relations.

For the relation R to qualify as an equivalence relation:

1. Reflexive: a must be related to a, as shown by a - a = 0.
2. Symmetric: If (a, b) is in R, then (b, a) is also in R.
3. Transitive: If (a, b) and (b, c) are in R, then (a, c) must also be in R.

Each property of the equivalence relation shows how pairs of numbers relate to one another. To prove each property:

• Reflexivity holds because a - a = 0, which is divisible by m.
• Symmetry is shown by assuming (a, b) is in R, then a being equal to b implies b is equal to a.
• Transitivity is done by linking a and b to c - if a is related to b (a - b) and b is related to c (b - c), then we can conclude that a is related to c (a - c), which follows the mathematical rules of addition.

Consider a group project: if you and a friend agree on certain rules (cooperative agreement), it follows that your friend agrees with your teammate too (sympathy in views). The same rules apply to everyone in the group, demonstrating reflexivity (each individual agrees with themselves) and transitivity (if everyone agrees, then relationships between pairs are maintained).

For any equivalence relation R over a set A, an equivalence class [a] is the set of all elements related to a under R. It includes all elements b in A such that (a, b) is in R.

An equivalence class groups together all elements that are equivalent under the relation. For example, if R represents 'having the same remainder when divided by 3', then:

• The equivalence class of 0 includes all multiples of 3: {..., -9, -6, -3, 0, 3, 6, 9,...} because all these integers give a remainder of 0 when divided by 3.
• Similarly, the equivalence classes for 1 and 2 will also include integers that give a remainder of 1 and 2 respectively, when divided by 3.

Think of equivalence classes like sports teams where each team contains players who fulfill specific criteria (e.g., all players on a football team are considered a part of that team regardless of their individual differences).

Equivalence classes are either completely disjoint or identical. If [a] = [b], then elements are in the same class; if [a] ∩ [b] is empty, they are in different classes.

Equivalence classes exhibit a unique property: they do not overlap, which means two classes cannot share elements. Mathematically, if [a] and [b] are equivalent classes representing a relation, if they intersect non-trivially, they must be the same class, reinforcing the integrity of the equivalence relation structure.

Imagine a library sorting books into genres. A book can either belong to one specific genre shelf (like 'Fantasy') or another (like 'Science Fiction'), but it cannot exist on both shelves. This rule mirrors how equivalence classes work: they are exclusive or identical.

--