Let R be an equivalence relation on a set A.

Chapter 8, Problem 40E

(choose chapter or problem)

Problem 40E

Let R be an equivalence relation on a set A. Prove each of the statements.directly from the definitions of equivalence relation and equivalence class without using the results of Lemma 8.3.2, Lemma 8.3.3, or Theorem.

Theorem

Suppose A is a set and R is an equivalence relation on A. For notational simplicity, we assume that R has only a finite number of distinct equivalence classes, which we denote A1, A2,…An,

where n is a positive integer. (When the number of classes is infinite, the proof is identical except for notation.)

Proof that A = A1 ∪ A2∪ …∪ An: [We must show that A ⊆ A1 ∪ A2 ∪ ・ ・ ・ ∪ An and that A1 ∪ A2 ∪… ∪ An ⊆ A.]

To show that A ⊆ A1 ∪ A2 ∪… ∪ An, suppose x is any element of A. [We must show that x ∈ A1 ∪ A2 ∪…∪ An.] By reflexivity of R,x R x. But this implies that x ∈ [x] by definition of class. Since x is in some equivalence class, it must be in one of the distinct equivalence classes A1, A2, …or An. Thus x ∈ Ai for some index i , and hence x ∈ A1 ∪ A2 ∪…∪ An by definition of union [as was to be shown].

To show that A1 ∪ A2 ∪…∪ An ⊆ A, suppose x ∈ A1 ∪ A2 ∪…∪ An. [We must show that x ∈ A.] Then x ∈ Ai for some i = 1, 2…n, by definition of union.

But each Ai is an equivalence class of R. And equivalence classes are subsets of A. Hence Ai ⊆ A and so x ∈ A [as was to be shown].

Since A ⊆ A1 ∪ A2 ∪… ∪ An and A1 ∪ A2 ∪…∪ An ⊆ A, then by definition of set equality, A = A1 ∪ A2 ∪…∪ An.

Proof that the distinct classes of R are mutually disjoint: Suppose that Ai and Aj are any two distinct equivalence classes of R. [We must show that Ai and Aj are disjoint.] Since Ai and Aj are distinct, then Ai ≠ Aj . And since Ai and Aj are equivalence classes of R, there must exist elements a and b in A such that Ai = [a] and Aj= [b]. By Lemma 8.3.3,

either

But [a] ≠[b] because Ai ≠Aj . Hence [a] ∩ [b] = . Thus Ai ∩ Aj = ,and so Ai and Aj are disjoint [as was to be shown].

Exercise

For all a, b, and x in A, if a R b and x ∈[a] then x ∈[b].