quotient set A/R if R is an euqivalence relation on A A/R is a partition of A

Question

I am struggeling with figuring out how to stat with this proof. I understand how to go about this if I need to prove that R is a partition of A. But the quotient set is confusing me.

Prove that: IF $R$ is an equivalence relation on set $A$. Then A modulo R, $A/R = \{[x]_R|x\in A\}$, is a partition of A.

Any hints on how to get started would be appreciated!

Answer 1

You need to check 3 things:

1. The equivalence classes are non-empty.
2. The union of the set of equivalence classes is $A$.
3. The equivalence classes are mutually disjoint.

Now, to give a hint, compare the above three conditions you have to check with the definition of an equivalence relation on $A$:

1. $(x,x) \in R$ (reflexivity)
2. $(x,y) \in R \implies (y,x) \in R$ (symmetry)
3. $(x,y) \in R , (y,z) \in R \implies (x,z) \in R$ (transitivity)

Try to find a way to connect these three things together. Drawing a figure might help.

I will give you further hints, but do not read them unless you have tried the problem on your own: 1. Reflexivity tells you that the class of $a \in A$ contains $a$ itself. Therefore, you can find out why each class has to be non-empty and they should cover the whole set. 2. Transitivity tells you that if two different classes have something in common, they should coincide!

For the reverse direction, i.e. when you have been given a partition of a set $A$, you can define an equivalence relation on $A$. Just take your equivalence classes to be the partitioned sets themselves. Work out the details.

Now you should have a good understanding of partitioning a set and defining an equivalence relation on it. The two concepts are very similar and somehow equivalent. ;-)

Answer 2

If $R$ is an equivalence relation on set $A$, then $A$ modulo $R$, $A/R=\{[x]_R:x\in A\}$, is a partition of $A$.

$\textbf{Proof}$. The family $\{[x]_R:x\in A\}$ of sets does not contain the empty set since for each equivalence class $[x]_R$, $x\in [x]_R$. So each $[x]_R\not=\varnothing$.

Secondly, we need to show that $$ \bigcup_{x\in A} [x]_R = A. $$ The containment $\bigcup_{x\in A} [x]_R \subseteq A$ is clear since each set $[x]_R\subseteq A$. So we will show the other containment: $A \subseteq \bigcup_{x\in A} [x]_R$. Let $x\in A$. Then $x\in [x]_R$. So $x\in \bigcup_{x\in A}[x]_R$.

Lastly, suppose $x\not\sim_R y$ (so $x\not=y$). So $x\in [x]_R$ and $y\in [y]_R$. If $[x]_R\cap [y]_R\not=\varnothing$, then there exists an element $z\in [x]_R\cap [y]_R$. So $z\sim_R x$ and $z\sim_R y$. Since $\sim_R$ is an equivalence relation, $x\sim_R y$ by transitivity. This is a contradiction. So $$x\not\sim_R y \mbox{ implies }[x]_R\cap [y]_R = \varnothing. $$ So any two distinct equivalence classes are disjoint.

Thus, $A/R$ partitions the set $A$. $\square$