equivalence relations proof over the same set

37 Views Asked by At

I want to proof the following theorem:

Let R be an equivalence relation on set A. Then {R[a]:a that belongs to A} is a partition of A.

So long I have manage to proof that each a that belongs to A, it belong to the partition (by using reflexive property); and that if S and T belongs to a partition then S=T (by using symmetry and transitive property). The part that I cannot prove is the partition property that says:

If S and T are partitions then S intersection T is equals to the empty set.

How can I prove that?

1

There are 1 best solutions below

0
On

We can prove the third property by contradiction. Let $P = \{R[a] \mid a \in A\}$.

Let $R[a]$ and $R[b]$ be distinct sets in $P$ and suppose $\exists\; x \in A$ with $x \in R[a]$ and $x \in R[b]$.

Then $aRx$ and $xRb$. By transitivity and symmetry, $aRb$ and $bRa$.

Therefore, for any $y \in R[a],\; yRa$ so by transitivity, $yRb$ and so $y \in R[b]$.

Similarly, for any $z \in R[b],\; zRb$ so by transitivity, $zRa$ and so $z \in R[a]$.

This contradicts that $R[a]$ and $R[b]$ are distinct sets. So there cannot be such an $x$. Therefore, $R[a]$ and $R[b]$ are disjoint, as the third property requires.

For your first two properties, you might want to compare them against the three properties here to make sure you have them right.