CSCE 222 Lecture 15

From Notes
Jump to navigation Jump to search

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


Review: Relations

Reflexive
Δ={(a,a)|a∈A}⊆R
Symmetric
R=R−1={(b,a)|(a,b)∈R}
Transitive
(aRb∧bRc)→aRc
Equivalence
reflexive, symmetric, and transitive


Equivalence Classes

Written as [x]R.

[a]R={b∈A|aRb}

Example

R={(a,b)|a≡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 a−b=mc→a≡bmodmb−a=m(−c)→b≡amodm
  3. transitive a−b≡modmb−c≡0modma−c=m(c+d)

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

[0]R={2m|m∈ℤ}

Theorem

Let R be an equivalence relation on a set A:

  1. aRb
  2. [a]R=[b]R
  3. [a]R∩[b]R≠∅

are equivalent properties


Proof

(1) → (2)

Suppose that aRb holds if c∈[a]R, then aRb. Since aRb→bRa, we have bRa and aRc by the transitive property, so c∈[b]R. Therefore, we have shown that [a]R⊆[b]R. By same token, [b]R⊆[a]R, so [a]R=[b]R

(2) → (3)

Since [a]R contains a, we have [a]R≠∅; so [a]R∩[a]R=[a]R∩[b]R≠∅.

(3) → (1)

Since [a]R∩[b]R≠∅, there exists an element c∈[a]R∩[b]R, so aRc and bRc holds. By symmetry, cRb holds. By transitivity, we can conclude from aRc and cRb that aRb holds.



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

⋃a∈R[a]R=A

Two equivalence classes are disjointed ([a]R∩[b]R=∅) if [a]R≠[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 {Ai|i∈I} on a set A, then there exists an equivalence relation R on A that has Ai, i∈I, as equivalence classes.