Definition 3. A collection P of nonempty subsets of a nonempty set S forms a par

Question

Definition 3. A collection P of nonempty subsets of a nonempty set S forms a partition of
S provided

1. S is the union of the sets in P and

2. If A and B are in P and A = B, then A ? B = ?, that is, the intersection of the
sets A and B is empty.

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

1) Denoting equivalence classes as [a] for some a in S, Union of all [a]'s clearly is equal to S. Claim: [a] and [b] are either disjoint or equal. If they are not disjoint, then there exists c in both [a] and [b] which means a~c and b~c. Due to transitivity, this means any element related to a is also related to b via c and vice versa. Hence [a]=[b] Thus S is the union of [a]'s (equivalence classes) which are also disjoint. Thus the equivalence classes constitute a partition of S. 2) Given a partition of S, Define ~ on S as a~b IFF they are both in the same set A a~a, a~b implies b~a and a~b and b~c implies a~c. Thus ~ is an equivalence relation.

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

---

---

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