Let $M\neq \emptyset$ be a set and let $\mathcal{P}\subseteq 2^M$ such that the following axioms are satisfied:
- $\emptyset\notin \mathcal{P}$
- $\displaystyle{\bigcup_{P\in \mathcal{P}}P=M}$
- $\forall P,Q\in \mathcal{P}: (P\cap Q\neq \emptyset\Rightarrow P=Q)$
(i) Show that for $x\in M$ there is an unique set $[x]\in \mathcal{P}$ such that $x\in [x]$.
(ii) We define a relation on $M$ as $x\sim y:\iff [x]=[y]$. Show that $\sim$ is an equivalence relation.
$$$$
I have done the following:
(i) We assume that the is not an unique set that contains $x$, i.e. there are $[x],[y]\in\mathcal{P}$ with $[x]\neq [y]$ and $x\in [x]$ and $x\in [y]$. Then the intersection of $[x]$ and $[y]$ is non-empty and from the 3rd axiom we get that $[x]=[y]$, a contradiction.
Therefore there must be a unique set of $\mathcal{P}$ that contains $x$.
Is the proof correct?
(ii) For that we have to show that the relation is reflexive, symmetric and transitive.
Reflexivity:
Let $x \in M$. Then it holds, trivially, that $[x]=[x]$. Therefore $x\sim x$. So $\sim$ is reflexive.
Symmetry:
Let $x,y \in M$ and $x\sim y$. Then $[x]=[y]$. Equivalently it holds that $[y]=[x]$ and therefore $y \sim x$. So $\sim$ is symmetric.
Transitivity:
Let $x,y,z\in M$ and $x\sim y$ and $y\sim z$. Then it holds that $[x]=[y]$ and $[y]=[z]$. So we have that $[x]=[y]=[z]$, so $[x]=[z]$ and therefore $x\sim z$. So $\sim$ is transitive.
Is everything correct and complete? Or do we have to justify each property with more details, i.e. using the definition of $[x]$ ?
Your work looks good. To extend your understanding of partitions and equivalence relations prove the following theorem.
There is a bijection between the partitions of a set and equivalence relations of that set, such that the sets of the partition are the equivalence classes of the equivalence relation.