Equivalence relations

Definition. $\sim$ is an equivalence relation on $A$ if:
- *Reflexive*: $\forall x\in A$, $x\sim x$;
- *Symmetric*: $\forall x,y\in A$, $x\sim y\Rightarrow y\sim x$;
- *Transitive*: $\forall x,y,z\in A$, $(x\sim y\land y\sim z)\Rightarrow x\sim z$.

Example. On $\mathbb{Z}$, $x\sim y\iff x-y$ is even.

Verification.
- Reflexive: $x-x=0$ is even.
- Symmetric: if $x-y$ even, then $y-x=-(x-y)$ even.
- Transitive: if $x-y$ and $y-z$ are even, then $x-z=(x-y)+(y-z)$ even.

Conclusion. Congruence mod $2$ (and more generally mod $n$) is an equivalence relation.