# Thread: Equivalence classes and relations.

1. ## Equivalence classes and relations.

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

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

1). Reflexivity $\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.

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

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

1). Reflexivity $\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 $[s_{1}]$and $[s_{2}]$ share and element x. then by definition $s_{1}Rx$ and $s_{2}Rx$ using the transitivity and symmetry properties you can show that $s_{1}Rs_{2}$. I'll leave you to prove that $s_{1}Rs_{2}$ iff $[s_{1}] = [s_{2}]$.

Bobak