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 $\geq$ 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 is 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\sim 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 $\geq$ operator, we know that for any two integers $m,n\in Z$ exactly one of $m\geq 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\sim 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\sim _{R}b$ to denote that $a$ and $b$ are equivalent under $R$. If only one equivalence relation is under consideration, we can instead write simply $a\sim b$. As a notational convenience, we can simply say that $\sim$ is an equivalence relation on a set $X$ and let the rest be implied.

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 X$, 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 X$, 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}\implies {b\sim _{p}a}$ for all $a,b\in G$.
• Transitivity: For any $a,b,c\in X$, 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 together, we get ${(a-b)+(b-c)=(k_{1}p)+(k_{2}p)}\Leftrightarrow {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.

Equivalence classes

Let $\sim$ be an equivalence relation on $X$. Then, for any element $a\in X$ we define the equivalence class of $a$ as the subset $\left[a\right]\subseteq X$ given by

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

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

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

• We first prove that $\left[b\right]\subseteq \left[a\right]$. Let $p$ be an arbitrary element of $\left[b\right]$. Then $p\sim b$ by definition of the equivalence class, and $p\sim a$ by transitivity of equivalence relations. Thus, ${p\in \left[b\right]}\implies {p\in \left[a\right]}$ and $\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 definition $q\sim a$. By transitivity, $q\sim b$, so $q\in \left[b\right]$. Thus, ${q\in \left[a\right]}\implies {q\in \left[b\right]}$ and $\left[a\right]\subseteq \left[b\right]$.

As $\left[a\right]\subseteq \left[b\right]$ and as $\left[b\right]\subseteq \left[a\right]$, we have $\left[b\right]=\left[a\right]$.

Q.E.D.

Partitions of a set

A partition of a set $X$ is a disjoint family of sets $X_{i}$, $i\in I$, such that $\bigcup _{i\in I}X_{i}=X$.

Theorem: An equivalence relation $\sim$ on $X$ induces a unique partition of $X$, and likewise, a partition induces a unique equivalence relation on $X$, such that these are equivalent.

Proof: (Equivalence relation induces Partition): Let $P$ be the set of equivalence classes of $\sim$. Then, since $a\in [a]$ for each $a\in X$, $\cup P=X$. Furthermore, by the above theorem, this union is disjoint. Thus the set of equivalence relations of $\sim$ is a partition of $X$.

(Partition induces Equivalence relation): Let $X_{i}\,,\,i\in I$ be a partition of $X$. Then, define $\sim$ on $X$ such that $a\sim b$ if and only if both $a$ and $b$ are elements of the same $X_{i}$ for some $i\in I$. Reflexivity and symmetry of $\sim$ is immediate. For transitivity, if $a,b\in X_{i}$ and $b,c\in X_{i}$ for the same $i\in I$, we necessarily have $a,c\in X_{i}$, and transitivity follows. Thus, $\sim$ is an equivalence relation with $X_{i}\,,\,i\in I$ as the equivalence classes.

Lastly obtaining a partition $P$ from $\sim$ on $X$ and then obtaining an equivalence equation from $P$ obviously returns $\sim$ again, so $\sim$ and $P$ are equivalent structures.

Q.E.D.

Quotients

Let $\sim$ be an equivalence relation on a set $X$. Then, define the set $X/\sim$ as the set of all equivalence classes of $X$. In order to say anything interesting about this construction we need more theory yet to be developed. However, this is one of the most important constructions we have, and one that will be given much attention throughout the book.