18.4: Important examples

Example \(\PageIndex{1}\): Equality is the strongest form of equivalence.

The “strongest” equivalence relation on a set \(A\) is the identity relation, where \(a \equiv b\) if and only if \(a = b\text{.}\) In this case, each equivalence class is a singleton: \([a] = \{a\}\) for each \(a \in A\text{.}\) This equivalence relation yields the “finest” or most “granular” partition of \(A\text{,}\) into the union of all the singleton sets in \(\mathscr{P}(A)\text{.}\) Here, the quotient \(A/\equiv\) is essentially the same as \(A\text{:}\) the natural projection \(A \to (A/\equiv)\) is a bijection.

Example \(\PageIndex{2}\): Even and odd.

We can partition \(\mathbb{N}\) into the subsets of even and odd numbers. This is the same partition obtained from the modulo-\(2\) equivalance relation \(\mathord{\equiv}_2\text{,}\) and we have quotient

\begin{equation*} (\mathbb{N} / \mathord{\equiv}_2) = \{ [0], [1] \} \text{.} \end{equation*}
This quotient is how we construct boolean algebra (see Chapter 3). The convention \(1 + 1 = 0 \) in boolean algebra comes from defining addition in the quotient so that

\begin{equation*} [1] + [1] = [1 + 1] = [2] = [0] \text{.} \end{equation*}

Example \(\PageIndex{3}\): Modulo-\(n\) arithmetic.

Similarly to Example 18.4.2, if we consider the modulo-\(n\) equivalence relation \(\mathord{\equiv}_n\) on \(\mathbb{N}\text{,}\) we have

\begin{equation*} (\mathbb{N} / \mathord{\equiv}_n) = \{ [0], [1], [2], \ldots, [n-1] \} \text{.} \end{equation*}
We can transfer the arithmetic of \(\mathbb{N}\) to \(\mathbb{N} / \mathord{\equiv}_n\) by defining

\begin{align*} [m] + [n] & = [m + n] \text{,} & [m] \cdot [n] & = [m n \text{.} \end{align*}
For example, in modulo-\(5\) arithmetic,

\begin{equation*} [2] + [4] = [6] = [1] \end{equation*}
and

\begin{equation*} [2] \cdot [4] = [8] = [3] \text{.} \end{equation*}

Checkpoint \(\PageIndex{1}\) (Bonus content) Properties of modulo-\(n\) arithmetic.

There are a few things to check about this new modulo-\(n\) arithmetic.

Check that modulo-\(n\) addition and multiplication are well-defined; that is, make sure the result of each of these operations never depends on the choices of representatives of the equivalence classes involved.

Check that modulo-\(n\) addition and multiplication satisfy all the usual rules of arithmetic. That is, check that modulo-\(n\) addition and multiplication are both associative and commutative, and that multiplication distributes over addition.

The natural numbers \(0\) and \(1\) play special roles in \(\mathbb{N}\) with respect to ordinary addition and multiplication, respectively. Do their equivalence classes \([0]\) and \([1]\) play the same special roles in \(\mathbb{N} / \mathrel{\equiv}_n\) with respect to modulo-\(n\) addition and multiplication, respectively?

Example \(\PageIndex{4}\): Same image under a function.

For a function \(f: A \rightarrow B\text{,}\) we may consider elements of the domain equivalent if they produce the same output under \(f\text{.}\) That is, the relation \(\mathord{\equiv}_f\) on \(A\) defined by “\(a_1 \equiv_f a_2\) means \(f(a_1) = f(a_2)\)” is an equivalence relation.

Checkpoint \(\PageIndex{2}\): Classes of the “same image” relation for an injective function.

Suppose \(f: A \rightarrow B\) is a function, and consider the equivalence relation \(\mathord{\equiv}_f\) on \(A\) described in Example 18.4.5. How could one tell whether or not \(f\) is injective by looking at the equivalence classes in \(A\) under \(\mathord{\equiv}_f\text{?}\)

Example \(\PageIndex{1}\): Inverting a non-injective function.

Equivalence relations allow us to take another point of view of the concept of inverse image of an element from Section 10.5.

Suppose \(f: A \rightarrow B\text{,}\) and consider the equivalence relation \(\mathord{\equiv}\) on \(A\) described in Example 18.4.5. Then we may create a new, “induced” function

\begin{align*} \tilde{f} \colon (A / \equiv) & \to B, \\ [a] & \mapsto f(a). \end{align*}

Figure 18.4.8. Diagram illustrating the induced map \(\tilde{f}\text{.}\)
In this function definition, an entire equivalence class is being mapped to the output image of one of the elements of that class under the original function \(f\text{.}\) But under this equivalence relation, each element in a specific equivalence class shares the same output image in the codomain as all the other elements in that class. For this reason, allowing our input-output rule definition \(\tilde{f}([a]) = f(a)\) to depend on the choice of class representative \(a\) is well-defined, and hence is a function.

See.

Example 10.1.13.

Moreover, the induced function \(\tilde{f}\) is always injective, even if \(f\) is not. If we assume that \(f\) is surjective (or, if \(f\) is not surjective we could replace our codomain \(B\) with the image set \(f(A)\) so that \(f\) is surjective — see restricting the domain), then \(\tilde{f}\) will also be surjective, hence bijective. This means that \(\tilde{f}\) is invertible, with inverse

\begin{align*} \tilde{f}^{-1} \colon B & \to (A / \mathord{\equiv}_f), \\ b & \mapsto \{a\in A \vert f(a) = b \} = f^{-1}(\{b\}). \end{align*}
In some sense \(\tilde{f}^{-1}\) is an inverse of \(f\text{,}\) except that it is a function \(B \to (A / \mathord{\equiv}_f) \) instead of \(B \to A\text{.}\)