CSCE 222 Lecture 15

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

Review: Relations

Reflexive

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle [a]_R \ne \emptyset} ; so Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle [a]_R \cap [a]_R = [a]_R \cap [b]_R \ne \emptyset} .

(3) → (1)

Since Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle [a]_R \cap [b]_R \ne \emptyset} , there exists an element Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle c \in [a]_R \cap [b]_R} , so Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle {}_aR_c} and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle {}_bR_c} holds. By symmetry, Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle {}_cR_b} holds. By transitivity, we can conclude from Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle {}_aR_c} and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle {}_cR_b} that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle {}_aR_b} holds.

---

Each element Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a \in A} is contained in an equivalence class of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle R} , namely Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle [a]} :

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \bigcup_{a\in R} [a]_R = A}

Two equivalence classes are disjointed (Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle [a]_R \cap [b]_R = \emptyset} ) if Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle [a]_R \ne [b]_R} . Thus the equivalence classes of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle R} partition Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A} .

Theorem

Let Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle R} be an equivalence relation on Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A} . Then the equivalence class of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle R} partitions Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A} . Conversely, given a partition Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \{A_i ~|~ i \in I\}} on a set Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A} , then there exists an equivalence relation Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle R} on Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A} that has Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A_i} , Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle i \in I} , as equivalence classes.