Abstract algebra/Equivalence relations and congruence classes

We often wish to describe how two mathematical entities within a set are related. For example, if we were to look at the set of all people on Earth, we could define "is a child of" as a relationship. Similarly, the $\ge$ operator defines a relation on the set of integers. Formally speaking, a relation is a binary proposition defined on two elements of a set, and is generally written with an infix operator. We will write $a\sim b$ for some $a,b\in G$ and for some relation $\sim$.

However, there are very many types of relations. Indeed, further inspection of our earlier examples reveals that the two relations are quite different. In the case of the "is a child of" relationship, we observe that there are some people A,B where neither A is a child of B, nor B is a child of A. In the case of the $\ge$ operator, we know that for any two integers $m,n\in Z$ exactly one of $m\ge n$ or $n>m$ is true. In order to learn anything about relations, we must look at a smaller class of relations.

In particular, we care about the following properties of relations:

• Reflexivity: $a\sim a$ for all $a\in G$.
• Symmetry: $a\sim b⟹b\sim a$ for all $a,b\in G$.
• Transitivity: $a\sim b\wedge b\sim c⟹a\sim c$ for all $a,b,c\in G$.

One should note that in all three of these properties, we quantify across _all_ elements of the set.

A total order relation which exhibits the properties of reflexivity, symmetry and transitivity is called an equivalence relation. Two elements related under an equivalence relation are called equivalent.

Example: For a fixed integer $p$, we define a relation ${\sim }_p$ on the set of integers such that $a{\sim }_{p}b$ if and only if $a-b=kp$ for some $k\in Z$. Prove that this defines an equivalence relation on the set of integers.

Proof:

• Reflexivity: For any $a\in G$, it follows immediately that $a-a=0=0p$, and thus $a{\sim }_{p}a$ for all $a\in G$.
• Symmetry: For any $a,b\in G$, assume that $a{\sim }_{p}b$. It must then be the case that $a-b=kp$ for some integer $k$, and $b-a=(-k)p$. Since $k$ is an integer, $-k$ must also be an integer. Thus, $a{\sim }_{p}b⟹b{\sim }_{p}a$ for all $a,b\in G$.
• Transivity: For any $a,b,c\in G$, assume that $a{\sim }_{p}b$ and $b{\sim }_{p}c$. Then $a-b=k_{1}p$ and $b-c=k_{2}p$ for some integers $k_1,k_2$. By adding these two equalities togeter, we get $(a-b)+(b-c)=(k_{1}p)+(k_{2}p)\iff a-c=(k_1+k_2)p$, and thus $a{\sim }_{p}c$

Q.E.D.

Remark. In elementary number theory we denote this relation $a\equiv b(\text{mod }p)$ and say a is equivalent to b modulo p.

Congruence classes (sometimes called equivalence classes) are partitionings of a set according to an equivalence relation. In other words, for any element $a\in G$ we define a subset $\left[a\right]\subseteq G$ as:

$\left[a\right]=\{b\in G|a\sim b\}$

Theorem: $b\in \left[a\right]⟹\left[b\right]=\left[a\right]$

Proof: Assume $b\in \left[a\right]$. Then, by construction $a\sim b$.

• [$\subseteq$]: Let $p$ be an arbitrary element of $\left[b\right]$. Then $p\sim b$ by construction of the equivalence class, and $p\sim a$ by transitivity of equivalence relations. Thus, $p\in \left[b\right]⟹p\in \left[a\right]$, or that $\left[b\right]\subseteq \left[a\right]$.
• [$\supseteq$]: Let $q$ be an arbitrary element of $\left[a\right]$. Then, by construction $q\sim a$. By transitivity, $q\sim b$, so $q\in \left[b\right]$. Thus, $q\in \left[a\right]⟹q\in \left[b\right]$, or that $\left[a\right]\subseteq \left[b\right]$.

As $\left[a\right]\subseteq \left[b\right]$ and as $\left[b\right]\subseteq \left[a\right]$, it must be the case that $\left[b\right]=\left[a\right]$.

Q.E.D.

Template:Incomplete