CSCE 222 Lecture 15

« previous | Monday, February 28, 2011 | next »

Review: Relations

Reflexive

$\mathrm{\Delta }=\{(a,a)|a\in A\}\subseteq R$

Symmetric

$R=R^{-1}=\{(b,a)|(a,b)\in R\}$

Transitive

$({}_a{R}_b\wedge {}_b{R}_c)\to {}_a{R}_c$

Equivalence

reflexive, symmetric, and transitive

Equivalence Classes

Written as $[x{]}_R$.

$[a{]}_R=\{b\in A|{}_a{R}_b\}$

Example

$R=\{(a,b)|a\equiv bmodm\}$ is an equivalence relation on the set of all integers:

in other words, the difference between $a$ and $b$ should be a multiple of $m$.

1. reflexive $a-a=mc=0$
2. symmetric $\begin{array}{r}a-b=mc\to a\equiv bmodm\\ b-a=m(-c)\to b\equiv amodm\end{array}$
3. transitive $\begin{array}{rcl}a-b& \equiv & modm\\ b-c& \equiv & 0modm\\ a-c& =& m(c+d)\end{array}$

For example, the congruence modulo 2 on the set of all integers:

$[0{]}_R=\{2m|m\in \mathbb{\mathbb{Z}}\}$

Theorem

Let $R$ be an equivalence relation on a set $A$:

1. ${}_a{R}_b$
2. $[a{]}_R=[b{]}_R$
3. $[a{]}_R\cap [b{]}_R\ne \mathrm{\varnothing }$

are equivalent properties

Proof

(1) → (2)

Suppose that ${}_a{R}_b$ holds if $c\in [a{]}_R$, then ${}_a{R}_b$. Since ${}_a{R}_b\to {}_b{R}_a$, we have ${}_b{R}_a$ and ${}_a{R}_c$ by the transitive property, so $c\in [b{]}_R$. Therefore, we have shown that $[a{]}_R\subseteq [b{]}_R$. By same token, $[b{]}_R\subseteq [a{]}_R$, so $[a{]}_R=[b{]}_R$

(2) → (3)

Since $[a{]}_R$ contains $a$, we have $[a{]}_R\ne \mathrm{\varnothing }$; so $[a{]}_R\cap [a{]}_R=[a{]}_R\cap [b{]}_R\ne \mathrm{\varnothing }$.

(3) → (1)

Since $[a{]}_R\cap [b{]}_R\ne \mathrm{\varnothing }$, there exists an element $c\in [a{]}_R\cap [b{]}_R$, so ${}_a{R}_c$ and ${}_b{R}_c$ holds. By symmetry, ${}_c{R}_b$ holds. By transitivity, we can conclude from ${}_a{R}_c$ and ${}_c{R}_b$ that ${}_a{R}_b$ holds.

---

Each element $a\in A$ is contained in an equivalence class of $R$, namely $[a]$:

$\bigcup _{a\in R}[a{]}_R=A$

Two equivalence classes are disjointed ($[a{]}_R\cap [b{]}_R=\mathrm{\varnothing }$) if $[a{]}_R\ne [b{]}_R$. Thus the equivalence classes of $R$ partition $A$.

Theorem

Let $R$ be an equivalence relation on $A$. Then the equivalence class of $R$ partitions $A$. Conversely, given a partition $\{A_i|i\in I\}$ on a set $A$, then there exists an equivalence relation $R$ on $A$ that has $A_i$, $i\in I$, as equivalence classes.