# 抽象代数代考| Inverse Maps. Equivalence relations.

1. Definition 1: Inverse map

Map $g: B \rightarrow A$ is the inverse of the map $f: A \rightarrow B$ if

$$(g \circ f)=\mathrm{i} d_{A}, \text { and }(f \circ g)=\mathrm{i} d_{B}$$

where $\mathrm{i} d_{A}$ and $\mathrm{i} d_{B}$ are the identity maps of sets $A$ and $B$ respectively. The inverse map is usulay denoted by

$$f^{-1}: B \rightarrow A$$

2. Example 1

Map

$$g:[0,+\infty) \rightarrow[0,+\infty), \quad g(x)=\sqrt{x}$$

is the inverse of the map

$$f:[0,+\infty) \rightarrow[0,+\infty), \quad f(x)=x^{2}$$

At the same time map

$$f:(-\infty,+\infty) \rightarrow[0 ;+\infty), \quad f(x)=x^{2}$$

does not admit an inverse $^{a}$.

${ }^{a}$ Why?

When does a map admits an inverse? The following theorem answers this question.

3. Theorem 1

Map $f: A \rightarrow B$ admits an inverse if and only if $f$ is bijective. In this case the inverse is unique.

NB: Whenever we encounter if and only if claim, a proof in two directions is required!

Proof. Direction $\Longrightarrow$.

Assume that $f$ admits an inverse $g: B \rightarrow A .$ We are about to prove that $f$ is injective and bijective.

• $(f$ is injective). Indeed, assume that $f(x)=f(y)$ for some $x, y \in A .$ Apply map $g$ to both sides of this identity, then

$$x=\mathrm{i} d_{A}(x)=(g \circ f)(x)=g(f(x))=g(f(y))=(g \circ f)(y)=\mathrm{i} d_{A}(y)=y .$$

So $f$ is injective.

• ( $f$ is surjective). Take any $b \in B$. Then

$$f(g(b))=(f \circ g)(b)=\mathrm{i} d_{B}(b)=b,$$

so $b$ is in the range of $f$, and therefore $f$ is surjective.

Direction $\Longleftarrow$.

Assume that $f$ is both injective and surjective. We are about to construct function $g: B \rightarrow A$ which will be the inverse of $f$. Given any $b \in B$ we can find $a \in A$ such that $f(a)=b$, since $f$ is surjective. Then we define

$$g(b)=a$$

It remains to check that $g$ is indeed the inverse map. – Check that $(f \circ g)=\mathrm{i} d_{B} .$ Take any $b \in B .$ Then by definition of $g$, we have $f(g(b))=b$. Therefore indeed $(f \circ g)(b)=b$.

• Check that $(g \circ f)=\mathrm{i} d_{A}$. Take any $a \in A$. Then we want to check that

$$(g \circ f)(a)=a$$

$$f(g(f(a)))=f(a)$$

since $f \circ g=\mathrm{i} d_{B}$. Now, as $f$ is injective the latter implies

$$g(f(a))=a$$

as required.

4. Equivalence relations

Often, given a set $A$, we would like to consider a coarser set by identifying some of the elements of $A$ with each other. For example if $A={$ days in October $}$, then planning a schedule, we might want to identify the same days of the week, e.g., October 6 would be the same to us as October 13 , October 20 , October 27 . This procedure is formalized through the notion of equivalence relations.

5. Definition 2: Equivalence relation

Equivalence relation on a set $A$ is a subset $R \subset A \times A$ satisfying the following properties

• (reflexive) for any $a \in A$ we have $(a, a) \in R$
• $($ symmetric $)$ if $(a, b) \in R$, then $(b, a) \in R$.
• (transitive) if $(a, b) \in R$ and $(b, c) \in R$, then $(a, c) \in R$.

If we have $(a, b) \in R$ we will write ‘ $a \sim b$ ‘ and say ‘ $a$ is equivalent to $b$ ‘.

Set $R \subset A \times A$ consists of all pairs $a, b \in A$ which we would like to identify with each other.

6. Example 2

1. $R={(a, a) \mid a \in A} .$ In other words, any element $a$ is equivalent only to itself.
2. $R={(a, b) \mid a, b \in A} .$ In other words, any element $a \in A$ is equivalent to any other element $b \in A$.
3. Take $R=\mathbb{Z}$ and define $R={(m, n) \mid m-n$ is even $} \subset \mathbb{Z} \times \mathbb{Z}$.

If $a \in A$ and $\sim$ is an equivalence relation, we can form an equivalence class

$$[a]={b \in A \mid b \sim a} .$$

7. Proposition 1

Let $\sim$ be an equivalence relation on the set $A$. Then any two equivalence classes $[a],[b]$ either coincide element-wise, or do not intersect.

8. | Proof. Exercise.

The above exercise allows to define a new set consisting of the equivalence classes:

9. Definition 3

The set of equivalence classes in A modulo an equivalence relation $\sim$ is defined as

$$A / \sim={[a] \mid a \in A} .$$

There is a natural map

$$A \rightarrow A / \sim, \quad a \mapsto[a]$$

sending each element to its equivalence class.

Problem 1: When is the natural map $A \rightarrow A / \sim$ surjective? injective? bijective?

10. Example 3

Going back to Example 2, we see that

If $R={(a, a) \mid a \in A}$ then $A / \sim$ is the same as $A$

If $R={(a, b) \mid a, b \in A}$ then $A / \sim$ has only one element

Finally, in the last example $\mathbb{Z} / \sim$ consists of two elements: class of odd integers and class of even integers.