11.3 Quick review and some even Exercises

A relation $R$ on $A$ is an equivalence relation if it is reflexive, symmetric and transitive.

If $R$ is an equivalence relation, then when two things are related in $R$ they are equivalent in some way.

To show relation $R$ is not an equivalence relation, simply show that it is missing on of the three properties.

Since equivalence is transitive, it divides $A$ into disjoint groupings where everything in a group is mutually related. Each group is called an equivalence class.

The group of items that $x$ is equivalent to is denoted $[x]$, which is defined as

$[x] = \{ y : (x,y) \in R \}$

Ex: Let $R = \{ (x,y) \in \mathbb{Z} \times \mathbb{Z} : x \bmod 3 = y \bmod 3\}$ (ie, two items are related if their remainders when divided by 3 are the same).

One equivalence class is all of the integers that when divided by 3 leave remainder 0.

$[0] = [3] = [6] = \cdots = \{ y : (0,y) \in R \} = \{\ldots, -6, -3, 0, 3, 6, \ldots\}$

Another equivalence class is all of the integers that when divided by 3 leave remainder 1.

$[1] = [4] = [7] = \cdots = \{ y : (1,y) \in R \} = \{\ldots, -5, -2, 1, 4, 7, \ldots\}$

The last equivalence class is all of the integers that when divided by 3 leave remainder 2.

$[2] = [5] = [8] = \cdots = \{ y : (2,y) \in R \} = \{\ldots, -4, -1, 2, 5, 8, \ldots\}$

Exercise 2: Let $A = \{a, b, c, d, e\}$. Suppose $R$ is an equivalence relation on $A$. Suppose $R$ has two equivalence classes. Also $aRd$, $bRc$ and $eRd$. Write out $R$ as a set.

This is an exercise in deductive reasoning. They don't tell you all the relations, but they tell you enough to deduce the answer.

Because $aRd$ and $eRd$ we know $a$ and $d$ are in the same class and $e$ and $d$ are in the same class. This means $a$, $d$ and $e$ are in the same class.

Since $bRc$, those two are together, but since neither of them is related to $a$, $d$ or $e$, they must be in a separate class.

So, the two equivalence classes must be $\{a,d,e\}$ and $\{ b,c\}$. But, the question asks for the full relation. We know that every pair of elements in the same equivalence class is related — including self-pairs — so the key to writing the relation is to write all pairs for each equivalence class.

   for x = a ... e
      for y = a ... e
         if x and y are in the same equivalence class
            print (x,y)

Solution 2: $R = \{ (a,a), (a,d), (a,e), (b,b), (b,c), (c,b), (c,c), (d,a), (d,d), (d,e), (e,a), (e,d), (e,e)\}$.

Exercise 6: There are five different equivalence relations on the set $A = \{a, b, c\}$. Describe them all.

Since each equivalence relation divides $A$ into equivalence classes, one way of doing this problem is to write out all the different ways of dividing $A$ into disjoint subsets. Each way of doing so could be turned into a corresponding relation, like in Exercise 2.

Solution 6: $\{a\} \{b\} \{c\}$ $\{a\} \{b,c\}$ $\{a,b\} \{c\}$ $\{a,c\} \{b\}$ $\{a,b,c\}$