Chapter 6 Proofs Flashcards Preview

MAT 1362 > Chapter 6 Proofs > Flashcards

Flashcards in Chapter 6 Proofs Deck (3)
Loading flashcards...
1

Proposition 6.6

Suppose ∼ is an equivalence relation on a set A, and a, b ∈ A; then...

(i) a ∈ A

(ii) a ∼ b ⇔ [a] = [b]

(i) 

∼ is an equivalence relation
⇒ ∼ is reflexive
⇒ a ∼ a
⇒ a ∈ [a]

(ii)

let a ∼ b

let c ∈ [a] 
⇒ c ∼ a
⇒ c ∼ b
⇒ c ∈ b
⇒ [a] ⊆ [b]

let c ∈ [b]
⇒ c ∼ b
⇒ b ∼ a 
⇒ c ∼ a
⇒ c ∈ [a]
⇒ [b] ⊆ [a]

let [a] = [b]
⇒ a ∈ [a] = b
⇒ a ∈ [b]
⇒ a ∼ b

2

Proposition 6.7

Suppose ∼ is an equivalence relation on a set A; then, for all a, b ∈ A, we have...

[a] = [b] or [a] ∩ [b] = ∅ 

Suppose a, b ∈ A. 

If [a] ∩ [b] = ∅, we are done. So assume [a] ∩ [b] ̸= ∅.

Then there exists an element c ∈ [a] ∩ [b]. Thus, a ∼ c ∼ b, which implies that a ∼ b.

Therefore, by Proposition 6.6(ii), we have [a] = [b] . 

3

Proposition 6.10

(i) Suppose ∼ is an equivalence relation on A; then the set Π of equivalence classes of ∼ is partition of A.

(ii) Suppose Π is a partition of A; then the relation ∼ defined by a ∼ b ⇔ a and b lie in the same element of Π

(i)