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. A binary relation, hereafter referred to simply as a relation, is a binary proposition defined on any selection of the elements of two sets.

Formally, a relation is any arbitrary subset of the Cartesian product between two sets X and Y so that, for a relation R, $R \subseteq X \times Y$. In this case, X is referred to as the domain of the relation and Y is referred to as its codomain. If an ordered pair (x,y) is an element of R (where, by the definition of R, $x \in X$ and $y \in Y$), then we say that x is related to y by R. We will use R(x) to denote the set

$\{y \in Y:(x, y) \in R\}$.

In other words, R(x) is used to denote the set of all elements in the codomain of R to which some x in the domain in related.

Equivalence relations

To denote that two elements x and y are related for a relation R which is a subset of some Cartesian product $X \times X$, we will use an infix operator. We write x∼y for some $x,y\in X$ and $(x, y) \in R$.

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 about relations, we must look at a smaller class of relations.

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

• Reflexivity: A relation $R \subseteq X \times X$ is reflexive if a∼a for all $a\in X$.
• Symmetry: A relation $R \subseteq X \times X$ is symmetric if ${a \sim b} \implies {b \sim a}$ for all $a,b \in X$.
• Transitivity: A relation $R \subseteq X \times X$ is transitive if ${ {a \sim b} \wedge {b \sim c} } \implies { a \sim c }$ for all $a,b,c \in X$.

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

Any relation $R \subseteq X \times X$ which exhibits the properties of reflexivity, symmetry and transitivity is called an equivalence relation on X. Two elements related by an equivalence relation are called equivalent under the equivalence relation. We write $a \equiv b (R)$ to denote that a and b are equivalent under R. If only one equivalence relation is under consideration, we can instead write simply $a \equiv b$.

Example: For a fixed integer p, we define a relation ∼_p on the set of integers such that a∼_pb 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 X$, it follows immediately that a − a = 0 = 0p, and thus a∼_pa for all $a\in G$.
• Symmetry: For any $a,b \in X$, assume that a∼_pb. 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 }\implies {b \sim_p a}$ for all $a,b\in G$.
• Transitivity: For any $a,b,c\in X$, assume that a∼_pb and b∼_pc. Then a − b = k₁p and b − c = k₂p for some integers k₁,k₂. By adding these two equalities together, we get ${(a-b)+(b-c)=(k_1 p) + (k_2 p)} \Leftrightarrow {a-c = (k_1 + k_2) p}$, and thus a∼_pc.

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

Congruence classes, also called equivalence classes, are partitionings of a set according to some equivalence relation $R \subseteq X \times X$. In other words, for any element $a\in X$ we define a subset $\left[ a \right]\subseteq X$ as:

$\left[ a \right] = \left \{ b \in X | a \equiv b (R)\right \}$

We refer to this as the R-equivalence class of a.

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

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

• We first prove that $\left[b\right] \subseteq \left[a\right]$. Let p be an arbitrary element of $\left[ b \right]$. Then $p\equiv b$ by construction of the equivalence class, and $p\equiv a$ by transitivity of equivalence relations. Thus, ${p\in\left[b\right]}\implies {p\in\left[a\right]}\implies\left[b\right] \subseteq \left[a\right]$.
• We now prove that $\left[a\right] \subseteq \left[b\right]$ Let q be an arbitrary element of $\left[ a \right]$. Then, by construction $q\equiv a$. By transitivity, $q\equiv b$, so $q\in\left[ b\right]$. Thus, ${q\in\left[a\right]}\implies {q\in\left[b\right]}\implies\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. The text in its current form is incomplete.