CTfS Chapter 3 Exercises

exercise

Exercises from Category Theory for Scientists (CTfS), Chapter 3 (“Categories and functors, without admitting it”). 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 3 Solutions. Index: Map of Content.

Exercise 3.1.1.7

Recall the notion of commutativity for monoids.

• a. What is the smallest set $M$ that you can give the structure of a non-commutative monoid?
• b. What is the smallest set $M$ that you can give the structure of a monoid?

CTfS §3.1.1; context: Map of Content, Monoid.

Sources: CTfS, Exercise 3.1.1.7.

Solution: Solution 3.1.1.7

Exercise 3.1.1.13

Let $\{\ast \}$ be a one-element set.

• a. What is the free monoid generated by $\{\ast \}$?
• b. What is the free monoid generated by $\varnothing$?

CTfS §3.1.1; context: Free Monoid, Map of Content.

Sources: CTfS, Exercise 3.1.1.13.

Solution: Solution 3.1.1.13

Exercise 3.1.1.18

Consider the buffer of Application 3.1.1.17, but of size 3 instead of 32. Using Definition 3.1.1.14, show that with the “overwrite” relations ${\sim }_1$, $[a,b,c,d,e,f]=[a,b,f]$, and with the “discard” relations ${\sim }_2$, $[a,b,c,d,e,f]=[a,b,c]$.

CTfS §3.1.1; context: Map of Content, Presentation of a Monoid.

Sources: CTfS, Exercise 3.1.1.18.

Solution: Solution 3.1.1.18

Exercise 3.1.1.23

(Classify the cyclic monoids.) Come up with a naming system such that every cyclic monoid (one generator) gets a name, no two non-isomorphic cyclic monoids get the same name, and every name refers to a cyclic monoid. (Hint: the monoids of Example 3.1.1.22 might suggest "$\mathbb{N}\bigsqcup \{\infty \}$" — on the right track, but not correct.)

CTfS §3.1.1; context: Map of Content, Presentation of a Monoid.

Sources: CTfS, Exercise 3.1.1.23.

Solution: Solution 3.1.1.23

Exercise 3.1.2.4

• a. Realize $T:=[0,12)\subseteq \mathbb{R}$ as the coequalizer of a pair of arrows $\mathbb{R}\to \mathbb{R}$.
• b. For any $x\in \mathbb{R}$, realize the map $x\cdot -:T\to T$ (“advance the clock by $x$ hours”) using the universal property of coequalizers.
• c. Prove that it is an action.

CTfS §3.1.2; context: Map of Content, Monoid Action.

Sources: CTfS, Exercise 3.1.2.4.

Solution: Solution 3.1.2.4

Exercise 3.1.2.13

For the functions $\phi :\{\text{actions of }\mathrm{List}(\Sigma )\text{ on }S\}\to \mathrm{Hom}(\Sigma \times S,S)$ (restrict to one-letter words) and $\psi$ in the other direction (extend by recursion):

• a. Show that for any $f:\Sigma \times S\to S$, $\psi (f):\mathrm{List}(\Sigma )\times S\to S$ is an action.
• b. Show that $\phi$ and $\psi$ are mutually inverse.

CTfS §3.1.2; context: Finite State Machine, Map of Content.

Sources: CTfS, Exercise 3.1.2.13.

Solution: Solution 3.1.2.13

Exercise 3.1.4.7

Let $M=(\mathbb{N},0,+)$, $N=({\mathbb{R}}_{\ge 0},0,+)$ and $P=({\mathbb{R}}_{>0},1,\ast )$. Can you think of nontrivial monoid homomorphisms $M\to N$, $M\to P$, $N\to P$, $N\to M$, $P\to N$?

CTfS §3.1.4; context: Map of Content, Monoid.

Sources: CTfS, Exercise 3.1.4.7.

Solution: Solution 3.1.4.7

Exercise 3.1.4.15

Let $\mathbb{N}$ be the free monoid on one generator, $\Sigma =\{a,b\}$, $S=\{\text{State }0,1,2\}$, and $f:\mathbb{N}\to \mathrm{List}(\Sigma )$ the homomorphism with $1\mapsto [a,b,b]$. Restrict the action $\alpha$ of Example 3.1.3.1 along $f$ to an action ${\Delta }_f(\alpha )$ of $\mathbb{N}$ on $S$. Write down its action table.

CTfS §3.1.4; context: Finite State Machine, Map of Content.

Sources: CTfS, Exercise 3.1.4.15.

Solution: Solution 3.1.4.15

Exercise 3.2.1.8

In Exercise 3.1.1.23 you classified the cyclic monoids. Which of them are groups?

CTfS §3.2.1; context: Map of Content, Presentation of a Monoid.

Sources: CTfS, Exercise 3.2.1.8.

Solution: Solution 3.2.1.8

Exercise 3.2.1.14

• a. Consider the $U(1)$ action on ${\mathbb{R}}^3$ by rotation about the $z$-axis (Example 3.2.1.10). Describe the set of orbits.
• b. What are the orbits of the permutation group ${\Sigma }_{\{1,2,3\}}$ acting on $\{1,2,3\}$?

CTfS §3.2.1; context: Group Action, Map of Content.

Sources: CTfS, Exercise 3.2.1.14.

Solution: Solution 3.2.1.14

Exercise 3.2.1.15

Let $G$ act on $X$. Is “being in the same orbit” an equivalence relation on $X$?

CTfS §3.2.1; context: Equivalence Relation, Group Action, Map of Content.

Sources: CTfS, Exercise 3.2.1.15.

Solution: Solution 3.2.1.15

Exercise 3.3.2.4

Let $G$ be a graph and ${\mathrm{Path}}_G$ its set of paths. Someone claims there is a monoid structure on ${\mathrm{Path}}_G$ with multiplication given by concatenation. Are they correct? (Hint: what should the identity element be?)

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

Sources: CTfS, Exercise 3.3.2.4.

Solution: Solution 3.3.2.4

Exercise 3.3.3.5

A graph homomorphism $f:G\to G^{\prime }$ induces $\mathrm{Path}(f):\mathrm{Path}(G)\to \mathrm{Path}(G^{\prime })$.

• a. Does $\mathrm{Path}(f)$ carry paths of length $n$ to paths of length $n$, or can lengths change?
• b. If $f_0,f_1$ are injective, is $\mathrm{Path}(f)$ injective?
• c. If $f_0,f_1$ are surjective, is $\mathrm{Path}(f)$ surjective?

CTfS §3.3.3; context: Graph Homomorphism, Map of Content.

Sources: CTfS, Exercise 3.3.3.5.

Solution: Solution 3.3.3.5

Exercise 3.3.3.6

For a graph $(V,A,\mathrm{src},\mathrm{tgt})$ let $i=⟨\mathrm{src},\mathrm{tgt}⟩:A\to V\times V$. Is commutativity of the single square $i^{\prime }\circ f_1=(f_0\times f_0)\circ i$ equivalent to commutativity of the two squares ${\mathrm{src}}^{\prime }{f}_1=f_0\mathrm{src}$ and ${\mathrm{tgt}}^{\prime }{f}_1=f_0\mathrm{tgt}$?

CTfS §3.3.3; context: Graph Homomorphism, Map of Content.

Sources: CTfS, Exercise 3.3.3.6.

Solution: Solution 3.3.3.6

Exercise 3.3.3.9

A relation on $\mathbb{R}$ is a subset of $\mathbb{R}\times \mathbb{R}$. Choose $\epsilon >0$ and draw the relation ”$x$ is within $\epsilon$ of $y$“.

CTfS §3.3.3; context: Map of Content, Relation.

Sources: CTfS, Exercise 3.3.3.9.

Solution: Solution 3.3.3.9

Exercise 3.4.1.8

• a. List all the preorder relations on $\{1,2\}$.
• b. For $n\in \mathbb{N}$, how many linear orders exist on $\{1,\dots ,n\}$?
• c. Does your formula work for $n=0$?

CTfS §3.4.1; context: Map of Content, Preorder.

Sources: CTfS, Exercise 3.4.1.8.

Solution: Solution 3.4.1.8

Exercise 3.4.1.12

True or false: a partial order is a preorder that has no cliques. (If false, is there a “nearby” true statement?)

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

Sources: CTfS, Exercise 3.4.1.12.

Solution: Solution 3.4.1.12

Exercise 3.4.1.14

Let $X$ be the set of people and $R\subseteq X\times X$ the relation with $(x,y)\in R$ if $x$ is the child of $y$. Describe the preorder generated by $R$.

CTfS §3.4.1; context: Map of Content, Preorder.

Sources: CTfS, Exercise 3.4.1.14.

Solution: Solution 3.4.1.14

Exercise 3.4.4.3

• a. Would you guess that the taxonomic order of biological species has all meets?
• b. All joins?
• c. What would a meet or a join mean?

CTfS §3.4.4; context: Join, Map of Content.

Sources: CTfS, Exercise 3.4.4.3.

Solution: Solution 3.4.4.3

Exercise 3.4.4.7

Let $P$ be the set of people and $I$ the set of pieces of information known by the government. For $J\subseteq I$ let $K(J)\subseteq P$ be the set of people who need to know every piece of information in $J$, and let $S=\{K(J)\mid J\subseteq I\}$, ordered by inclusion.

• a. Is $(P,\le )$ a preorder? If not, find a nearby preorder.
• b. If $J_1\subseteq J_2$, do we have $K(J_1)\subseteq K(J_2)$, $K(J_2)\subseteq K(J_1)$, or neither?
• c. Should $(S,\subseteq )$ have all meets?
• d. Should it have all joins?

CTfS §3.4.4; context: Join, Map of Content.

Sources: CTfS, Exercise 3.4.4.7.

Solution: Solution 3.4.4.7

Exercise 3.4.4.11

Let $S$ be the set of open subsets of the earth, and assign to each region $s$ the interval $T(s)=[a,b]$ of recorded temperatures (low and high) throughout $s$. Order intervals by inclusion.

• a. Is $T:S\to V$ a morphism of orders?
• b. Does it preserve meets or joins? (Hint: not both.)

CTfS §3.4.4; context: Join, Map of Content.

Sources: CTfS, Exercise 3.4.4.11.

Solution: Solution 3.4.4.11

Exercise 3.5.2.12

Is there a nontrivial PED on $\mathrm{Loop}$ that holds for the data of Example 3.5.2.9? If so, what is it, and how many equivalence classes of paths in $\mathrm{Loop}$ remain after imposing it?

The data (a discrete dynamical system $f$): $A\mapsto B$, $B\mapsto C$, $C\mapsto C$, $D\mapsto B$, $E\mapsto C$, $F\mapsto G$, $G\mapsto H$, $H\mapsto G$.

CTfS §3.5.2; context: Discrete Dynamical System, Map of Content.

Sources: CTfS, Exercise 3.5.2.12.

Solution: Solution 3.5.2.12

Exercise 3.5.2.13

Let $P$ be a chess-playing program which, given any position (including whose turn it is), makes a move.

• a. Is this an example of a discrete dynamical system?
• b. How do the rules for ending the game in a win or draw play out in this model?

CTfS §3.5.2; context: Discrete Dynamical System, Map of Content.

Sources: CTfS, Exercise 3.5.2.13.

Solution: Solution 3.5.2.13

Exercise 3.5.2.18

Consider the olog with $F$ = “a father”, $C$ = “a child”, $f:F\to C$ “has as first child” and $h:C\to F$ “has as father”. What path equivalence declarations would be appropriate?

CTfS §3.5.2; context: Database Schema, Map of Content.

Sources: CTfS, Exercise 3.5.2.18.

Solution: Solution 3.5.2.18

Exercise 3.5.3.2

Consider the schema with objects “a self-email”, “an email”, “a person”, arrows is: self-email → email and is sent by, is sent to: email → person, and the fact “for any self-email $x$, the sender of $x$ equals its recipient”. An instance (3.19) has emails Em1206 (Bob → Sue), Em1207 (Carl → Carl), Em1208 (Sue → Martha), Em1209 (Chris → Bob), Em1210 (Chris → Chris), Em1211 (Julia → Julia), Em1212 (Martha → Chris); self-emails SEm1207, SEm1210, SEm1211 mapping to Em1207, Em1210, Em1211; and persons Bob, Carl, Chris, Julia, Martha, Sue.

• a. What is the set $PK(\text{an email})$?
• b. What is $PK(\text{a person})$?
• c. What is the function $FK(\text{is sent by})$?
• d. Interpret the fact as a PED. Is it satisfied by the instance?

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

Sources: CTfS, Exercise 3.5.3.2.

Solution: Solution 3.5.3.2

Exercise 3.5.3.5

Suppose $M$ is a monoid and some instance of it (an action table) is written out. What evidence in the table might suggest that $M$ is a group?

CTfS §3.5.3; context: Map of Content, Monoid Action.

Sources: CTfS, Exercise 3.5.3.5.

Solution: Solution 3.5.3.5