Equivalence Relations

We have seen that certain common relations such as "=", and congruence (which we will deal with in the next section) obey some of these rules above. The relations we will deal with are very important in discrete mathematics, and are known as equivalence relations. They essentially assert some kind of equality notion, or equivalence, hence the name.

Characteristics of equivalence relations

For a relation R to be an equivalence relation, it must have the following properties, viz. R must be:

• symmetric
• transitive
• reflexive

(A helpful mnemonic, S-T-R)

In the previous problem set you have shown equality, "=", to be reflexive, symmetric, and transitive. So "=" is an equivalence relation.

We denote an equivalence relation, in general, by $x\sim y$.

Example proof

Say we are asked to prove that "=" is an equivalence relation. We then proceed to prove each property above in turn (Often, the proof of transitivity is the hardest).

• Reflexive: Clearly, it is true that a = a for all values a. Therefore, = is reflexive.
• Symmetric: If a = b, it is also true that b = a. Therefore, = is symmetric
• Transitive: If a = b and b = c, this says that a is the same as b which in turn is the same as c. So a is then the same as c, so a = c, and thus = is transitive.

Thus = is an equivalence relation.

Partitions and equivalence classes

It is true that when we are dealing with relations, we may find that many values are related to one fixed value.

For example, when we look at the quality of congruence, which is that given some number a, a number congruent to a is one that has the same remainder or modulus when divided by some number n, as a, which we write

a ≡ b (mod n)

and is the same as writing

b = a+kn for some integer k.

(We will look into congruences in further detail later, but a simple examination or understanding of this idea will be interesting in its application to equivalence relations)

For example, 2 ≡ 0 (mod 2), since the remainder on dividing 2 by 2 is in fact 0, as is the remainder on dividing 0 by 2.

We can show that congruence is an equivalence relation (This is left as an exercise, below Hint use the equivalent form of congruence as described above).

However, what is more interesting is that we can group all numbers that are equivalent to each other.

With the relation congruence modulo 2 (which is using n=2, as above), or more formally:

x ~ y if and only if x ≡ y (mod 2)

we can group all numbers that are equivalent to each other. Observe:

$0\equiv 2\equiv 4\equiv \ldots {\pmod {2}}$

$1\equiv 3\equiv 5\equiv \ldots {\pmod {2}}$

This first equation above tells us all the even numbers are equivalent to each other under ~, and all the odd numbers under ~.

We can write this in set notation. However, we have a special notation. We write:

$[0]=\{0,2,4,...\}$

$[1]=\{1,3,5,...\}$

and we call these two sets equivalence classes.

All elements in an equivalence class by definition are equivalent to each other, and thus note that we do not need to include [2], since 2 ~ 0.

We call the act of doing this 'grouping' with respect to some equivalence relation partitioning (or further and explicitly partitioning a set S into equivalence classes under a relation ~). Above, we have partitioned Z into equivalence classes [0] and [1], under the relation of congruence modulo 2.

Problem set

Given the above, answer the following questions on equivalence relations (Answers follow to even numbered questions)

1. Prove that congruence is an equivalence relation as before (See hint above).
2. Partition {x | 1 ≤ x ≤ 9} into equivalence classes under the equivalence relation

$x\sim y\ {\mbox{iff}}\ x\equiv y{\pmod {6}}$

Answers

2. [0]={6}, [1]={1,7}, [2]={2,8}, [3]={3,9}, [4]={4}, [5]={5}