5.2 Congruence Classes

Equivalence relations

These three properties are the reflexivity, symmetry and transitivity axioms for an equivalence relation. Lemma 5.8 proves that for each fixed \(n\), congruence \(\text{mod }(n)\) is an equivalence relation on \({\mathbb Z}\).

A relation \(\sim\) between elements of some set \(X\) is said to be an equivalence relation if:

  • for every \(a\in X\), \(a\sim a\), (the relation is reflexive)
  • for every pair \(a,b\in X\), if \(a\sim b\) then \(b\sim a\) (the relation is symmetric),
  • for every triple \(a,b,c\in X\), if \(a\sim b\) and \(b\sim c\) then \(a\sim c\) (the relation is transitive).

So the congruence relation \(\equiv\) is an equivalence relation on \(\mathbb Z\).

Let \(f:X\to Y\) be any function. Consider the relation \[ x\sim y\text{ if and only if } f(x)=f(y). \] Then \(\sim\) is an equivalence relation on \(X\).

  • \(x\sim x\) as \(f(x)=f(x)\),
  • if \(x\sim y\) then \(f(x)=f(y)\) and so \(f(y)=f(x)\) i.e. \(y\sim x\),
  • if \(x\sim y\) and \(y\sim z\) then \(f(x)=f(y)\) and \(f(y)=f(z)\) and so \(f(x)=f(z)\) so that \(x\sim z\).

This particular equivalence relation is often referred to as the kernel of the function \(f\).

Partitioning a set

The point of an equivalence relation is to give a way of splitting a set up into subsets (pieces). Given any equivalence relation \(\sim\) on a set \(X\) we define subsets known as the equivalence classes as follows:

For each element \(x\in X\) let \([x]\) denote the subset \(\{y\in X\mid y\sim x\}\)

We will show that each equivalence class \([x]\) is a non-empty subset containing \(x\) itself and that if \([x]\cap [z]\ne\emptyset\) then \([x]=[z]\).

Notice that because \(x \sim x\), the equivalence class \([x]\) contains \(x\) itself. Now suppose that \([x]\cap[z]\ne\emptyset\). Then there is an element \(y\in [x]\cap [z]\). Since \(y\in [x]\), \(y\sim x\), and since \(y\in [z]\), \(y\sim z\). Since \(\sim\) is symmetric, it follows that \(z\sim y\) and \(x\sim y\). Since \(\sim\) is transitive, \(x\sim y\sim z\) implies that \(x\sim z\) so \(x\) also lies in \([z]\).

Now suppose that \(w\in [x]\). Then \(w\sim x\sim z\) implies that \(w\in [z]\). Since this works for ANY \(w\in [x]\) we see that \([x]\subseteq [z]\). Running this argument reversing the roles of \(x\) and \(z\) we can show that \([z]\subseteq[x]\). So \([z]=[x]\) as required.

So have demonstrated that \(X = \cup_{x\in X}{[x]}\) and that \(x \in [x]\) for all \(x\in X\).

A collection of subsets \(P = \{X_i\subseteq X|i\in I\}\) with the property that

is called a partition of the set \(X\).

Example 5.9

Let \(X\) be the set of vectors in \(\mathbb R^2\) and for \(u,v\in X\) define \(u\sim v\) to mean that \(u\) and \(v\) have the same length. Then it is clear that

  • \(u\sim u\) for all \(u \in X\);
  • if \(u\sim v\) then \(v\sim u\) for all \(u,v\in X\);
  • if \(u\sim v\) and \(v\sim w\) then \(u\sim w\), for all \(u,v,w\in X\).

Hence \(\sim\) is an equivalence relation on \(X\). Notice that the equivalence class \([(0,1)]\) consists of all vectors of length 1 and so is the unit circle in \(\mathbb R^2\).

Congruence classes

Since \(\equiv_n\) is an equivalence relation by Lemma 5.8, it follows that \({\mathbb Z}\) is partitioned into disjoint equivalence classes. We refer to these as congruence classes. \[{[a]=\{b\in{\mathbb Z}\mid b\equiv a\text{ mod }(n)\}}\] \[{=\{\;\ldots, a-2n, a-n, a, a+n, a+2n, \ldots\,\}}\] for \(a\in{\mathbb Z}\).

Each class corresponds to one of the \(n\) possible remainders \(r=0, 1, \ldots, n-1\) on division by \(n\), so there are \(n\) different congruence classes. They are \[[0]=\{\;\ldots, 2n, -n, 0, n, 2n, \ldots\,\}\] \[[1]=\{\;\ldots, 1-2n, 1-n, 1, 1+n, 1+2n, \ldots\,\}\] \[\vdots\] \[[n-1]=\{\;\ldots, -n-1, -1, n-1, 2n-1, 3n-1, \ldots\,\}\]

There are no further classes distinct from these. For example \[[n]=\{\;\ldots, -n, 0, n, 2n, 3n, \ldots\,\}=[0].\]

It should then be clear that the following important observation is then true. \[[a]=[b]\quad\text{if and only if}\quad a\equiv b\text{ mod }(n)\,.\]

So the following statements all mean the same thing and can be used interchangeably

Proposition 5.10

The following are equivalent:

  • \(a\equiv b\text{ mod }~(n)\),
  • \(a\) and \(b\) have the same remainder on division by \(n\),
  • \(n|(a-b)\),
  • \([a] = [b]\).

Notice that when \(n=1\) all integers are congruent to each other, so there is a single congruence class, coinciding with \({\mathbb Z}\). So we gain nothing in this case. For \(n=2\) the two classes \([0]=[0]_2\) and \([1]=[1]_2\) consist of the even and odd integers respectively.