Problem 1.3. 1. Prove that if ? is an equivalence relation on a set S, then the

Question

Problem 1.3.
1. Prove that if ? is an equivalence relation on a set S, then the set of
equivalence classes of ? forms a partition of S. (Hint: To prove that if two equivalence
classes are not equal then they are disjoint, it is easier to show that if they are not
disjoint, then they must be equal. Make sure to explain why this is so.)

2. Let P be a partition of a set S, and define a relation ? on S by a ? b means there
is a set in P that contains both a and b. Prove that ? is an equivalence relation on
S, that is, prove that ? satisfies the above three properties.

Explanation / Answer

(Nothing to do with linear algebra, as you know.) An equiv relation on S is (a) reflexive ( x ~ x) (b) symmetric (if x ~ y then y ~ x) and transitive ( if x ~ y and y ~ z then x ~ z) Given a in S, define C(a) = { x : a ~ x}, the equivalence class of a. (1) If a ~ b then C(a) = C(b) For suppose x is in C(a). Then b ~ a ~ x so b ~ x . Therefore x is in C(b). Thus C(b) is contained in C(a). Similarly, C(a) is contained in C(b). (2) If C(a) n C(b) is non-empty then a ~ b For there is some y with a ~ y and also b ~ y , Then a ~ y ~ b so a ~ b (3) From (1) & (2), C(a) n C(b) is non-empty if & only if C(a) = C(b), if & only if a ~ b. Therefore S is the union of disjoint equivalence classes. Each class is some C(a_i) where no two of the a_i's are equivalent. help ful

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.