Chapter 6 Proofs

Question 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]

Answer 1

(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

Question 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] = ∅

Answer 2

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] .

Question 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 Π

Answer 3

(i)