6. Functor and Natural Transformation

6.1. Functor

We were led to study categories by noting that many areas of mathematics have their own definition of a “function” between their objects. Since category theory is a mathematical discipline whose objects are categories, we would like to define a “function” between categories. Of course we would like such a function to preserve categorical structure, sending objects to objects and morphisms to morphisms as well as preserving identities and composition.

A functor \(F\colon \mathcal C \to \mathcal D\) consists of a function \(F_0\) which maps objects of \(\mathcal C\) to objects of \(\mathcal D\) and a function \(F_1\) which maps morphisms of \(\mathcal C\) to morphisms of \(\mathcal D\) such that

\(F\) preserves domains and codomains of morphisms:

\[\text{if } f\colon A\to B \text{ in } \mathcal C, \text{ then } F_1(f)\colon F_0(A)\to F_0(B) \text{ in }\mathcal D;\]

\(F\) preserves identities: \(F_1(\mathrm{id}_A)=\mathrm{id}_{F_0(A)}\);

\(F\) preserves composition: \(F_1(g\circ f)=F_1(g)\circ F_1(f)\).

Indeed, these are the natural conditions we would expect a “morphism of categories” to fulfill. When doing so causes no confusion, we drop subscripts and parentheses and simply write \(Ff\colon FA\to FB\), and so forth.

An example is the free monoid, or Kleene closure of a set.

Example 6.1

Let \(A\) be a set of symbols, or “letters.” A finite string of letters from \(A\) is called a “word,” and \(A^\ast\) denotes the set of all words (including the empty word, which is denoted by \(\varepsilon\)). Thus,

\[A^\ast =\{a_0a_1\dots a_{n-1} \mid a_i\in A\text{ and }n\in\mathbb{N}\}\cup\{\varepsilon\}\]

If \({::}\) denotes the binary concatenation operation, defined by

\[a_0 a_1\dots a_{m-1}{::}b_0 b_1\dots b_{n-1}= a_0 a_1\dots a_{m-1} b_0 b_1\dots b_{n-1},\]

then the algebra \(\mathbf{A}^\ast = \langle A^\ast, \epsilon, :: \rangle\) is a monoid. (Exercise!)

Now consider the mapping \(K\) that takes a set \(A\) to its Kleene closure \(KA = \mathbf{A}^\ast\), and takes each function \(f \colon A \to B\) to the function \(Kf \colon A^\ast \to B^\ast\) defined as follows:

\[K f(a_0 a_1 \dots a_{n-1}) = f(a_0) f(a_1) \dots f(a_{n-1}).\]

Then \(K \colon \mathbf{Set}\to \mathbf{Mon}\) is a functor.

---

Exercise 6.1.1: Prove that the \(K:\) Set → Mon just described is indeed a functor. Also prove that the Kleene closure \(𝐀^∗\) of a set \(A\) is a monoid, and that \(Kf: 𝐀^∗ → 𝐁^∗\) is a monoid morphism.

---

There is another functor in the opposite direction of the Kleene closure.

Example 6.2

The underlying set functor of \(𝐌\) is denoted by \(U 𝐌\) (or \(|𝐌|\)); it returns the universe of the structure \(𝐌\), and for each morphism \(f\), \(U f\) (or \(|f|\)) is \(f\) viewed simply as a function on sets.

---

Exercise 6.1.2: Prove that the \(U:\) Mon → Set just defined is indeed a functor.

---

Note

To denote the Kleene closure of a set \(A\), we will use either \(KA\) or \(𝐀^∗\), as convenience dictates. Similarly, we may use \(U 𝐌\) or \(|𝐌|\) to denote the underlying set of the structure \(𝐌\).

---

Example 6.3

Let \(η_A: A → |𝐀^*|\) be the function that maps \(a ∈ A\) to the “one-letter word” \(a ∈ A^*\). The functors \(K = (\ ⋅\ )^∗\) and \(U = |\ ⋅\ |\) are related by the universal mapping property of monoids, which says that for every monoid \(𝐌\) and every function \(f: A → U 𝐌\) there exists a unique morphism \(f̂: KA → 𝐌\) such that the triangle in the figure below commutes.

(We have included two copies of the diagram to demonstrate our alternative but equivalent notational conventions.)

---

Exercise 6.1.3: Verify that there does indeed exist such an \(\hat{f}\) and that it is unique.

Exercise 6.1.4: Show that functor composition is associative. Use this to conclude that \(UK:\) Set → Set is a functor.

---

6.2. Endomorphism and Endofunctor

A morphism \(f: A → A\) with equal source and target is called an endomorphism.

Given morphisms \(f, g\), if \(src(f) = src(g)\) and \(tar(f) = tar(g)\) then we call them parallel morphisms and write \(f,g: A → B\).

Parallel morphisms \(f,g: A → B\) are typically diagrammed like this

A functor with common source and target category is called an endofunctor.

If two functors \(F, G\), satisfy \(src(F) = src(G)\) and \(tar(F) = tar(G)\), then we call them parallel functors.

Let’s look at some more examples of functors.

Example 6.4

Given two sets \(A\) and \(B\), regard the posets \(P(A)\) and \(P(B)\) as categories (via the inclusion order). Given a function \(f: A → B\), we define the

existential image functor \(∃ f: P(A) → P(B)\) by

\[∃ f(X) = \{f(x): x ∈ X\}, \quad \text{ for } X ∈ P(A);\]

universal image functor \(∀ f: P(A) → P(B)\) by

\[∀ f(X) = \{y ∈ B : f^{-1}(\{y\}) ⊆ X\}, \quad \text{ for } X ∈ P(A).\]

Thus, if \(f: A → B\) is a set morphism, then \(∃f, ∀f: P(A) → P(B)\) is a pair of parallel functors,

---

Exercise 6.2.1: Verify that the functor from Grp to Mon that takes a group to its monoid reduct is both full and faithful.

Exercise 6.2.2: Verify that \(∃ f\) and \(∀ f\) are indeed functors. In particular, they are monotone functions, as required.

---

Another pair of examples is provided by the so-called powerset functor.

Example 6.5

If for each \(f: A → B\) we define the morphism \(Pf: PA → PB\) by

\[Pf(S)=\{f(x)∣ x ∈ S\} \text{ for each } S ⊆ A,\]

then the (covariant) powerset functor is the one depicted by the diagram on the left in the figure below.

For each \(g\colon B \to A\) define \(g^\leftarrow \colon PA \to PB\) by

\[g^\leftarrow(S) = \{b \in B \mid g(b) \in S\}, \text{ for each } S\subseteq A.\]

If we define the morphism \(\bar{P}g\colon PA\to PB\) by \(\bar{P}g=g^\leftarrow\), then the contravariant powerset functor is the one depicted on the right in the figure above.

Note that \(g\) is a function from \(B\) to \(A\), which is a morphism from \(A\) to \(B\) in \(\mathbf{Set}^{\mathrm{op}}\).

---

Exercise 6.2.3: Verify that given two functors \(F: \mathcal C → \mathcal D\) and \(G: \mathcal D → \mathcal E\) we have that \(G ∘ F: \mathcal C → \mathcal E\) is also a functor. That is, verify that functor composition is well-defined.

---

6.3. Natural transformation

A category of categories has categories as objects and functors as morphisms. The functors of categories of categories are called natural transformations. More precisely, a natural transformation (is a family of morphisms that) takes one category to another, and takes functors (“category morphisms”) to functors.

Given functors \(F, G \colon \mathcal C \to \mathcal D\), a natural transformation \(\alpha \colon F {\Rightarrow}G\) is a family \(\{\alpha_A \mid A \in \mathcal C_0\}\) of morphisms in \(\mathcal D\) indexed by the objects of \(\mathcal C\) such that, for each \(A \in \mathcal C_0\), the map \(\alpha_A\) is a morphism from \(FA\) to \(GA\) satisfying the following naturality condition: \(Gf \circ \alpha_A = \alpha_B \circ Ff\), for every \(f\colon A \to B\) in \(\mathcal C_1\); that is, the square in the figure below commutes.

The morphism \(\alpha_A\) is called the component of \(\alpha\) at \(A\).

We shall also write \(\alpha\colon F \Rightarrow G\colon \mathcal C \to \mathcal D\) to indicate that \(\alpha\) is a natural transformation between the functors \(F, G\colon \mathcal C \to \mathcal D\).

We may refer to the commutativity of the square in the figure aboveas the naturality of \(\alpha\) at \(A\) in \(f\).

Let’s now look at a couple of important examples of natural transformations.

Example 6.6

Recall the functor \(K\colon \mathbf{Set}\to \mathbf{Mon}\) which takes a set \(A\) to its Kleene closure.

We can define a natural transformation \(rev \colon K \Rightarrow K\) with components \(rev_A \colon A^\ast \to A^\ast\) given by \(rev_A(a_1 a_2 \dots a_n) = a_n a_{n-1} \dots a_1\), for all \(a_1 a_2 \dots a_n \in A^\ast\).

This does indeed define a natural transformation since \(Kf \circ rev_A = rev_B\circ Kf\), and one can easily verify this naturality (of \(rev\) at \(A\) in \(f\)). (Exercise!)

---

Exercise 6.3.1: Verify the naturality.

---

Our second example of a natural transformation involves the covariant powerset functor \(\mathcal P\colon\mathbf{Set}\to\mathbf{Set}\), as well as the composition of the functors \(U\) and \(K\) defined above.

Example 6.7

Let \(\alpha\colon UK \to \mathcal P\) be defined for each set \(A\) as follows:

\[\begin{split}\alpha_A(s)= \begin{cases} \{\alpha_0,\dots,\alpha_n\} &\text{when } s=\alpha_0\cdots\alpha_n \\ \varnothing &\text{when } s=\epsilon \end{cases}\end{split}\]

In order to verify the naturality of \(\alpha\) in \(A\) at \(f \colon A \to B\), we must show that \(\mathcal Pf\circ\alpha_A=\alpha_B\circ Uf^\ast\).

Let \(s\in{UA^\ast }\). In case \(s=a_0\cdots a_n\), we have

\[\begin{split}(\mathcal Pf\circ\alpha_A)(s) &= \mathcal Pf(\{a_0,\dots,a_n\})\\ &= \{f(a_0),\dots,f(a_n)\}\\ &= \alpha_B(f(a_0)\cdots f(a_n))\\ &= (\alpha_B\circ{Uf^\ast })(s).\end{split}\]

On the other hand, if \(s=\epsilon\), then

\[(\mathcal Pf\circ\alpha_A)(s)=\mathcal Pf(\varnothing)=\varnothing=\alpha_B(\varnothing)=(\alpha_B\circ Uf^\ast)(s).\]

Since for all \(s\in UA^\ast\) we have \((\mathcal Pf\circ\alpha_A)(s)=(\alpha_B\circ Uf^\ast)(s)\) we conclude that \(\mathcal Pf\circ\alpha_A=\alpha_B\circ Uf^\ast\), as desired. Thus, \(\alpha\) is a natural transformation.

Example 6.8 (evaluation functor)

Let \(X\) be a fixed set and denote by \(\mathrm{id}_\mathbf{Set}\) the identity functor.

Define a functor \(F_X\colon \mathbf{Set}\to \mathbf{Set}\) as follows:

• on objects. \(F_XA= (X \rightarrow A)\times X\)
• on morphisms. \(F_Xf = (f\circ \_) \times \mathrm{id}_X\),

where \(A\) is any set and \(f\) is any function.

Here, \((X \rightarrow A)\) denotes all functions from \(X\) to \(A\), and \((X \rightarrow A) \times X\) is a cartesian product of sets, and \((f\circ \_) \times \mathrm{id}_X\) is a cartesian product of functions.

Explicitly, if \((g, x) \in (X \to A) \times X\), then \(((f\circ \_) \times \mathrm{id}_X) (g,x) = (f\circ g, \mathrm{id}_X(x)) = (f g, x)\).

Define \(ev\colon F_X {\Rightarrow}\mathrm{id}_{\mathbf{Set}}\) as follows:

for each set \(A\), let the component \(ev_A\) be the evaluation function, that is,

\[\begin{split}ev_A : (X → A) × X & \ ⟶ \ A; \\ (g,x) & \ ⟼ g(x). \phantom{XX}\end{split}\]

To see that \(ev\) is a natural transformation, let \(f: A \to B\) be a function and check that \(\mathrm{id}_{\mathbf{Set}}(f) \circ ev_A = ev_B\circ F_Xf\). Indeed, if \((g,x)\in (X \rightarrow A) \times X\), then

\[\begin{split}\begin{aligned}(\mathrm{id}_{\mathbf{Set}}(f) \circ ev_A)(g,x)&= f(ev_A(g,x)) = fg(x)\\ &= ev_B(fg,x) = ev_B((f\circ \_) \times \mathrm{id}_X)(g,x))\\ &= ev_B(F_Xf(g,x)) = (ev_B\circ F_Xf)(g,x). \end{aligned}\end{split}\]

Thus, if \(f\in \mathbf{Set}_1\) and \(A = \mathrm{dom}f\), then \(ev\) is natural at \(A\) in \(f\); equivalently, the following diagram commutes for all \(f \in \mathbf{Set}_1\) (where \(A = \mathrm{dom}f\), \(B = \mathrm{cod}f\)):

Example 6.9 (evaluation natural transformation)

Let \(\mathrm{id}_{\mathbf{Set}}\) be the identity endofunctor on \(\mathbf{Set}\) (acting as one expects).

Take a fixed set \(A\) and define \(F_A\colon \mathbf{Set}\to \mathbf{Set}\) as follows:

for each function \(f\) mapping \(A\) to a set \(B\), let

\[\begin{split}\begin{aligned}F_A(B) &:= B^A \times A,\\ F_A(f) &:= (f\circ \_) \times \mathrm{id}_A.\end{aligned}\end{split}\]

As usual,

\(B^A\) denotes the collection of functions from \(A\) to \(B\),

\(B^A \times A\) is a cartesian product of sets, and

\((f\circ \_) \times \mathrm{id}_A\) is a cartesian product of functions.

The evaluation natural transformation is denoted by \(eval^A\colon F_A \to \mathrm{id}_{\mathbf{Set}}\) and defined as follows:

for each set \(B\), let the component \(eval^A_B\) be the evaluation function (i.e., function application); that is, … (todo: complete sentence!)

We can think of a natural transformation \(\alpha\) as a single polymorphic function rather than a collection of functions, since the definition of natural transformation guarantees that \(\alpha\) behaves “in the same way” regardless of the object parameter.

Two more examples of a natural transformations are the source and target maps for a graph.

Example 6.10

Let \(g\) be an object in \(\mathbf{Grph}\) (i.e., a graph).

Define the vertices functor \(V\colon\mathbf{Grph}\to\mathbf{Set}\) by \(V(g)= V_g\) and \(V(f)= f_v\).

Define the edges functor \(E\colon\mathbf{Grph}\to\mathbf{Set}\) by \(E(g)= E_g\) and \(E(f)= f_e\).

We then have the source natural transformation \(\sigma\colon E\to V\) where \(\sigma_g\colon E_g\to V_g\) is given by \(\sigma_g(e)= s_g(e)\) and the target natural transformation \(\tau\colon E\to V\) where \(\tau_g\colon E_g\to V_g\) is given by \(\tau_g(e)= t_g(e)\).

To summarize, if \(g\) is an object in \(\mathbf{Grph}\), then we have

\(E\): the “edges” functor mapping \(g\) to \(E_g\) and \(f\) to \(f_E\);

\(V\): the “vertices” functor mapping \(g\) to \(V_{g}\) and \(f\) to \(f_V\);

\(\sigma\) : the “source” natural transformation \(\sigma_{g} \colon E_{g} \to V_{g}; \; e \mapsto s_{g}(e)\);

\(\tau\) : the “target” natural transformation, \(\tau_{g} \colon E_{g} \to V_{g};\; e \mapsto t_{g}(e)\).

---

Exercise 6.3.2: Verify that \(V\) and \(E\) are functors and that \(σ\) and \(τ\) are natural transformations.

---

Intuitively, natural transformations are polymorphic functions, functions that operate in the “same way” independently of the object parameter.

Example 6.11

Suppose we have

• categories. \(\mathcal C\), \(\mathcal D\), \(\mathcal E\), \(\mathcal F\),
• functors. \(I\colon \mathcal C \to \mathcal D,\;\) \(\;F, G\colon \mathcal D \to \mathcal E,\;\) \(\;H\colon \mathcal E \to \mathcal F\),
• natural transformation. \(\alpha\colon F \Rightarrow G\).

From this context arise two more pairs of functors.

\(FI,\, GI \colon \mathcal C \to \mathcal E\),

\(HF,\, HG \colon \mathcal D \to \mathcal F\),

and we can define a pair of natural transformations:

\(\alpha I\colon FI \Rightarrow GI\) with components \((\alpha I)_C = \alpha_{IC}\),

\(H\alpha\colon HF \Rightarrow HG\) with components \((H\alpha)_D = H(\alpha_D)\),

for objects \(C\) of \(\mathcal C\) and \(D\) of \(\mathcal D\).

---

6.4. Equivalent categories

An isomorphism in a functor category is referred to as a natural isomorphism. If there is a natural isomorphism between the functors \(F\) and \(G\), then we shall say that \(F\) and \(G\) are naturally isomorphic.

We emphasised at the start of this chapter that we were interested in the way structures behaved and not so much in their internal make-up. To this end we might expect that the judgement “\(A\) and \(B\) are isomorphic in \(C\)” is more important than the judgement “\(A\) and \(B\) are equal in \(C\).” Indeed, the development of category theory has shown this to be the case.

This leads us to the notion of equivalence of categories. If two categories are equivalent, then the rough idea is that we can write down a one-to-one correspondence between isomorphism classes of objects in the respective categories. Let us give the precise definition.

Two categories \(\mathcal C\) and \(\mathcal D\) are called equivalent if there are functors \(F : \mathcal C → \mathcal D\) and \(G :\mathcal D → \mathcal C\) together with natural isomorphisms \(\epsilon : FG \cong \mathrm{id}_{\mathcal D}\), and \(\eta : \mathrm{id}_{\mathcal C} \cong GF\). In this case, we say that \(F\) is an equivalence of categories with an inverse equivalence \(G\) and we denote this equivalence by \(F: \mathcal C \simeq \mathcal D : G\).

---

6.5. Solutions

Solution to Exercise 6.1.1.

We must prove

1. For \(f: A → B\) a set function, \(map(f): A^∗ → B^∗\) is a monoid morphism;
2. \(K(\mathrm{id}_A) = \mathrm{id}_{KA}\);
3. \(K(gf) = Kg ∘ Kf\) where \(f: A → B\) and \(g: B → C\).

The proof of the first item follows from Exercise 5.2.2.

Proof of the second item.

\[\begin{split}K(\mathrm{id}_A)(a_1a_2\dots a_n) &= map(\mathrm{id}_A)(a_1a_2\dots a_n)\\ &= \mathrm{id}_A(a_1)\mathrm{id}_A(a_2)\dots \mathrm{id}_A(a_n)\\ &= a_1a_2\dots a_n \\ &= \mathrm{id}_{A^\ast}(a_1a_2\dots a_n)\\ &= \mathrm{id}_{KA}(a_1a_2\dots a_n).\end{split}\]

Proof of the second item.

\[\begin{split}K(gf)(a_1a_2 \dots a_n) &= map(gf)([a_1a_2,\dots a_n) \\ &= gf(a_1) gf(a_2) \dots gf(a_n)\\ &= map(g)(f(a_1) f(a_2) \dots f(a_n))\\ &= map(g)(map(f)(a_1a_2 \dots a_n)\\ &= (Kg \circ Kf)(a_1a_2 \dots a_n).\end{split}\]

Define the functor \(F :\) Set \(→\) Mon by \(FA = A^∗\) (on objects) and by \(Ff = map(f)\) (on morphisms), where \(map(f): A^∗ → B^∗\) is the usual mapping of a function over a list; that is, \(map(f)(a_0 a_1 \dots a_{n-1}) = f(a_0)f(a_1)\dots f(a_{n-1})\), for all \(a_0 a_1 \dots a_{n-1}\) in \(A^∗\).

We check explicitly that \(F\) is indeed a functor.

• \(F(\mathrm{id}_A) = \mathrm{id}_{FA}\):

\[\begin{split}F(\mathrm{id}_A)(a_1 a_2 \dots a_n) &= map(\mathrm{id}_A)(a_1 a_2 \dots a_n)\\ &= \mathrm{id}_A(a_1) \mathrm{id}_A(a_2)\dots \mathrm{id}_A(a_n)\\ &= a_1 a_2 \dots a_n \\ &= \mathrm{id}_{A^\ast}(a_1 a_2 \dots a_n)\\ &= \mathrm{id}_{FA}(a_1 a_2 \dots a_n).\end{split}\]

• \(F(gf) = Fg ∘ Ff\) where \(f: A → B\) and \(g: B → C\):

  \[\begin{split}F(gf)(a_1 a_2 \dots a_n) &= map(gf)(a_1 a_2 \dots a_n) \\ &= gf(a_1) gf(a_2) \dots gf(a_n)\\ &= map(g)(f(a_1) f(a_2) \dots f(a_n))\\ &= map(g)(map(f)(a_1 a_2 \dots a_n)\\ &= (Fg ∘ Ff)(a_1 a_2 \dots a_n).\end{split}\]

---

Solution to Exercise 6.1.2.

A monoid morphism \(f: 𝐌 → 𝐍\) is a set function that maps the universe of 𝐌 to the universe of 𝐍 and preserves the monoid structure—i.e., repsects the monoid operations.

Thus, \(Uf\) is naturally defined as this set map from \(M\) to \(N\); that is, for each \(m ∈ M\), we simply let \((Uf)(m) = f(m)\).

We now prove that \(U\) is a functor. Property ([item:pres-morphs]) is obvious, as is ([item:pres-ids]) since \(U \mathrm{id}_{𝐌} = \mathrm{id}_{M} = \mathrm{id}_{U 𝐌}\).

As for Property ([item:pres-comps]), if \(f: 𝐌 → 𝐍\) and if \(g: 𝐍 → 𝐏\) are monoid morphisms, then for each \(m ∈ M\) we have \(U(g ∘ f)(m) = g ∘ f(m) = (Ug ∘ Uf)(m)\).

---

Exercise 6.1.3

Solution (to do).

---

Exercise 6.1.4

Solution (to do).

---

Exercise 6.2.1

Solution (to do).

---

Exercise 6.2.2

Solution (to do).

---

Exercise 6.2.3

Solution (to do).

---

Solution to Exercise 6.3.1.

\[\begin{split}(Ff ∘ rev_A)(a_1 a_2 \dots a_n) &= Ff (a_n a_{n-1} \dots a_1)\\ &= map(f)(a_n a_{n-1} \dots a_1)\\ &= f(a_n) f(a_{n-1}) \dots f(a_1)\\ &= rev_B \ f(a_1) f(a_{2}) \dots f(a_n)\\ &= rev_B \ map(f) (a_1 a_{2} \dots a_n)\\ &= (rev_B ∘ Ff) (a_1 a_{2} \dots a_n).\end{split}\]

---

Exercise 6.3.2

Solution (to do).