What are equivalent relations, partitions and congruence classes?

Question

My teacher's notes:

"For any $n\geq1$, "congruent mod $n$" defines an equivalent relation on $\Bbb{Z}$ and therefore, partition $\Bbb{Z}$ into $n$ different congruences classes"

What does any of that mean?

Answer 1

Correction: it should say "defines an equivalence relation on $\mathbb{Z}$". The background knowledge used here is:

• Equivalence relations. A binary relation $R$ on a set $X$ is an equivalence if it satisfies the following properties:
  • Reflexivity: $xRx$ for all $x\in X$
  • Symmetry: if $xRy$ for some $x,y\in X$, then also $yRx$.
  • Transitivity: if $xRy$ and $yRz$ for some $x,y,z\in X$, then also $xRz$.
• Equivalence classes: if you have an equivalence relation $R$ on a set $X$, this relation partitions the set $X$ into subsets ("equivalence classes") such that, within each subset, all elements are in relation to each other, and no two elements from different subsets are in relation with each other.
  • One way to see that is to look at the sets $R_x=\{y\in X : xRy\}$, for every $x\in X$. Those sets are either disjoint, or they are one and the same set - can be proven easily using the properties of the equivalence relation - and because $x\in R_x$ for all $x\in X$, they cover the whole $X$.

Now, armed with that knowledge... I presume your teacher has proven that the relation "congruent mod $n$" on $\mathbb Z$ is an equivalence relation. It immediately follows that $\mathbb Z$ is partitioned into equivalence classes, which (speaking of congruences) we can call "congruence classes modulo $n$".

Example: $n=5$. The relation on $\mathbb Z$ is $x\equiv y\mod 5$, and so the congruence classes are the following five subsets:

• $\{\ldots,-10, -5, 0, 5, 10,\ldots\}$
• $\{\ldots,-9, -4, 1, 6, 11,\ldots\}$
• $\{\ldots,-8, -3, 2, 7, 12,\ldots\}$
• $\{\ldots,-7, -2, 3, 8, 13,\ldots\}$
• $\{\ldots,-6, -1, 4, 9, 14,\ldots\}$

Any two numbers from each set are congruent (modulo $5$) and there aren't two numbers from different sets that are congruent (modulo $5$).

Answer 2

An equivalence relation $R$ on a set $S$ means that for $x,y,z \in S$ that $xRy \implies yRx$, $xRx$ for all $x$ and if $xRy$ and $yRz$ then $xRz$.

A partition of a set is a collection of subsets of the set that have no elements in common with any other subset and every element of the set is in one of the subsets. You can think of this as organizing the elements of the set into different groups with no groups having any common element.

By the fundamental theorem of equivalence relations every partition is an equivalence relation and every equivalence relation is a partition. I would argue this is the most important theorem in modern mathematics and is the workhorse of many results in algebra, topology and analysis.

Because of this we sometimes give a special label to the partitions induced by the equivalence relation and in this case they're being called congruence classes. This will generalize to the idea of a coset in an algebraic group.