Skip to main content
Logo image

Elementary Foundations: An introduction to topics in discrete mathematics

Jeremy Sylvestre

Section 18.4 Important examples

Example 18.4.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 \(\powset{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 18.4.2. Even and odd.

We can partition \(\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*} (\N / \mathord{\equiv}_2) = \{ \eqclass{0}, \eqclass{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*} \eqclass{1} + \eqclass{1} = \eqclass{1 + 1} = \eqclass{2} = \eqclass{0} \text{.} \end{equation*}

Example 18.4.3. Modulo-\(n\) arithmetic.

Similarly to Example 18.4.2, if we consider the modulo-\(n\) equivalence relation \(\mathord{\equiv}_n\) on \(\N\text{,}\) we have
\begin{equation*} (\N / \mathord{\equiv}_n) = \{ \eqclass{0}, \eqclass{1}, \eqclass{2}, \dotsc, \eqclass{n-1} \} \text{.} \end{equation*}
We can transfer the arithmetic of \(\N\) to \(\N / \mathord{\equiv}_n\) by defining
\begin{align*} \eqclass{m} + \eqclass{n} \amp = \eqclass{m + n} \text{,} \amp \eqclass{m} \cdot \eqclass{n} \amp = \eqclass{m n} \text{.} \end{align*}
For example, in modulo-\(5\) arithmetic,
\begin{equation*} \eqclass{2} + \eqclass{4} = \eqclass{6} = \eqclass{1} \end{equation*}
and
\begin{equation*} \eqclass{2} \cdot \eqclass{4} = \eqclass{8} = \eqclass{3} \text{.} \end{equation*}

Checkpoint 18.4.4. (Bonus content) Properties of modulo-\(n\) arithmetic.

There are a few things to check about this new modulo-\(n\) arithmetic.
  1. 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.
  2. 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.
  3. The natural numbers \(0\) and \(1\) play special roles in \(\N\) with respect to ordinary addition and multiplication, respectively. Do their equivalence classes \(\eqclass{0}\) and \(\eqclass{1}\) play the same special roles in \(\N / \mathrel{\equiv}_n\) with respect to modulo-\(n\) addition and multiplication, respectively?

Example 18.4.5. Same image under a function.

For a function \(\funcdef{f}{A}{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 18.4.6. Classes of the “same image” relation for an injective function.

Suppose \(\funcdef{f}{A}{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 18.4.7. 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 \(\funcdef{f}{A}{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) \amp \to B, \\ \eqclass{a} \amp \mapsto f(a). \end{align*}
Diagram illustrating an induced map on a quotient
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}\bbrac{\eqclass{a}} = f(a)\) to depend on the choice of class representative \(a\) is well-defined, and hence is a function.
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*} \inv{\tilde{f}} \colon B \amp \to (A / \mathord{\equiv}_f), \\ b \amp \mapsto \setdef{a\in A}{ f(a) = b } = \inv{f}\bbrac{\{b\}}. \end{align*}
In some sense \(\inv{\tilde{f}}\) is an inverse of \(f\text{,}\) except that it is a function \(B \to (A / \mathord{\equiv}_f) \) instead of \(B \to A\text{.}\)
<Prev^TopNext>