CSCE 222 Lecture 15

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

Review: Relations

Reflexive

$\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})\rightarrow {}_{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 b\mod m\}$ 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{aligned}a-b=mc\rightarrow a\equiv b\mod m\\b-a=m(-c)\rightarrow b\equiv a\mod m\end{aligned}}$
3. transitive ${\begin{array}{rcl}a-b&\equiv &\mod m\\b-c&\equiv &0\mod m\\\hline 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 {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}\neq \emptyset$

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}\rightarrow {}_{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}\neq \emptyset$; so $[a]_{R}\cap [a]_{R}=[a]_{R}\cap [b]_{R}\neq \emptyset$.

(3) → (1)

Since $[a]_{R}\cap [b]_{R}\neq \emptyset$, 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}=\emptyset$) if $[a]_{R}\neq [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.