Proving that the quotient of a set by an equivalent relation is a partition

213 Views Asked by At

I need to show that the quotient of a set $S$ with respect to the equivalence relation $\sim$ is a partition of $S$.

To show this, we will denote the quotient by $P_\sim.$ Note that $$ P_\sim = \{[a]_\sim \mid a\in S\}$$ where $[a]_\sim = \{b\in S \mid b\sim a\}$.

First, we will show that each element of $P_\sim$ is nonempty. So let $x\in P_\sim,$ then there exists some $a \in S$ such that $x = [a]_\sim.$ Since $\sim$ is an equivalence relation, it follows that it is reflexive thus $a \sim a$ hence $a \in [a]_\sim$ so $[a]_\sim$ is nonempty thus $x$ is nonempty.

Second, we will show that any two elements of $P_\sim$ are disjoint. So let $x, y \in P_\sim$ such that $x \not= y.$ We will show that $x \cap y = \emptyset.$ By definition, there exist $a,b \in S$ such that $x = [a]_\sim, y = [b]_\sim.$

Now, suppose, for the sake of contradiction, that there exists some $z \in S$ such that $z \in x\cap y, $ that is, $ z \in [a]_\sim \cap [b]_\sim.$ Hence $z\sim a$ and $z\sim b$. By symmetry of $\sim,$ we have $b\sim z$. As $b\sim z$ and $z \sim a$, we have $b\sim a$. We will show that $[a]_\sim = [b]_\sim.$ Suppose that $c \in [b]_\sim$ arbitrary. Then, as $b \sim a,$ we have $c \sim a$ so $c \in [a]_\sim$ thus $[b]_\sim \subseteq [a]_\sim .$

Similarly, suppose $d \in [a]_\sim$. By symmetry of $\sim, b\sim a$ implies $a \sim b.$ As $d\sim a$ and $a\sim b,$ we have $d\sim b$ so $d \in [b]_\sim$ thus $[a]_\sim \subseteq [b]_\sim.$ Therefore $[a]_\sim = [b]_\sim $ which is equivalent to $x = y$ which is a contradiction. Hence $x \cap y = \emptyset$.

Finally, we will show that $$\bigcup_{r\in P_\sim} r = S.$$ Suppose first, that $y \in \bigcup_{r\in P_\sim}{r}.$ Then there exists some $x \in P_\sim$ such that $y \in x.$ Consequently, there exists $a \in S$ such that $y \in [a]_\sim.$ Thus $y \in S$ and $y\sim a$ which leads to $y \in S.$ As $y$ was arbitrary, it follows that $$\bigcup_{r\in P_\sim} r \subseteq S.$$ Next, suppose $y \in S.$ Then, by the reflexivity of $\sim,$ we have $y\sim y$ so $y \in [y]_\sim.$ By definition, $[y]_\sim \in P_\sim$ thus $y \in \bigcup_{r\in P_\sim}r $. As $y$ was arbitrary, it follows that $$S \subseteq \bigcup_{r\in P_\sim} r.$$ Therefore, $$\bigcup_{r\in P_\sim} r = S.$$ We have thus shown that $P_\sim$ forms a partition of $S.$

Please see if this proof looks correct and suggest ways to improve my writing of the same.

1

There are 1 best solutions below

2
On BEST ANSWER

Your proof is okay and cannot be improved. However I cannot resist the temptation to give you a proof that is a bit more concise.


If $[a]:=\{x\in S\mid x\sim a\}$ then by reflexivity of $\sim$ we find that $a\in[a]$. So elements of $\mathcal P$ are not empty and secondly we find that for every element $a\in S$ we have $a\in[a]\in\mathcal P$.

Now it only remains to show that we have $[a]=[b]$ or $[a]\cap[b]=\varnothing$ for every pair $[a],[b]\in\mathcal P$.

If $b\in[a]$ or equivalently $b\sim a$ then by transitivity it follows that $[b]\subseteq[a]$. Moreover by symmetry we also have $a\sim b$ and consequently $[a]\subseteq[b]$ so that we can conclude that $b\in[a]\implies[b]=[a]$.

So if $x\in[a]\cap[b]$ then $[a]=[x]=[b]$.

Now we are ready.