CTfS Chapter 4 Exercises

exercise

Exercises from Category Theory for Scientists (CTfS), Chapter 4 (“Basic category theory”). CTfS gives no solutions; the solutions here are the wiki’s own. This is a selection: the exercises referenced from concept notes. Solutions: CTfS Chapter 4 Solutions. Index: Map of Content.

Exercise 4.1.1.8

(The category $\mathbf{FLin}$ of finite linear orders.) Let $\mathbf{FLin}$ be the full subcategory of $\mathbf{PrO}$ spanned by the finite nonempty linear orders, and let $[n]=\{0<1<\cdots <n\}$. What are the cardinalities of

• a. ${\mathrm{Hom}}_{\mathbf{FLin}}([0],[3])$;
• b. ${\mathrm{Hom}}_{\mathbf{FLin}}([3],[0])$;
• c. ${\mathrm{Hom}}_{\mathbf{FLin}}([2],[3])$;
• d. ${\mathrm{Hom}}_{\mathbf{FLin}}([1],[n])$;
• e. (Challenge) ${\mathrm{Hom}}_{\mathbf{FLin}}([m],[n])$?

CTfS §4.1.1; context: Map of Content, Monotone Map, Simplex Category.

Sources: CTfS, Exercise 4.1.1.8.

Solution: Solution 4.1.1.8

Exercise 4.1.2.29

Let $G$ be the graph whose vertices are all cities in the US and whose arrows are airplane flights connecting cities. What idea is captured by the free category on $G$?

CTfS §4.1.2; context: Free Category, Map of Content.

Sources: CTfS, Exercise 4.1.2.29.

Solution: Solution 4.1.2.29

Exercise 4.2.1.10

Let $S=\{1,2,3,4\}\in \mathrm{Ob}(\mathbf{Set})$.

• a. What is the automorphism group of $S$, and how many elements does it have?
• b. What is the endomorphism monoid of $S$, and how many elements does it have?
• c. Is the endomorphism monoid of $S$ the underlying monoid of the automorphism group?

CTfS §4.2.1; context: Endomorphism Monoid, Map of Content.

Sources: CTfS, Exercise 4.2.1.10.

Solution: Solution 4.2.1.10

Exercise 4.2.1.11

Consider the graph $G$ with vertices $1,2,3,4$ and arrows $12,21,13,31,24,42,34,43$ (arrow $ij$ goes from $i$ to $j$): a square $1-2-4-3-1$ with both directions on each side. What is its group of automorphisms? (Hint: every automorphism of $G$ induces an automorphism of $\{1,2,3,4\}$; which ones preserve the arrows?)

CTfS §4.2.1; context: Endomorphism Monoid, Map of Content.

Sources: CTfS, Exercise 4.2.1.11.

Solution: Solution 4.2.1.11

Exercise 4.2.1.13

A preorder can be considered as a category $P$. A partial order is a preorder with an additional property (antisymmetry). Phrase this property in terms of isomorphisms in $P$.

CTfS §4.2.1; context: Map of Content, Partial Order.

Sources: CTfS, Exercise 4.2.1.13.

Solution: Solution 4.2.1.13

Exercise 4.2.1.22

Which of the following graphs are symmetric (admit an arrow-reversing involution $\rho$)? (a) a pictured graph; (b) the graph $G$ of (3.3); (c) the graph of Exercise 3.3.1.8; (d) the graph $G^{\prime }$ of (3.6); (e) the graph $\mathrm{Loop}$ with one vertex and one arrow; (f) the graph of Exercise 4.2.1.11.

CTfS §4.2.1; context: Map of Content, Symmetric Graph.

Sources: CTfS, Exercise 4.2.1.22.

Solution: Solution 4.2.1.22

Exercise 4.2.1.23

Let $\mathcal{C}$ be the graph indexing category ($\mathrm{src},\mathrm{tgt}:A\rightrightarrows V$) and $\mathcal{D}$ the symmetric graph indexing category (additionally $\rho :A\to A$ with $\rho \rho =\mathrm{id}$, $\rho ;\mathrm{src}=\mathrm{tgt}$, $\rho ;\mathrm{tgt}=\mathrm{src}$).

• a. How many functors $\mathcal{C}\to \mathcal{D}$ are there?
• b. Is one more “reasonable” than the others?
• c. Choose the most reasonable one, $i:\mathcal{C}\to \mathcal{D}$. For a symmetric graph $S:\mathcal{D}\to \mathbf{Set}$, $S\circ i$ is a graph; which graph? What has changed?

CTfS §4.2.1; context: Map of Content, Symmetric Graph.

Sources: CTfS, Exercise 4.2.1.23.

Solution: Solution 4.2.1.23

Exercise 4.2.2.3

Consider the schema $S$ with objects $F$ (“a father”), $C$ (“a child”), arrows $c:F\to C$ (“has as first child”), $f:C\to F$ (“has as father”) and the PED $F.c.f=F$. How many morphisms (in total) are there in the category generated by $S$?

CTfS §4.2.2; context: Map of Content, Presentation of a Category.

Sources: CTfS, Exercise 4.2.2.3.

Solution: Solution 4.2.2.3

Exercise 4.2.3.12

Let $T$ be a torus and $p,q\in T$. Since the fundamental groupoid ${\Pi }_1(T)$ is a category, what does ${\mathrm{Hom}}_{{\Pi }_1(T)}(p,q)$ represent?

CTfS §4.2.3; context: Groupoid, Map of Content.

Sources: CTfS, Exercise 4.2.3.12.

Solution: Solution 4.2.3.12

Exercise 4.2.4.4

Take the preorder $J$ of jurisdictions (ordered by inclusion $U\le V$) and let $R(V)$ be the set of all laws actually being respected by all people in $V$.

• a. Does $R:\mathrm{Ob}(J)\to \mathrm{Ob}(\mathbf{Set})$ extend to a functor $J\to \mathbf{Set}$?
• b. If instead we assign to each jurisdiction the meet (conjunction) of all laws respected there, i.e. the maximal law respected throughout, does this extend to a functor $J\to \mathbf{Prop}$?

CTfS §4.2.4; context: Contravariant Functor, Map of Content.

Sources: CTfS, Exercise 4.2.4.4.

Solution: Solution 4.2.4.4

Exercise 4.3.1.10

Let $f:X\to Y$ be a function and $C_X,C_Y:\mathbf{Grph}\to \mathbf{Set}$ the constant functors (every graph ↦ $X$, resp. $Y$; every morphism ↦ identity).

• a. Use $f$ to construct a natural transformation $C_X\Rightarrow C_Y$.
• b. What are its components?

CTfS §4.3.1; context: Constant Functor, Map of Content.

Sources: CTfS, Exercise 4.3.1.10.

Solution: Solution 4.3.1.10

Exercise 4.3.1.11

Let $\mathrm{Ar},\mathrm{Ve}:\mathbf{Grph}\to \mathbf{Set}$ be the functors taking a graph to its set of arrows, resp. vertices.

• a. What natural transformation might “taking source vertices gives a natural transformation from $\mathrm{Ar}$ to $\mathrm{Ve}$” refer to?
• b. What are its components?
• c. Would “taking target vertices” also be a natural transformation?

CTfS §4.3.1; context: Map of Content, Natural Transformation.

Sources: CTfS, Exercise 4.3.1.11.

Solution: Solution 4.3.1.11

Exercise 4.3.2.13

A finite state machine on alphabet $\Sigma$ is a functor $\mathcal{M}\to \mathbf{Set}$ with $\mathcal{M}=\mathrm{List}(\Sigma )$. What kinds of changes of state machines are made by natural isomorphisms?

CTfS §4.3.2; context: Finite State Machine, Map of Content, Natural Transformation.

Sources: CTfS, Exercise 4.3.2.13.

Solution: Solution 4.3.2.13

Exercise 4.3.3.3

Recall set-indexed sets (Definition 2.7.6.12). Given a set $A$, come up with a schema $\mathcal{A}$ whose instances are $A$-indexed sets. Is the notion of morphism between instances (natural transformations) aligned with the definition of “mapping of $A$-indexed sets”?

CTfS §4.3.3; context: C-Set, Map of Content.

Sources: CTfS, Exercise 4.3.3.3.

Solution: Solution 4.3.3.3

Exercise 4.3.3.6

Let $Y_A$ be the graph instance with one arrow $a:v_0\to v_1$. Let $I$ be the graph of Example 4.3.3.4 (arrows $f:v\to w$, $g,h:w\to x$) and $J$ the graph with arrows $i:q\to r$, $j:r\to s$, $k:s\to r$, $l:s\to t$ and an isolated vertex $u$.

• a. How many natural transformations $Y_A\Rightarrow I$ are there?
• b. How many $Y_A\Rightarrow J$?
• c. Any conjecture about natural transformations $Y_A\Rightarrow X$ for arbitrary graphs $X$?

CTfS §4.3.3; context: C-Set, Map of Content, Representable Functor.

Sources: CTfS, Exercise 4.3.3.6.

Solution: Solution 4.3.3.6

Exercise 4.3.4.5

Let $\mathbf{Fin}$ be the category of finite sets and functions, and $\mathcal{S}$ the full subcategory on the sets $\underline{n}=\{1,\dots ,n\}$. For every $X\in \mathbf{Fin}$ there is an isomorphism $p_X:X\to \underline{n}$ for a unique $n$. Find an equivalence of categories $\mathbf{Fin}\simeq \mathcal{S}$.

CTfS §4.3.4; context: Category of Finite Sets, Map of Content.

Sources: CTfS, Exercise 4.3.4.5.

Solution: Solution 4.3.4.5

Exercise 4.3.4.13

Let $1$, $2$ be the discrete categories on one and two objects. There is only one functor $2\to 1$. (a) Is it full? (b) Is it faithful?

CTfS §4.3.4; context: Full and Faithful Functor, Map of Content.

Sources: CTfS, Exercise 4.3.4.13.

Solution: Solution 4.3.4.13

Exercise 4.3.4.14

Let $0$ be the empty category and $F:0\to \mathcal{C}$ the unique functor. For general $\mathcal{C}$, is $F$ (a) full, (b) faithful, (c) an equivalence?

CTfS §4.3.4; context: Full and Faithful Functor, Map of Content.

Sources: CTfS, Exercise 4.3.4.14.

Solution: Solution 4.3.4.14

Exercise 4.3.4.16

Let ${\mathbb{Z}}_2$ be the group with two elements, as a one-object category. Are there any fully faithful functors ${\mathbb{Z}}_2\to 1$?

CTfS §4.3.4; context: Full and Faithful Functor, Map of Content.

Sources: CTfS, Exercise 4.3.4.16.

Solution: Solution 4.3.4.16

Exercise 4.4.1.5

Consider the schema $[2]$ ($0\stackrel{f_1}{\to }1\stackrel{f_2}{\to }2$) and the schema $\mathcal{C}$ with arrows $g:a\to b$, $h:b\to c$, $i:a\to c$, but without the PED $[g,h]\simeq [i]$.

• a. How many schema morphisms $[2]\to \mathcal{C}$ send $0$ to $a$?
• b. How many schema morphisms $\mathcal{C}\to [2]$ send $a$ to $0$?

CTfS §4.4.1; context: Categories and Schemas are Equivalent, Map of Content.

Sources: CTfS, Exercise 4.4.1.5.

Solution: Solution 4.4.1.5

Exercise 4.4.1.6

Let $L_n$ be the schema $\mathrm{Loop}$ (one vertex $s$, one arrow $f$) with the PED $f^{n+1}\simeq f^n$, and let $1$ be the schema with one vertex and no arrows. (a) Is $1\cong L_1$ in $\mathbf{Sch}$? (b) Is it isomorphic to any other $L_n$?

CTfS §4.4.1; context: Categories and Schemas are Equivalent, Map of Content.

Sources: CTfS, Exercise 4.4.1.6.

Solution: Solution 4.4.1.6

Exercise 4.4.1.7

With $L_n$ as in Exercise 4.4.1.6: what is (a) $|{\mathrm{Hom}}_{\mathbf{Sch}}(L_3,L_5)|$, (b) $|{\mathrm{Hom}}_{\mathbf{Sch}}(L_5,L_3)|$? (Hint: $|{\mathrm{Hom}}_{\mathbf{Sch}}(L_4,L_9)|=8$.)

CTfS §4.4.1; context: Categories and Schemas are Equivalent, Map of Content, Start Here.

Sources: CTfS, Exercise 4.4.1.7.

Solution: Solution 4.4.1.7

Exercise 4.5.1.4

Consider $(\mathbb{N},\le )$ and $(\mathbb{N},\mid )$ (divisibility: $a\mid b$ iff $an=b$ for some $n\in \mathbb{N}$), and their product order $(X,⪯)=(\mathbb{N},\le )\times (\mathbb{N},\mid )$. Which are true: $(2,4)⪯(3,4)$? $(2,4)⪯(3,5)$? $(2,4)⪯(8,0)$? $(2,4)⪯(0,0)$?

CTfS §4.5.1; context: Divisibility Order, Map of Content.

Sources: CTfS, Exercise 4.5.1.4.

Solution: Solution 4.5.1.4

Exercise 4.5.1.15

Let $f:\mathbb{R}\to \mathbb{R}$ be a function, e.g. $f(x)=x+7$. Its graph is a curve in ${\mathbb{R}}^2=\mathbb{R}\times \mathbb{R}$, understood as a function $F:\mathbb{R}\to {\mathbb{R}}^2$.

• a. Given $x\in \mathbb{R}$, what are the coordinates of $F(x)$?
• b. Obtain $F$ using the universal property of products.

CTfS §4.5.1; context: Map of Content, Product.

Sources: CTfS, Exercise 4.5.1.15.

Solution: Solution 4.5.1.15

Exercise 4.5.2.5

Let $f:A\to A$ in a category $\mathcal{C}$. Consider the two diagrams: the infinite chain $A\stackrel{f}{\to }A\stackrel{f}{\to }A\stackrel{f}{\to }\cdots$, and the single loop $f$ at $A$.

• a. Should these have the same indexing category?
• b. If so, what allows the pictures to look different?
• c. If not, what coincidence makes them look so alike?

CTfS §4.5.2; context: Diagram, Map of Content.

Sources: CTfS, Exercise 4.5.2.5.

Solution: Solution 4.5.2.5

Exercise 4.5.2.9

Let ${\mathcal{C}}_0=0$ be the empty category and ${\mathcal{C}}_{n+1}=({\mathcal{C}}_n{)}^{◃}$. Draw ${\mathcal{C}}_4$.

CTfS §4.5.2; context: Cone Category, Map of Content, Simplex Category.

Sources: CTfS, Exercise 4.5.2.9.

Solution: Solution 4.5.2.9

Exercise 4.5.2.10

Let $\mathcal{C}$ be the graph indexing schema $A\rightrightarrows V$. What is ${\mathcal{C}}^{◃}$, and how does it compare to the equalizer-like shape (4.18)?

CTfS §4.5.2; context: Cone Category, Map of Content.

Sources: CTfS, Exercise 4.5.2.10.

Solution: Solution 4.5.2.10

Exercise 4.5.3.12

Let $M=(\mathrm{List}(\{a,b\}),[],++)$ be the free monoid on $\{a,b\}$, viewed as a one-object category. (a) Does it have an initial object? (b) A terminal object?

CTfS §4.5.3; context: Map of Content, Terminal Object.

Sources: CTfS, Exercise 4.5.3.12.

Solution: Solution 4.5.3.12

Exercise 4.5.3.13

Let $K_S$ be the indiscrete category on a set $S$ of objects (exactly one morphism between any two objects). (a) Does $K_S$ have an initial object? (b) A terminal object?

CTfS §4.5.3; context: Codiscrete Category, Map of Content.

Sources: CTfS, Exercise 4.5.3.13.

Solution: Solution 4.5.3.13

Exercise 4.5.3.19

Let $I$ be the graph indexing category.

• a. What is $I^{◃}$?
• b. Let $G:I\to \mathbf{Set}$ be the graph of Example 3.3.1.2. Give an example of an object of ${\mathbf{Set}}_{/G}$ (a cone over $G$).
• c. What is the name of the limit of $G$?

CTfS §4.5.3; context: Cone Category, Map of Content.

Sources: CTfS, Exercise 4.5.3.19.

Solution: Solution 4.5.3.19

Exercise 4.6.2.5

A finite state machine is a functor $F:\mathcal{M}\to \mathbf{Set}$ from the one-object category $\mathcal{M}=\mathrm{List}(\{a,b\})$ (two loops $a,b$), recorded by the action table of Example 3.1.3.1. What is the category of elements ${\int }_{\mathcal{M}}F$? How does it relate to Figure 3.1?

CTfS §4.6.2; context: Category of Elements, Finite State Machine, Map of Content.

Sources: CTfS, Exercise 4.6.2.5.

Solution: Solution 4.6.2.5

Exercise 4.6.4.3

Let $c,c^{\prime }\in \mathrm{Ob}(\mathcal{C})$, considered as functors $1\to \mathcal{C}$. What is the comma category $(c\downarrow c^{\prime })$ of $1\stackrel{c}{\to }\mathcal{C}\stackrel{c^{\prime }}{\leftarrow }1$?

CTfS §4.6.4; context: Comma Category, Map of Content.

Sources: CTfS, Exercise 4.6.4.3.

Solution: Solution 4.6.4.3