Category Theory Note 2 Newbie Composition and Morphisms

Posted on In Disqus:

Isomorphism or invertible map will be discussed in this chapter.

Isomorphism as Invertible Map

The crucial part of such map property is that an inverse map exists that $f: A \longrightarrow B$ has a $g$ inverse that satisfies $g \circ f \equiv 1_A$ and $f \circ g \equiv 1_B$.

A similarity between two collections can be given by choosing a map, which maps each element from the first one to the second one.

Thus isomorphism is also called invertible map. $A,B$ two objects are said to be isomorphic if an isomorphism $f:A\longrightarrow B$ exists. Properties:

  • Reflexive: $A$ is isomorphic to $A$.
  • Symmetric: If $A$ is isomorphic to $B$, $B$ is isomorphic to $A$.
  • Transitive: If $A$ is isomorphic to $B$, $B$ is isomorphic to $C$, $A$ is isomorphic to $C$.

Thus it is obvious that $1_A$ is an isomorphism, if $f:A\longrightarrow B$ is an isomorphism, $g$ as inverse of $f$ is also an isomorphism.

It is also obvious that the inverse (if exists) of any map $f$ is unique, which means only one $g$ be $f-$inv or $f^{-1}$.

Two simple problems may occur, one is “determination“ or “extension“

Determination

and the other one is “choice“ or “lifting“

Choice

Examples

What if we have “determination“ problem with $B = \boldsymbol{1}$, which makes

Point

It is easy to see that $g$ is a point to $C$, which means $g:\boldsymbol{1}\longrightarrow C$. Thus $h(x)$ for $x \in A$ have $h(x) = (g \circ f)(x) = g(b)$ for $b \in B \equiv \boldsymbol{1}$.

In this way, $h$ is a constant because $\forall x \in A$, $h$ maps them to a single value $g(b)$ on $C$.

Another example here is on “choice“ problem with $A = C$, which makes

Choice

To make things easier, we give a small example

Identity

It is not hard to see that $g$ is constant and $f$ has two choices. The only way for $f$ existence is that $|B| \ge |A|$ and every element in $C$ is mapped.

Retraction, Section

Retraction can be defined if $f:A \longrightarrow B$, a retraction for $f$ is a map $r :B \longrightarrow A$ for which $r \circ f = 1_A$. The determination problem can be simplified in a way shown in following pictures.

Section can be defined if $f : A \longrightarrow B$, a section for $f$ is a map $s: B\longrightarrow A$ for which $f \circ s = 1_B$. The choice problem can be simplified in a way shown in following pictures.

It is not hard to see that, if $f:A\longrightarrow B$ has a section $s:B\longrightarrow A$, then $\forall T$ and $\forall m:T\longrightarrow B, \exists x:T\longrightarrow X$ that $f \circ x = m$.

The dual version is: If $f:A\longrightarrow B$ has a retraction $r:B\longrightarrow A$, then $\forall T, \forall m: A\longrightarrow T, \exists x: B\longrightarrow T$ that $x \circ f = m$.

Epimorphism, Monomorphism, Idempotent

Suppose $f:A\longrightarrow B$ has a retraction, then $\forall T, \forall x_1, x_2:T\longrightarrow A$, if $f \circ x_1 = f\circ x_2$, then $x_1 = x_2$.

A map $f$ satisfying this conclusion is said to be injective for maps from $T$. If $\forall T$ is satisfied, then $f$ is injective, or is a monomorphism.

The dual version is that $f :A\longrightarrow B$ has a section, then $\forall T, \forall x_1, x_2:B \longrightarrow T$, if $x_1 \circ f = x_2 \circ f$, then $x_1 = x_2$.

A map $f$ with cancellation property ($x_1 \circ f = x_2 \circ f$ then $x_1 = x_2$) for any $T$ is called epimorphism.

Both epimorphism and monomorphism are cancellation properties.

An endomap $e$ is called idempotent if $e \circ e = e$.

If $f: A\longrightarrow B$ has both a retraction $r$ and a section $s$, then $r = s$.

Isomorphism, Automorphism

We can rephrase isomorphism with retraction and section:

A map $f$ is called an isomorphism if $\exists f^{-1}$ which is both a retraction and a section for $f$ that $f \circ f^{-1} = 1_B$ and $f^{-1} \circ f = 1_A$.

A map, which is an isomorphism and an endomap at a same time, is an automorphism.

In general, if any isomorphism exists for $A\longrightarrow B$, there are the same number of them as there are automorphism of $A$, and this can be proved without counting.

Let $Aut(A)$ be the set of all automorphisms of $A$ and $Isom(A,B)$ be the set of all isomorphisms of $A\longrightarrow B$. We just need to construct isomorphism between those two sets.

If $f : A\longrightarrow B$ is an isomorphism, then $F : Aut(A)\longrightarrow Isom(A,B)$ can be constructed by $F(\alpha) = f\circ \alpha$ for any automorphism $\alpha$ on $A$.

$F(\alpha) \in Isom(A,B)$, and we want to show $F$ itself is an isomorphism, by constructing $S = F^{-1}: Isom(A,B)\longrightarrow Aut(A)$.

Thus, $S(g) = f^{-1} \circ g$.
$$
\begin{aligned}
(F \circ S)(g) &= F(S(g))= F(f^{-1}\circ g) = f \circ (f^{-1}\circ g) = g\newline
(S \circ F)(\alpha) &= S(F(\alpha)) =S (f\circ \alpha) = f^{-1} \circ(f\circ \alpha) = \alpha
\end{aligned}
$$
We can see that $F\circ S = 1_{Isom(A,B)}$ and $S\circ F = 1_{Aut(A)}$.

Automorphism, or Permutation

An automorphism in category of sets is traditionally called a permutation, suggesting that it shifts elements of its sets around in a specified way.

A category of permutation has an object defined with a set $A$ and an automorphism $\alpha$. Thus an object is defined as $A^{\Large\circlearrowright_\alpha}$.

A map from $A^{\Large\circlearrowright_\alpha}$ to $B^{\Large\circlearrowright_\beta}$ is a map of $f : A\longrightarrow B$ which preserve the automorphisms $\alpha$ and $\beta$ in a sense that $f \circ \alpha = \beta\circ f$.

If $g$ is a map from $B^{\Large\circlearrowright_\beta}$ to $C^{\Large\circlearrowright_\gamma}$, and we want to compose $f$ and $g$, the natural thing is to compose them as $A \overset{f}{\longrightarrow} B \overset{g}{\longrightarrow} C$.

The verification is shown in the following commutative diagram, which indicates $g \circ f \circ \alpha = g \circ \beta\circ f = \gamma \circ g \circ f$.