CTfS Chapter 5 Solutions

solution

Solutions to the exercises of Category Theory for Scientists, Chapter 5 (written for this wiki; the book has none): CTfS Chapter 5 Exercises. Index: Map of Content.

Solution 5.1.1.3

Exercise 5.1.1.3

$\beta (f)$ is the unique monoid homomorphism extending $f$: it sends a list to the product of the images of its entries. So $\beta (f)([b,b,a,c])=2\cdot 2\cdot 7\cdot 2=56$ (and $\beta (f)([])=1$) (Free-Forgetful Adjunction, Free Monoid).

Sources: CTfS, Exercise 5.1.1.3; see Free-Forgetful Adjunction, Map of Content.

Solution 5.1.1.6

Exercise 5.1.1.6

• Left adjoint $\mathrm{Disc}$: a set $S$ ↦ the discrete graph with vertex set $S$ and no arrows. A graph map $\mathrm{Disc}(S)\to G$ is just a function $S\to V_G$, since there are no arrows to preserve.
• Right adjoint $\mathrm{Cod}$: $S$ ↦ the “complete” graph with vertices $S$ and exactly one arrow $s\to s^{\prime }$ for every ordered pair, including a loop at each vertex, i.e. arrows $S\times S$ with $\mathrm{src}={\pi }_1$, $\mathrm{tgt}={\pi }_2$. A graph map $G\to \mathrm{Cod}(S)$ is just a function $V_G\to S$, because every arrow has a unique possible image.

So $\mathrm{Disc}⊣U⊣\mathrm{Cod}$ (Adjunction).

Sources: CTfS, Exercise 5.1.1.6; see Adjunction, Map of Content.

Solution 5.1.1.9

Exercise 5.1.1.9

$p={\pi }_0$, the set of connected components: objects of $\mathcal{C}$ modulo the equivalence relation generated by “there is a morphism $c\to c^{\prime }$“. A functor $\mathcal{C}\to \mathrm{Disc}(S)$ must send every morphism to an identity, so it is constant on connected components, i.e. a function ${\pi }_0(\mathcal{C})\to S$. Hint check: functors $[1]\to \mathrm{Disc}(\underline{2})$ are the 2 constant ones, and functions ${\pi }_0([1])=\{\ast \}\to \underline{2}$ are 2 ✓ (the set of objects would give 4). So ${\pi }_0⊣\mathrm{Disc}⊣\mathrm{Ob}⊣\mathrm{Ind}$ (Adjunction).

Sources: CTfS, Exercise 5.1.1.9; see Adjunction, Map of Content.

Solution 5.1.4.5

Exercise 5.1.4.5

• a. One: $F(f)$ must be a morphism $0\to 2$ in $[2]$, and the only one is $g;h$.
• b. ${\Delta }_F(I)=I\circ F$: table 0 is $I(0)$ with the single column $f\mapsto I(g;h)$, and table 1 is $I(2)$. So table 0 reads Am ↦ Verb, Baltimore ↦ Noun, Carla ↦ Noun, Develop ↦ Verb, Edward ↦ Noun, Foolish ↦ Adjective, Green ↦ Adjective, and table 1 is {Adjective, Noun, Verb}. The middle table (parts of speech) is dropped and the two foreign keys are composed (Data Migration Functor).

Sources: CTfS, Exercise 5.1.4.5; see Data Migration Functor, Map of Content.

Solution 5.1.4.8

Exercise 5.1.4.8

• a. For example $I_1=\{x\}$, $I_2=\{p,q\}$, $I_3=\{r\}$.
• b. ${\Sigma }_F(I)(j)$ is the colimit of $I$ over the fiber $F^{-1}(j)$, a coproduct because the fibers are discrete. So ${\Sigma }_F(I)=(I_1,I_2\bigsqcup I_3)=(\{x\},\{p,q,r\})$ (Data Migration Functor, Coproduct).

Sources: CTfS, Exercise 5.1.4.8; see Data Migration Functor, Map of Content.

Solution 5.1.4.11

Exercise 5.1.4.11

• a. For example $I_1=\{x\}$, $I_2=\{p,q\}$, $I_3=\{r\}$.
• b. ${\Pi }_F(I)=(I_1,I_2\times I_3)=(\{x\},\{(p,r),(q,r)\})$: the limit over each discrete fiber is a product. If a fiber were empty, ${\Pi }_F$ would put the empty product $\{\ast \}$ there, while ${\Sigma }_F$ would put $\varnothing$ (Data Migration Functor, Product).

Sources: CTfS, Exercise 5.1.4.11; see Data Migration Functor, Map of Content.

Solution 5.2.3.3

Exercise 5.2.3.3

• a. Take the four open quadrant-ish squares $U_1=[0,2)\times [0,2)$, $U_2=(1,3]\times [0,2)$, $U_3=[0,2)\times (1,3]$, $U_4=(1,3]\times (1,3]$ (open in $X$). The pairwise overlaps are $U_{12},U_{13},U_{24},U_{34}$ (strips) and $U_{14},U_{23}$. All the triple overlaps and the 4-fold overlap equal the central square $(1,2)\times (1,2)$. The preorder has arrows from each overlap to the sets it lies in. Temperature bounds: $R_1(x,y)=10+x$ and $R_2(x,y)=20+x+y$.
• b. For $B\subseteq A$ the restriction $\mathcal{O}(A)\to \mathcal{O}(B)$ sends $f\mapsto f{|}_B$; the bounds still hold on $B$. “Value-assignment throughout $A$” is apt: an element is a choice of temperature at every point of $A$, within the bounds. It even satisfies the sheaf condition, because compatible local assignments glue uniquely.
• c. Yes: the inclusions ${\mathcal{O}}^{\prime }(A)\hookrightarrow \mathcal{O}(A)$ commute with restriction (the restriction of a continuous function is continuous), so they form a natural transformation. ${\mathcal{O}}^{\prime }$ is a sub-presheaf, in fact a sub-sheaf, since continuity is local. See Sheaf, Presheaf.

Sources: CTfS, Exercise 5.2.3.3; see Map of Content, Sheaf.

Solution 5.3.2.5

Exercise 5.3.2.5

${\eta }_X:X\to X\bigsqcup E$ is the coproduct inclusion, meaning “return a value, no exception”. ${\mu }_X:(X\bigsqcup E)\bigsqcup E\to X\bigsqcup E$ is the identity on $X$ and on the inner copy of $E$, and sends the outer copy of $E$ to $E$ identically. Both copies of the exceptions merge: an exception raised at either stage is reported. The unit laws hold because $\mu \circ {\eta }_{TX}$ and $\mu \circ T{\eta }_X$ are both the identity of $X\bigsqcup E$. Associativity holds because both ways of flattening $((X\bigsqcup E)\bigsqcup E)\bigsqcup E$ merge all three copies of $E$. This is Haskell’s Either e. Kleisli composition short-circuits on the first exception (Maybe Monad, Monad).

Sources: CTfS, Exercise 5.3.2.5; see Map of Content, Maybe Monad.

Solution 5.3.3.5

Exercise 5.3.3.5

• a. $R_f=\{(a,b)\mid b\in f(a)\}$. Conversely a relation $R$ gives $f_R(a)=\{b\mid (a,b)\in R\}$. These are inverse bijections ${\mathrm{Hom}}_{\mathrm{Kls}}(A,B)\cong \mathcal{P}(A\times B)$.
• b. They agree: $(g{\circ }_{\mathcal{P}}f)(a)={\bigcup }_{b\in f(a)}g(b)$, so $(a,c)\in R_{g\circ f}$ iff there exists $b$ with $(a,b)\in R_f$ and $(b,c)\in R_g$, the relational composite. The identities $\eta$ are the diagonal relations. Hence $\mathrm{Kls}(\mathcal{P})\cong \mathbf{Rel}$ (Power Set Monad, Category of Relations).

Sources: CTfS, Exercise 5.3.3.5; see Map of Content, Power Set Monad.

Solution 5.3.3.6

Exercise 5.3.3.6

The disjoint union $A\bigsqcup B=\{1,2,3,a,b\}$, not the Cartesian product. The projections are the relations $A\bigsqcup B\to A$ and $A\bigsqcup B\to B$ that are the identity on the matching summand and empty on the other. A pair of relations $R\subseteq Z\times A$, $S\subseteq Z\times B$ corresponds to exactly one relation $Z\to A\bigsqcup B$, namely their union. Since $\mathbf{Rel}\cong {\mathbf{Rel}}^{\mathrm{op}}$ via transposition, this is the dual of the coproduct statement (Power Set Monad).

Sources: CTfS, Exercise 5.3.3.6; see Map of Content, Power Set Monad.

Solution 5.3.3.7

Exercise 5.3.3.7

Also $A\bigsqcup B=\{1,2,3,a,b\}$, with the inclusions (as relations) as injections. A relation out of $A\bigsqcup B$ is a pair of relations out of $A$ and out of $B$. Products and coproducts coincide, so $\mathbf{Rel}$ has biproducts, as matrices over the Booleans do (Power Set Monad, Coproduct).

Sources: CTfS, Exercise 5.3.3.7; see Map of Content, Power Set Monad.

Solution 5.4.1.4

Exercise 5.4.1.4

• a. $f:(\text{circle},\text{circle},\text{square})\to \text{triangle}$: inside a big triangle, place two small disjoint circles near the bottom corners and a small square near the top vertex, none overlapping.

• b. One way to factor it is $f=g\circ (h,{\mathrm{id}}_{\text{square}})$ with the following pieces:

  • $h:(\text{circle},\text{circle})\to \text{square}$ places two small circles side by side in a square;
  • ${\mathrm{id}}_{\text{square}}$;
  • $g:(\text{square},\text{square})\to \text{triangle}$ places a wide square along the bottom and a small square at the top.

  Composition substitutes $h$ into the first square of $g$ (after rescaling), which puts the two circles in the bottom region of the triangle and leaves the top square alone. That is a positioning of the shape of $f$. So the three morphisms $g$, $h$ and ${\mathrm{id}}_{\text{square}}$ compose to $f$. Composition is associative because nested substitution is (Operad).

Sources: CTfS, Exercise 5.4.1.4; see Map of Content, Operad.