Section 2.4 – Equivalence Relations

definition: A relation $\mathcal R$ on a set $A$ is an equivalence relationship if it is,

  1. Reflexive
  2. Symmetric
  3. Transitive

Example

Consider $\mathcal R$ on $\mathbb Z \times \mathbb Z$, defined by,

Solution

Reflexivity

Let $a \in \mathbb Z$, then,

Therefore $(a,a) \in \mathcal R$.

Symmetry

Let $(a,b) \in \mathcal R$, so,

for some $k \in \mathbb Z$.

Since $-k \in \mathbb Z$, $b - a$ is a multiple of $3$ and therefore $(b,a) \in \mathcal R$.

Transitivity

Let $(a,b) \in \mathcal R$ and $(b,c) \in \mathcal R$, so,

and

for $k, m \in \mathbb Z$. Adding the equations,

Therefore since $(k + m) \in \mathbb Z$, $a - c$ is a multiple of $3$ and therefore $(a,c) \in \mathcal R$.

If $\mathcal R$ is an equivalence relation,

can $A \neq B$?

No, $\mathcal R \subseteq A \times A$.

Equivalence Class

definition: For an equivalence relation $\sim$ on a set $A$, the equivalence class of $a \in A$, is the set of all elements equivalent to $a$.

The set of equivalence classes is called the Quotient set of $A$ mod $\sim$, denoted $A \setminus \sim$.

Partition

definition: A partition of set $A$ is a collection of subsets $A_1, A_3, A_3,...,A_n$ such that,

  • Each is non empty ($A_i \neq \varnothing$)
  • They are pairwise disjoint ($A_i \cap A_j = \varnothing$)
  • They union to $A$ ($\cup_{i=0}^{n} ~A_i = A$)

Fact

If $\sim$ is equivalent to $A$, then,

  1. The set of all its equivalence classes forms a partition of $A$
  2. If $x,y \in A$ then either $[x] = [y]$ or $[x] \cap [y] = \varnothing$

Example

Let $\mathcal R \subseteq \mathbb Z \times \mathbb Z$, such that $(x,y) \in \mathcal R$. if and only if $a - b$ is a multiple of $3$.

Solution

1) What elements are equivalent to $0$?

For $k \in \mathbb Z$. So $3 \mathcal R 0, 6 \mathcal R 0, ...$

Next lets consider $[3]$,

2) What elements are equivalent to $1$?

So,

3) What elements are equivalent to 2?

So our equivalence classes are,

And the partition is,

To confirm this we must check that,

Example

Let $A = { a,b,c,d,e,f }$ and $\mathcal R = { (a,a), (b,b), ..., (f,e) }$

We can represent this in a matrix (which is good because I didn't write the whole thing),

$a$ $b$ $c$ $d$ $e$ $f$ $g$
$a$ $x$ $~$ $~$ $~$ $~$ $~$
$b$ $~$ $x$ $~$ $~$ $~$ $~$
$c$ $~$ $~$ $x$ $~$ $~$ $~$
$d$ $~$ $~$ $~$ $x$ $x$ $x$
$e$ $~$ $~$ $~$ $x$ $x$ $x$
$f$ $~$ $~$ $~$ $x$ $x$ $x$

From this we can tell that $\mathcal R$ is,

  1. Reflective (the diagonal is filled)
  2. Symmetric (across the diagonal line)
  3. Equivalence Classed (Each 'square' of $x$'s is an equivalence class.

Example

Let $D = { \text{All binary strings of length } 5 }$ and $\mathcal T$ be the relation on $ D \times D$ defined by $x \mathcal T y $ the first $3$ digits of $x$ match $y$.

Solution