Equivalence classes and relations.

• Dec 15th 2008, 04:21 AM
Showcase_22
Equivalence classes and relations.
Quote:

Prove that an equivalence relation can on a set S uniquely defines a partition of that set.
Suppose S can be separated into $\displaystyle A_1, A_2,.......,A_n$ partitions.

Hence $\displaystyle A_1 \cup A_2 \cup........\cup A_n=S$. Assume that reflexivity, symmetry and transitivity hold.

1). Reflexivity $\displaystyle \Rightarrow A_1 \cap A_i=\phi$ since an element from one subset cannot belong to another subset (property 2 of a partition- the intersections are empty).

This is where I have no idea where to go. Symmetry and transitivity I cannot connect to the definition of a partition.

I was wondering if this is the right idea to follow.
• Dec 15th 2008, 06:28 AM
bobak
Quote:

Originally Posted by Showcase_22
Suppose S can be separated into $\displaystyle A_1, A_2,.......,A_n$ partitions.

Hence $\displaystyle A_1 \cup A_2 \cup........\cup A_n=S$. Assume that reflexivity, symmetry and transitivity hold.

1). Reflexivity $\displaystyle \Rightarrow A_1 \cap A_i=\phi$ since an element from one subset cannot belong to another subset (property 2 of a partition- the intersections are empty).

This is where I have no idea where to go. Symmetry and transitivity I cannot connect to the definition of a partition.

I was wondering if this is the right idea to follow.

This is not a proof. I'll give you an outline or a proof. you want to prove (i) that all element in S belong to an equivalence class and (ii) that any two equivalence classes are either disjoint or equal and that once you have proved these two properties your pretty much done.

i) is trivial using the reflexive property.

ii) first suppose$\displaystyle [s_{1}]$and $\displaystyle [s_{2}]$ share and element x. then by definition $\displaystyle s_{1}Rx$ and $\displaystyle s_{2}Rx$ using the transitivity and symmetry properties you can show that $\displaystyle s_{1}Rs_{2}$. I'll leave you to prove that $\displaystyle s_{1}Rs_{2}$ iff $\displaystyle [s_{1}] = [s_{2}]$.

Bobak