The Lumenary · Early undergraduate

Functors

Name: ______________________

Date: ______________________

You will learn to

Define covariant and contravariant functors and show that a contravariant functor from $\cat{C}$ to $\cat{D}$ is the same as a functor $\cat{C}^{\mathrm{op}} \to \cat{D}$
Verify that the power-set, forgetful and hom functors are functors, and describe the free monoid (finite lists) and the free vector space on a set as functors
Prove that functors preserve isomorphisms, and use this to show that objects are not isomorphic
Use functoriality of the fundamental group to show that the disc does not retract onto its boundary circle
Recognise that functors need not be injective and need not reflect isomorphisms

1.
Which of these are functors? Choose all that apply.
- A. $\mathbf{Grp} \to \mathbf{Set}$ : a group goes to its underlying set, a homomorphism to its underlying function.
- B. $\mathbf{Set} \to \mathbf{Set}$ : $X$ goes to the set of finite lists in $X$ , and $f$ to "apply $f$ to every entry".
- C. $\mathbf{Grp} \to \mathbf{Grp}$ : $G$ goes to its centre $Z(G)$ , and $f$ to its restriction to the centre.
- D.Between two posets regarded as categories: a monotone map $p$ , with $x \le y$ sent to $p(x) \le p(y)$ .
- E. $\mathbf{Set} \to \mathbf{Set}$ : $X$ goes to its power set, and $f : X \to Y$ to the preimage map $T \mapsto f^{-1}(T)$ .
2.
How many group homomorphisms are there from $\mathbb{Z}/2$ to $\mathbb{Z}/6$ ? (That is, what is $|\mathrm{Hom}(\mathbb{Z}/2, \mathbb{Z}/6)|$ ?)
3.
Which argument correctly proves that the groups $\mathbb{Z}/4$ and $\mathbb{Z}/2 \times \mathbb{Z}/2$ are not isomorphic?
- A. $|\mathrm{Hom}(\mathbb{Z}/2, \mathbb{Z}/4)| = 2$ but $|\mathrm{Hom}(\mathbb{Z}/2, \mathbb{Z}/2 \times \mathbb{Z}/2)| = 4$ , and the functor $\mathrm{Hom}(\mathbb{Z}/2, -)$ would send an isomorphism to a bijection.
- B.They have different orders.
- C.One is abelian and the other is not.
- D.The bijection $0 \mapsto (0,0)$ , $1 \mapsto (1,0)$ , $2 \mapsto (0,1)$ , $3 \mapsto (1,1)$ is not a homomorphism.
4.
For the contravariant power-set functor $\mathcal{P}^\ast$ (which sends $f : X \to Y$ to the preimage map $\mathcal{P}^\ast(f)(T) = f^{-1}(T)$ ), and functions $f : X \to Y$ , $g : Y \to Z$ , which equation holds for all $T \subseteq Z$ ?
- A. $(g \circ f)^{-1}(T) = f^{-1}\big(g^{-1}(T)\big)$ , i.e. $\mathcal{P}^\ast(g \circ f) = \mathcal{P}^\ast(f) \circ \mathcal{P}^\ast(g)$
- B. $(g \circ f)^{-1}(T) = g^{-1}\big(f^{-1}(T)\big)$
- C. $(g \circ f)^{-1}(T) = g\big(f(T)\big)$
- D.None — preimages do not compose.
5.
Which of the following are morphisms $f$ that are not isomorphisms, but whose image $F(f)$ under the indicated functor is an isomorphism? Choose all that apply.
- A.The identity map from $\mathbb{R}$ with the discrete topology to $\mathbb{R}$ with the usual topology, and $F$ the forgetful functor $\mathbf{Top} \to \mathbf{Set}$ .
- B.The morphism $0 \to 1$ in the poset $\{0 < 1\}$ , and $F$ the functor to $\mathbf{Set}$ sending both objects to $\{\ast\}$ .
- C.A bijective group homomorphism, and $F$ the forgetful functor $\mathbf{Grp} \to \mathbf{Set}$ .
- D.A matrix $A \in \mathrm{GL}_2(\mathbb{R})$ with $\det A = 1$ , regarded as a morphism of the one-object category $\mathrm{GL}_2(\mathbb{R})$ , and $F = \det$ .
6.
In Lean/Mathlib, which type is right for the preimage power-set functor, which sends $f : X \to Y$ to $T \mapsto f^{-1}(T)$ ?
- A.(Type u)ᵒᵖ ⥤ Type u
- B.Type u ⥤ Type u
- C.(Type u)ᵒᵖ ⥤ (Type u)ᵒᵖ
- D.Type u → Type u
7.
In the proof that there is no retraction $r : D^2 \to S^1$ (with $r \circ i = \mathrm{id}_{S^1}$ ), which facts are used? Choose the most complete correct answer.
- A.Functoriality of $\pi_1$ gives $\pi_1(r) \circ \pi_1(i) = \mathrm{id}$ on $\pi_1(S^1) \cong \mathbb{Z}$ ; this identity would factor through $\pi_1(D^2) = 0$ , which is impossible.
- B. $\pi_1$ preserves isomorphisms, and $D^2$ is not isomorphic to $S^1$ .
- C. $D^2$ is compact and $S^1$ is not.
- D. $S^1$ minus a point is connected, so $r$ cannot be continuous.
8.
Functions between finite sets are stored as Python dicts. Write image(f, S) (the set $f(S)$ ) and preimage(f, T) (the set $f^{-1}(T)$ ), and compose(g, f) (first f, then g). The tests check the functor laws: images compose covariantly, $(g \circ f)(S) = g(f(S))$ , and preimages contravariantly, $(g \circ f)^{-1}(T) = f^{-1}(g^{-1}(T))$ .
Computational — Practice

Answer key — Functors

1.
The forgetful functor, the list functor and monotone maps are functors. The centre is not functorial under restriction, and the preimage construction reverses arrows, so it is a functor from $\mathbf{Set}^{\mathrm{op}}$ , not from $\mathbf{Set}$ .
2.
Homomorphisms $\mathbb{Z}/2 \to G$ correspond to elements $g$ with $2g = 0$ . In $\mathbb{Z}/6$ these are $g = 0$ and $g = 3$ . So there are $2$ .
3.
Apply the functor $\mathrm{Hom}(\mathbb{Z}/2, -) : \mathbf{Grp} \to \mathbf{Set}$ . Its values have $2$ and $4$ elements (the solutions of $2g = 0$ ). Isomorphic groups would give isomorphic sets, i.e. sets of the same size. Hence $\mathbb{Z}/4 \not\cong \mathbb{Z}/2 \times \mathbb{Z}/2$ .
4.
$x \in (g \circ f)^{-1}(T)$ iff $g(f(x)) \in T$ iff $f(x) \in g^{-1}(T)$ iff $x \in f^{-1}(g^{-1}(T))$ . So $\mathcal{P}^\ast(g \circ f) = \mathcal{P}^\ast(f) \circ \mathcal{P}^\ast(g)$ : a functor $\mathbf{Set}^{\mathrm{op}} \to \mathbf{Set}$ .
5.
The first two. Functors preserve isomorphisms but need not reflect them. In the third option $f$ is already an isomorphism of groups, and in the fourth every morphism is invertible.
6.
Preimage along $f : X \to Y$ goes from subsets of $Y$ to subsets of $X$ , so it is contravariant: a functor (Type u)ᵒᵖ ⥤ Type u. This is Lumenary.Functors.powersetContra, whose map field is f.unop ⁻¹' T and whose laws are Set.preimage_id and Set.preimage_preimage.
7.
Applying the functor $\pi_1$ to $r \circ i = \mathrm{id}_{S^1}$ gives $\pi_1(r) \circ \pi_1(i) = \mathrm{id}_{\pi_1(S^1)}$ . Since $\pi_1(D^2)$ is trivial, the left side sends every element to the identity, while the right side is the identity of $\mathbb{Z}$ , which is not trivial. Contradiction.
8.
```
def compose(g, f):
    return {x: g[f[x]] for x in f}

def image(f, S):
    return {f[x] for x in S}

def preimage(f, T):
    return {x for x in f if f[x] in T}
```
The tests check the functor laws on every subset, which is exhaustive for these small sets; the one-line proofs in the lesson show the laws for all sets. Notice that the preimage of $g$ is applied first in $f^{-1}(g^{-1}(T))$ : that reversal is contravariance.