Homework 3

Problem 1

To any group $G$ we can associate a category $G$ that has a unique object, an arrow for each element of $G$ , and arrow composition given by the group law in $G$ . (See a bit more here.)

Show there is a correspondence^[1] between groups and one-object categories in which every arrow is invertible.
Suppose $G$ and $H$ are groups. Show that group morphisms $ϕ : G \to H$ correspond^[2] to functors $Φ : G \to H$ .
Recall that a permutation representation of $G$ is a group morphism $ϕ : G \to S_{X}$ , where $S_{X}$ is the permutation group on a set $X$ . Show that permutation representations of $G$ correspond to functors $G \to S e t$ .
Suppose $ϕ, ψ : G \to H$ are group morphisms, with corresponding functors $Φ, Ψ : G \to H$ . Show there is a natural transformation $Φ \Rightarrow Ψ$ if and only if $ϕ$ and $ψ$ are conjugate, i.e., there is an element $h \in H$ such that $ψ (g) = h (ϕ (g)) h^{- 1}$ for all $g \in G$ .

Solution

We have seen how to assign to each group $G$ a one-object category $G$ whose arrows are labeled by the elements of $G$ (and with arrow composition corresponding to the group operation). By construction, the identity element in $G$ is sent to the identity arrow (on the unique object) in the category $G$ .

Now suppose $C$ is a category with a unique object and in which every arrow is invertible. Let $G$ be the set of arrows in $C$ , and define a binary operation on $G$ using the arrow composition in $C$ . (Note that every pair of arrows is composable, since all arrows in $C$ start and end at the unique object.) Since $C$ is a category, its composition law is associative and the identity arrow acts as a two-sided identity. It follows that the operation on $G$ is associative and the element corresponding to the identity arrow acts as two-sided identity. By assumption, every arrow in $C$ is invertible, which by construction of $G$ means that every element in $G$ has an inverse under the so-defined binary operation. Thus $G$ is a group.

Finally, it is "clear" these two processes are mutually inverse. (Here we should technically make a bijection between isomorphism classes of groups and something analogous on the category side.)
Suppose $ϕ : G \to H$ is a group morphism. We wish to define a functor $Φ : G \to H$ . Each of the categories $G$ and $H$ has a unique object, so the object function of $Φ$ must map the unique object of $G$ to the unique object of $H$ . The set of arrows in $G$ is $G$ and the set of arrows in $H$ is $H$ , so on arrows we define $Φ$ by $ϕ$ . By our construction of the categories $G$ and $H$ , the map $Φ : G \to H$ sends the (unique) identity arrow in $G$ to the (unique) identity arrow in $H$ (because $ϕ$ is a group morphism and hence $ϕ (e_{G}) = e_{H}$ ), and is compatible with composition (since $ϕ$ is a group morphism and hence $ϕ (g_{1} g_{2}) = ϕ (g_{1}) ϕ (g_{2})$ ). Thus, $Φ$ does indeed define a functor from $G$ to $H$ .

Conversely, suppose $Φ : C \to D$ is a functor between one-object categories in which every arrow is invertible. Let $G$ and $H$ be the groups corresponding to $C$ and $D$ , respectively. Then the set of elements of $G$ (respectively, $H$ ) is the set of arrows in $C$ (respectively, $D$ ), so the arrow function of the functor $Φ$ is a map $ϕ : G \to H$ . The compatibility of the functor $Φ$ with arrow composition (and the fact that it sends the identity arrow to the identity arrow) directly translate to $ϕ$ being a group morphism.

Finally, it is once again "clear" that these two processes are mutually inverse. (Once again, this is not technically true. We are really sketching an equivalence between two specific categories.)
Suppose first that $ϕ : G \to S_{X}$ is a group morphism. We define a functor $F : G \to Set$ as follows. On objects, $F$ maps the unique object of $G$ to the set $X$ . On arrows, $F$ maps each arrow in $G$ (corresponding to an element $g \in G$ ) to the corresponding bijection $ϕ (g) : X \to X$ . (Recall that the group $S_{X}$ consists of all set bijections from $X$ to itself.) Note that the identity element $e \in G$ must be sent to the identity permutation $1_{X} : X \to X$ , and that the group morphism property of $ϕ$ ensures the functor $F$ is compatible with composition: $F (g_{1} g_{2}) = ϕ (g_{1} g_{2}) = ϕ (g_{1}) ϕ (g_{2}) = F (g_{1}) F (g_{2})$ . We have therefore indeed defined a functor $F : G \to Set$ .

Conversely, suppose $F : G \to Set$ is a functor. The object function of $F$ assigns to the unique object of $G$ a set $X$ . The arrow function of $F$ assigns to each arrow in $G$ (corresponding to an element $g \in G$ ) an arrow $ϕ (g) : X \to X$ , with identity arrow (corresponding to the identity element $e \in G$ ) sent to the identity arrow $1_{X} : X \to X$ . The compatibility of the functor with composition implies $ϕ (g_{1} g_{2}) = F (g_{1} g_{2}) = F (g_{1}) F (g_{2}) = ϕ (g_{1}) ϕ (g_{2})$ . This implies both that $ϕ$ is has the group morphism property and also that every map $ϕ (g) : X \to X$ is invertible (i.e., bijective), since every arrow in $G$ is invertible. Thus, $ϕ (g) \in S_{X}$ and $ϕ : G \to S_{X}$ is a group morphism.

As with the previous two parts, these two associations are "clearly" mutually inverse. (We're really asking for trouble at this point.)
First suppose there is a natural transformation $τ : Φ \Rightarrow Ψ$ where $Φ, Ψ$ are functors from $G$ to $H$ . For the sake of clarity, let us label the unique object in $G$ by $a$ and the unique object in $H$ by $b$ . Note that both $Φ$ and $Ψ$ must map $a$ to $b$ . The natural transformation $τ$ is then entirely defined by a single arrow $τ_{a} : b \to b$ in $H$ , i.e., by an element $h \in H$ . The naturality condition requires that for every arrow $g : a \to a$ in $G$ (corresponding to an element $g \in G$ ) we have a commutative diagram

In other words, we must have $h ϕ (g) = ψ (g) h$ , i.e., $ψ (g) = h ϕ (g) h^{- 1}$ . Since this must hold for all $g \in G$ , this exactly says $ϕ$ and $ψ$ are conjugate maps.

Conversely, suppose $ϕ, ψ : G \to H$ are conjugate group morphisms, so that there exists some $h \in H$ such that $ψ (g) = h ϕ (g) h^{- 1}$ for all $g \in G$ . Let $Φ, Ψ : G \to H$ be the functors corresponding to $ϕ$ and $ψ$ , respectively. Define a map $τ : Φ \Rightarrow Ψ$ by sending the unique object $a$ of $G$ to the arrow $τ_{a}$ in $H$ corresponding to the element $h \in H$ . The conjugate property exactly ensures that this defines a natural transformation from $Φ$ to $Ψ$ , by the same diagram as above.

Problem 2

Let $S$ be a fixed set. For each set $X$ , let $X^{S}$ denote the set of all functions $h : S \to X$ in $S e t$ .

Show that $X \mapsto X^{S}$ is the object function of a functor $S e t \to S e t$ .
Show that $X \mapsto X^{S} \times S$ is the object function of a functor $S e t \to S e t$ .
For each set $X$ let $e_{X} : X^{S} \times S \to X$ be the evaluation map, defined by $e (h, s) = h (s)$ . Show that these maps are the components of a natural transformation $e : ∙^{S} \times S \Rightarrow I$ , where $I$ is the identity functor on $S e t$ .

Solution

Let's denote the functor we are creating by $∙^{S} : Set \to Set$ . It is already defined on objects, so we need to define it on arrows. To that end, let $f : X \to Y$ be a set map. We can define a set map $f^{S} : X^{S} \to Y^{S}$ by sending each map $h : S \to X$ (which is what the elements of the set $X^{S}$ are) to the map $f \circ h : S \to Y$ (which is an element of the set $Y^{S}$ ). In other words, $f^{S}$ is the "compose with $f$ " map. Observe that if $1_{X} : X \to X$ is an identity arrow in $Set$ , then $(1_{X})^{S}$ is the "compose with $1_{X}$ " map, which is the identity on $X^{S}$ . (Sanity check: for any $h : S \to X$ , the composition $1_{X} \circ h$ is the same set map $h : X \to S$ .)

It remains to check that this map on arrows is compatible with composition, so suppose $f : X \to Y$ and $g : Y \to Z$ are two set maps. For any $h \in X^{S}$ (i.e., set map $h : S \to X$ ), observe that $(g \circ f)^{S} (h) = (g \circ f) \circ h = g \circ (f \circ h) = g^{S} (f^{S} (h))$ , where the second equality held by the associativity of function composition. Thus, we do indeed have $(g \circ f)^{S} = g^{S} \circ f^{S}$ and hence our arrow map is compatible with composition. We therefore have defined a functor $∙^{S} : Set \to Set$ , as desired.
Define the functor $∙^{S} \times S : Set \to Set$ by sending each set $X$ to the set $X^{S} \times S$ , and each set map $f : X \to Y$ to the set map $f^{S} \times 1_{S} : X^{S} \times S \to Y^{S} \times S$ . (At the level of elements this is simply $(f^{S} \times 1_{S}) (h, s) = (f \circ h, s)$ .) It is straightforward to show this does indeed define a functor, with the verification being nearly identical to the steps used in part 1.
Recall that a natural transformation $τ : ∙^{S} \times S \Rightarrow I$ is the data consisting of a set map $τ_{X} : X^{S} \times S \to X$ for every set $X$ , such that for every set map $f : X \to Y$ the diagram below commutes:

In the case of our evaluation map $e_{X} : X^{S} \times S \to X$ we are being asked to show that the diagram below is commutative:

Let's chase some elements. Starting from the top-left corner, let $(h, s)$ be any element of the set $X^{S} \times S$ . Going across and down corresponds to $f (e_{X} (h, s)) = f (h (s))$ , while going down and then across corresponds to $e_{y} ((f^{S} \times 1_{S}) (h, s)) = e_{Y} (f \circ h, s) = (f \circ h) (s)$ . By the definition of function composition in $Set$ , we always have $f (h (s)) = (f \circ h) (s)$ , and so the diagram does indeed commute. Thus, evaluation does indeed define a natural transformation. (Did you ever really doubt it?)

Problem 3

Recall the notion of pullbacks, which for the sake of this exercise we will only consider in the category $Set$ .

Show that the functor which assigns to each diagram of the form $X \overset{f}{\to} Z \overset{g}{\leftarrow} Y$ in $Set$ the pullback $X \times_{Z} Y$ is a right adjoint of another functor. Describe the unit and counit of the adjunction.

Note

You don't need to check every tiny detail for this one. Define the pullback as a functor (giving the maps on objects and arrows), and then explicitly define the set map that should be a natural bijection between the appropriate hom-sets.

Hints

Let $J$ be the category with three objects and two non-identity arrows, visualized as $∙ \to ∙ \leftarrow ∙$ . Functors $J \to Set$ then correspond to diagrams in $Set$ of shape $J$ ; i.e., diagrams of the form $X \overset{f}{\to} Z \overset{g}{\leftarrow} Y$ in $Set$ . Let ${Set}^{J}$ denote the category of functors $J \to Set$ and let $Δ : Set \to {Set}^{J}$ denote the diagonal functor. Show the pullback functor is a right adjoint of $Δ$ .

Solution

Recall that for each diagram in $Set$ of the form

the pullback consists of the set $X \times_{Z} Y = {(x, y) ∣ f (x) = g (y)}$ together with the set maps $π_{1} : X \times_{Z} Y \to X$ and $π_{2} : X \times_{Z} Y \to Y$ defined by $(x, y) \mapsto x$ and $(x, y) \mapsto y$ , respectively. The set $X \times_{Z} Y$ (together with the maps $π_{1}$ and $π_{2}$ ) are characterized by a certain universal property (which we'll return to later).

Encoding the diagrams as objects in a functor category

To see how the pullback construction is an adjoint functor, we first encode such diagrams as elements of a functor category. Let $J$ be the category with three objects and two non-identity arrows, visualized as $a \overset{ϕ}{\to} c \overset{ψ}{\leftarrow} b$ . Functors $J \to Set$ then correspond to diagrams in $Set$ of shape $J$ ; i.e., diagrams of the form $X \overset{f}{\to} Z \overset{g}{\leftarrow} Y$ in $Set$ , exactly as shown above. (Here we are writing $X$ , $Y$ , and $Z$ for $F (a)$ , $F (b)$ , and