0
$\begingroup$

Prove that

The distinct equivalence classes if an equivalence relation on $A$ provide us with a decomposition of $A$ as a union of mutually disjoint subsets. Conversely, given decomposition of $A$ as a union of mutually disjoint, non empty subsets, we can define an equivalence relation on $A$ for which these subsets are the distinct equivalence classes.

I need help with the converse part!!

  • 2
    The relation is $x \equiv y$ if and only if $x$ and $y$ belong to the same subset.2012-12-17

1 Answers 1

1

Suppose that $\mathscr{P}$ is a partition of the set $A$, i.e., a collection of pairwise disjoint, non-empty subsets of $A$ whose union is $A$. Define a relation $\sim$ on $A$ as follows: for $a,b\in A$, $a\sim b$ if and only if there is a $P\in\mathscr{P}$ such that $a,b\in P$. In other words, $a\sim b$ if and only if $a$ and $b$ are in the same ‘piece’ of the partition $\mathscr{P}$. Now you have to verify that $\sim$ is an equivalence relation, so you have to check that it’s reflexive, symmetric, and transitive.

  • Reflexive: Let $a\in A$; $\bigcup_{P\in\mathscr{P}}P=A$, so there is some $P\in\mathscr{P}$ such that $a\in P$. Clearly both $a$ and $a$ (!) are in $P$, so $a\sim a$.

  • Symmetric: Let $a,b\in A$, and suppose that $a\sim b$. Then there is a $P\in\mathscr{P}$ such that $a,b\in P$. You want to show that $b\sim a$, so you want to show that there is a $P'\in\mathscr{P}$ such that $b,a\in P'$; what’s the obviously successful choice for $P'$?

  • Transitive: Let $a,b,c\in A$, and suppose that $a\sim b$ and $b\sim c$; you need to show that $a\sim c$. I think that I’ve done enough to give you a pretty good idea of how to tackle this, so I’ll leave it to you, but feel free to leave a comment if you get stuck.