EF Important examples

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 .

In this case, each equivalence class is a singleton:

[a] = {a}

for each

a \in A .

This equivalence relation yields the “finest” or most “granular” partition of

A,

into the union of all the singleton sets in

P (A) .

Here, the quotient

A / \equiv

is essentially the same as

A :

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

\equiv_{2},

and we have quotient

(N / \equiv_{2}) = {[0], [1]} .

🔗

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

[1] + [1] = [1 + 1] = [2] = [0] .

🔗

Example 18.4.3. Modulo- $n$ arithmetic.

🔗

Similarly to Example 18.4.2, if we consider the modulo-

n

equivalence relation

\equiv_{n}

N,

we have

(N / \equiv_{n}) = {[0], [1], [2], \dots, [n - 1]} .

🔗

We can transfer the arithmetic of

N

N / \equiv_{n}

by defining

\begin{aligned} [m] + [n] & = [m + n], & [m] \cdot [n] & = [m n] . \end{aligned}

🔗

For example, in modulo-

5

arithmetic,

[2] + [4] = [6] = [1]

🔗

and

[2] \cdot [4] = [8] = [3] .

🔗

Checkpoint 18.4.4. (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 $N$ with respect to ordinary addition and multiplication, respectively. Do their equivalence classes $[0]$ and $[1]$ play the same special roles in $N / \equiv_{n}$ with respect to modulo- $n$ addition and multiplication, respectively?

🔗

Example 18.4.5. Same image under a function.

🔗

For a function

f : A \to B,

we may consider elements of the domain equivalent if they produce the same output under

f .

That is, the relation

\equiv_{f}

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

f : A \to B

is a function, and consider the equivalence relation

\equiv_{f}

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

\equiv_{f} ?

🔗

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

f : A \to B,

and consider the equivalence relation

\equiv

A

described in Example 18.4.5. Then we may create a new, “induced” function

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

Diagram illustrating an induced map on a quotient — Figure 18.4.8. Diagram illustrating the induced map $\tilde{f} .$

🔗

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 .

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.

🔗

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{aligned} {\tilde{f}}^{- 1} : B & \to (A / \equiv_{f}), \\ b & \mapsto {a \in A | f (a) = b} = f^{- 1} ({b}) . \end{aligned}

🔗

In some sense

{\tilde{f}}^{- 1}

is an inverse of

f,

except that it is a function

B \to (A / \equiv_{f})

instead of

B \to A .

Elementary Foundations: An introduction to topics in discrete mathematics

Search Results:

Section 18.4 Important examples

Example 18.4.1. Equality is the strongest form of equivalence.

Example 18.4.2. Even and odd.

Example 18.4.3. Modulo- $n$ arithmetic.

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

Example 18.4.5. Same image under a function.

Checkpoint 18.4.6. Classes of the “same image” relation for an injective function.

Example 18.4.7. Inverting a non-injective function.

Section 18.4 Important examples

Example 18.4.1. Equality is the strongest form of equivalence.

Example 18.4.2. Even and odd.

Example 18.4.3. Modulo-n arithmetic.

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

Example 18.4.5. Same image under a function.

Checkpoint 18.4.6. Classes of the “same image” relation for an injective function.

Example 18.4.7. Inverting a non-injective function.

Example 18.4.3. Modulo- $n$ arithmetic.

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