Proof verification: Show that the set of congruence classes form a partition of $\mathbb{Z}$. Can someone let me know if my proof is logically correct? :)
Proof: Assume that there exists a congruence relation $\equiv$ on a set $\mathbb{Z}$. Since the relation is reflexive, $x\equiv x$ (mod n) for all $x \in \mathbb{Z}$, and so $x \in [x]_{n}$. Therefore, $[x]_{n}$ is nonempty and for all $x \in \mathbb{Z}$, $\mathbb{Z}= \bigcup _{x\in \mathbb{Z}} [x]_{n}$ (note that this is all my professor asks for me to say when it comes to the union part of the proof). Since $[x]_{n}$ is nonempty for all $x \in \mathbb{Z}$, it remains to be shown that for any two $x, y \in \mathbb{Z}$, either $[x]_{n} = [y]_{n}$ or $[x]_{n} \cap [y]_{n} = \varnothing$ (no two elements in $\mathbb{Z}$ are in the same congruence class unless the elements are equal (?)). Assume $[x]_{n} \cap [y]_{n} \neq \varnothing$ and let $z \in [x]_{n} \cap [y]_{n}$. Then $z\equiv x$ (mod n) and $z\equiv y$ (mod n). Then $x\equiv z$ (mod n) and $z\equiv y$ (mod n) by symmetry. Then $x\equiv y$ by transitivity. Then $[x]_{n} \subset [y]_{n}$. Similarly, $y\equiv z$ (mod n) and $z\equiv x$ (mod n) by symmetry and $y\equiv x$ (mod n) by transitivity. Then $[y]_{n} \subset [x]_{n}$. By the definition of set equality, $[x]_{n} = [y]_{n}$. Therefore, any two congruence classes are either disjoint or equal. Therefore, the congruence classes of each element in $\mathbb{Z}$ form a partition of $\mathbb{Z}$.
 A: Ok so it appears that you have some of the basic ideas that are essential to such an argument, but your proof needs a little more direction.  What is sufficient is to show that $\equiv$ is an equivalence relation on $\mathbb{Z}$, as an equivalence relation on ANY set forms a partition of that set into equivalence classes.  Thus you need to show that the following three properties are satisfied:  $$\begin{align*} \text{(reflexivity)}: x &\equiv x \quad \forall x\in \mathbb{Z} \\
\text{(symmetry)}: x &\equiv y \implies y \equiv x \quad \forall x,y \in \mathbb{Z} \\
\text{(transivity)}: x &\equiv y \text{ and } y \equiv z \implies x \equiv z \quad \forall x,y,z \in \mathbb{Z}
\end{align*}$$
These three characteristic properties are what define an equivalence relation.  This is a fundamental definition that is worth remembering as a student.
A: I think you have it.  One small correction : the statement " (no two elements in ZZ are in the same congruence class unless the elements are equal (?)" is off.  Wait, I take that back. ..  To make it clearer though,  I think you should say, "... unless the "classes" are the same. ..  What preceded it was correct though,  and I believe it's what you proceeded to prove. ..  namely,  any two classes are the same class, or else disjoint. ..
A: The OP's proof appears to be correct, but the justification of
$\tag 1 x\equiv y \implies [x]_{n} \subset [y]_{n}$
$\tag 2 y\equiv x \implies [y]_{n} \subset [x]_{n}$
is just assumed. Perhaps this was proved in class.
There is another way to show that sets $[x]_{n}$ form a partition, using a standard notation:
Lemma 1: $[x]_{n} = x + n\mathbb Z$.
The proof of lemma 1 is left as an exercise.
Since $x = x + n 0$, $x \in [x]_{n}$ and so each $[x]_{n}$ in nonempty and $\mathbb Z \subset \bigcup \, [x]_{n}$.
Lemma 2: If $z \in [x]_{n}$ then $[z]_{n} = [x]_{n}$.
Proof
We have $z = x + nk$. So $z + n\mathbb Z = (x+nk) +n\mathbb Z$. But then
$\quad [z]_{n} = $
$\quad (x + nk) + n\mathbb Z =$
$\quad (x + nk) + \{\dots,-n(k+2),-n(k+1),-nk,-n(k-1),-n(k-2),\dots\}=$
$\quad \{\dots,x+n(-2),x+n(-1),x+n(0),x+n(+1),x+n(+2),\dots\}=$
$\quad x + n\mathbb Z =$
$\quad [x]_{n} $.
Alternate Proof
We have $z = x + nk$.
If $y \in [z]_{n}$ then $y = z + nj = (x+nk) + nj = x + (k+j)n$, so $y \in [x]_{n}$. Thus $[z]_{n} \subset [x]_{n}$.
If $y \in [x]_{n}$ then $y = x + nh$. If we can solve $y = z + gn$ for $g$, then $[x]_{n} \subset [z]_{n}$ and the proof will be finished. But
$\quad y = z + gn \text{ iff }$
$\quad x + nh = x + nk + gn \text{ iff }$
$\quad nh = nk + gn \text{ iff }$
$\quad g = h - k$  $\quad \blacksquare$
Lemma 3: If $z \in [x]_{n}$ and $z \in [y]_{n}$ then $[x]_{n} = [y]_{n}$.
Proof
Follows immediately from lemma 2. $\quad \blacksquare$
Lemma 3 of course completes the proof that the congruence classes partition $\mathbb Z$.
