§ SOLUTIONS FOR <REF>.

Suppose we have the preorders

\[
\begin{tikzpicture}
\node (cat) {category};
\node[below right=1 of cat] (pos) {preorder};
\node[below left=1 of cat] (mon) {monoid};
\draw[->] (pos) -- (cat);
\draw[->] (mon) -- (cat);
\node[draw, fit=(cat) (pos) (mon)] (X) {};
\node[left=0 of X] {$\cat{X}\coloneqq$};
\node[right=2 of pos] (0) {nothing};
\node at (0|-cat) (1) {this book};
\draw[->] (0) -- (1);
\node[draw, fit=(0) (1)] (Y) {};
\node[left=0 of Y] {$\cat{Y}\coloneqq$};
\end{tikzpicture}
\]

* Draw the Hasse diagram for the preorder $\cat{X}\op\times\cat{Y}$.

* Write down a profunctor $\Lambda\colon\cat{X} \tickar \cat{Y}$ and, reading
$\Lambda(x,y)=\true$ as “my aunt can explain a $x$ given $y$,” give an
interpretation of the fact that the preimage of $\true$ forms an upper set in

* The Hasse diagram for $\cat{X}\op \times \cat{Y}$ is shown here (ignore the colors):

\[
\begin{tikzpicture}[font=\scriptsize,xscale =2]
\node (a1) at (0,0) {(category, nothing)};
\node[blue] (c1) at (-1,1) {(monoid, nothing)};
\node (b1) at (1,1) {(preorder, nothing)};
\node[blue] (a2) at (0,2) {(category, this book)};
\node[blue] (c2) at (-1,3) {(monoid, this book)};
\node[blue] (b2) at (1,3) {(preorder, nothing)};
\node[draw, fit=(a1) (c1) (b1) (b2)] (A) {};
\draw[->] (a1) to (c1);
\draw[->] (a1) to (a2);
\draw[->] (a1) to (b1);
\draw[->] (a2) to (c2);
\draw[->] (a2) to (b2);
\draw[->] (c1) to (c2);
\draw[->] (b1) to (b2);
\end{tikzpicture}
\]

* There is a profunctor $\Lambda\colon \cat{X} \tickar \cat{Y}$, i.e. a functor $\cat{X}\op\times\cat{Y}\to\BB$,
such that, in the picture above, blue is sent to true and black is sent to false, i.e.
\begin{align*}
\Lambda(\mbox{monoid, nothing})& = \Lambda(\mbox{monoid, this book}) \\
&=\Lambda(\mbox{preorder, this book})
&=\Lambda(\mbox{category, this book})
=\true \\
\Lambda(\mbox{preorder, nothing}) &=\Lambda(\mbox{category, nothing})
\end{align*}

The preorder $\cat{X}\op\times\cat{Y}$ describes tasks in decreasing difficulty. For example, (we hope) it is easier for my aunt to explain a monoid given this
book than for her to explain a monoid without this book. The profunctor
$\Lambda$ describes possible states of knowledge for my aunt: she can describe monoids without help, categories with help from the book, etc. It is an upper set
because we assume that if she can do a task, she can also do any easier task.

Show that $\imp$ as defined in <ref> indeed satisfies <ref>.

We've done this one before! We hope you remembered how to do it. If not, see

Show that a $\cat{V}$-profunctor (<ref>) is
the same as a function $\Phi\colon\Ob(\cat{X})\times\Ob(\cat{Y})\to V$ such that
for any $x,x'\in\cat{X}$ and $y,y'\in\cat{Y}$ the following inequality holds in

\[
\cat{X}(x',x)\otimes\Phi(x,y)\otimes\cat{Y}(y,y')\leq\Phi(x',y').

\]

Recall from <ref> that a $\cat{V}$-functor $\Phi\colon
\cat{X}\op \times \cat{Y} \to \cat{V}$ is a function $\Phi\colon\Ob(\cat{X}\op \times
\cat{Y}) \to \Ob(\cat{V})$ such that for all $(x,y)$ and $(x',y')$ in
$\cat{X}\op\times \cat{Y}$ we have

\[
(\cat{X}\op \times \cat{Y})\big((x,y),(x',y')\big) \le
\cat{V}\big(\Phi(x,y),\Phi(x',y')\big).
\]

Using the definitions of product $\cat{V}$-category (<ref>)
and opposite $\cat{V}$-category (<ref>) on the left hand side,
and using <ref>, which describes how we are
viewing the quantale $\cat{V}$ as enriched over itself, on the right hand side,
this unpacks to

\[
\cat{X}(x',x) \otimes \cat{Y}(y,y') \le \Phi(x,y) \multimap \Phi(x',y')
\]

Using symmetry of $\otimes$ and the definition of hom-element, <ref>, we see that
$\Phi$ is a profunctor if and only if

\[
\cat{X}(x',x)\otimes\Phi(x,y)\otimes\cat{Y}(y,y')\leq\Phi(x',y').
\]

Is it true that a $\Bool$-profunctor, as in <ref> is exactly the same as a feasibility relation, as in <ref>, once you peel back all the jargon? Or is there some subtle difference?

Yes, since a $\Bool$-functor is exactly the same as a monotone map, the definition of
$\Bool$-profunctor and that of feasibility relation line up perfectly!

We can express $\Phi$ as a matrix where the $(m,n)$th entry is the value of
$\Phi(m,n)\in \BB$. Fill out the $\Bool$-matrix:

\[
\begin{array}{c|ccccc}
\Phi&a&b&c&d&e\\\hline
\end{array}

\]

The feasibility matrix for $\Phi$ is

\[
\begin{array}{c|ccccc}
\Phi&a&b&c&d&e\\\hline
\end{array}
\]

Fill out the $\Cost$-matrix:

\[
\begin{array}{c|ccc}
\Phi&x&y&z\\\hline
\end{array}

\]

The $\Cost$-matrix for $\Phi$ is

\[
\begin{array}{c|ccc}
\Phi&x&y&z\\\hline
\end{array}
\]

Calculate $M_X^4*M_\Phi*M_Y^3$, remembering to do matrix multiplication according to the $(\min,+)$-formula for matrix multiplication in the quantale $\Cost$; see <ref>.

Your answer should agree with what you got in <ref>; does it?

\begin{align*}
\Phi = M^3_X\ast M_\Phi \ast M_Y^2
\begin{pmatrix}
\end{pmatrix}
\begin{pmatrix}
\infty&\infty&\infty\\
\infty&\infty&\infty\\
\infty&9&\infty
\end{pmatrix}
\begin{pmatrix}
\end{pmatrix} \\
\begin{pmatrix}
\end{pmatrix}
\begin{pmatrix}
\end{pmatrix} \\
\begin{pmatrix}
\end{pmatrix}
\end{align*}

In the above diagram, the node (g/n, funny) has no dashed blue arrow emerging
from it. Is this valid? If so, what does it mean?

Yes, this is valid: it just means that the profunctor $\Phi\colon (T \times E)
\tickar \$$ does not relate (good-natured, funny) to any element of $\$$. More
formally, it means that $\Phi((\mbox{good-natured, funny}),p) = \false$ for all
$p \in \$ = \{\mbox{\$100K, \$500K, \$1M}\}$. We can interpret this to mean that
it is not feasible to produce a good-natured, funny movie for any of the cost
options presented—so at least not for less than a million dollars.

Consider the $\Cost$-profunctors $\Phi\colon\cat{X}\tickar\cat{Y}$ and $\Psi\colon\cat{Y}\tickar\cat{Z}$ shown below:

\[
\begin{tikzpicture}[font=\scriptsize, x=1cm, every label/.style={font=\tiny}]
\node[label={[above=-5pt]:$A$}] (a) {$\bullet$};
\node[right=1 of a, label={[above=-5pt]:$B$}] (b) {$\bullet$};
\node[below=1 of a, label={[below=5pt]:$C$}] (c) {$\bullet$};
\node[right=1 of c, label={[below=5pt]:$D$}] (d) {$\bullet$};
\draw[->] (c) to node[above left=-1pt and -1pt] {3} (b);
\draw[bend right,->] (a) to node[left] {3} (c);
\draw[bend left,->] (d) to node[below] {4} (c);
\draw[bend right,->] (b) to node[above] {2} (a);
\draw[bend left,->] (b) to node[right] {5} (d);
\node[draw, inner sep=15pt, fit=(a) (b) (c) (d)] (X) {};
\node[above=0 of X, font=\normalsize] {$\cat{X}\coloneqq$};
\node[right=4 of a, label={[above=-5pt]:$x$}] (x) {$\bullet$};
\node[below=1 of x, label={[below=5pt]:$y$}] (y) {$\bullet$};
\node[label={[right=-5pt]:$z$}] at ($(x)!.5!(y)+(1.5cm,0)$) (z) {$\bullet$};
\draw[bend left,->] (y) to node[left] {3} (x);
\draw[bend left,->] (x) to node[right] {4} (y);
\draw[bend left,->] (x) to node[above] {3} (z);
\draw[bend left,->] (z) to node[below right=-1pt and -1pt] {4} (y);
\node[draw, inner sep=15pt, fit=(x) (y) (z.west)] (Y) {};
\node[above=0 of Y, font=\normalsize] {$\cat{Y}\coloneqq$};
\node [right=3.5 of x, label={[above=-5pt]:$p$}] (p) {$\bullet$};
\node [right=1 of p, label={[above=-5pt]:$q$}] (q) {$\bullet$};
\node [below=1 of q, label={[below=5pt]:$r$}]  (r) {$\bullet$};
\node [left=1 of r, label={[below=5pt]:$s$}]   (s) {$\bullet$};
\draw[bend left,->] (p) to node[above] {2} (q);
\draw[bend left,->] (q) to node[right] {2} (r);
\draw[bend left,->] (r) to node[below] {1} (s);
\draw[bend left,->] (s) to node[left]  {1} (p);
\node[draw, inner sep=15pt, fit=(p) (r)] (Z) {};
\node[above=0 of Z, font=\normalsize] {$\cat{Z}\coloneqq$};
\begin{scope}[->, dashed, blue]
\draw[bend left] (b) to node[above] {11} (x);
\draw[bend right] (d) to node[below] {9} (y);
\draw[bend left=20pt] (z) to node[above] {4} (p);
\draw[bend right=20pt] (z) to node[below] {4} (s);
\draw[bend right=20pt] (y) to node[below] {0} (r);
\end{scope}
\end{tikzpicture}
\]

Fill in the matrix:

\[
\begin{array}{c|cccc}
\Phi\cp\Psi&p&q&r&s\\\hline
\end{array}

\]

There are a number of methods that can be used to get the correct answer. One
way that works well for this example is to search for the shortest paths on the
diagram: it so happens that all the shortest paths go through the bridges from
$D$ to $y$ and $y$ to $r$, so in this case $(\Phi\cp\Psi)(-,-) =
\cat{X}(-,D)+9+\cat{Z}(r,-)$. This gives:

\[
\begin{array}{c|cccc}
\Phi\cp\Psi&p&q&r&s\\\hline
\end{array}
\]

A more methodical way is to use matrix multiplication. Here's one way you might
do the multiplication, using a few tricks.

\begin{align*}
\Phi\cp\Psi &= (M_X^3 \ast M_\Phi \ast M_Y^2) \ast (M_Y^2 \ast M_\Psi \ast M_Z^3) \\
&= M_X^3 \ast M_\Phi \ast M_Y^4 \ast M_\Psi \ast M_Z^3 \\
&= (M_X^3 \ast M_\Phi \ast M_Y^2) \ast M_\Psi \ast M_Z^3 \\
&= \Phi \ast M_\Psi \ast M_Z^3 \\
\begin{pmatrix}
\end{pmatrix}
\begin{pmatrix}
\infty&\infty&\infty&\infty\\
\infty&\infty&0&\infty\\
\end{pmatrix}
\begin{pmatrix}
\end{pmatrix} \\
\begin{pmatrix}
\end{pmatrix}
\begin{pmatrix}
\infty&\infty&\infty&\infty\\
\end{pmatrix} \\
\begin{pmatrix}
\end{pmatrix}
\end{align*}

Choose a not-too-simple $\Cost$-category $\cat{X}$. Give a bridge-style diagram for the unit profunctor $U_{\cat{X}}\colon\cat{X}\tickar\cat{X}$.

We choose the $\Cost$-category $\cat{X}$ from
<ref>. The unit profunctor $U_\cat{X}$ on $\cat{X}$ is
described by the bridge diagram

\[
\begin{tikzpicture}[font=\scriptsize, x=1cm, every label/.style={font=\tiny}]
\node[label={[above=-5pt]:$A$}] (a) {$\bullet$};
\node[right=1 of a, label={[above=-5pt]:$B$}] (b) {$\bullet$};
\node[below=1 of a, label={[below=5pt]:$C$}] (c) {$\bullet$};
\node[right=1 of c, label={[below=5pt]:$D$}] (d) {$\bullet$};
\draw[->] (c) to node[above left=-1pt and -1pt] {3} (b);
\draw[bend right,->] (a) to node[left] {3} (c);
\draw[bend left,->] (d) to node[below] {4} (c);
\draw[bend right,->] (b) to node[above] {2} (a);
\draw[bend left,->] (b) to node[right] {5} (d);
\node[draw, inner sep=15pt, fit=(a) (b) (c) (d)] (X) {};
\node[right=4 of b, label={[above=-5pt]:$A$}] (a1) {$\bullet$};
\node[right=1 of a1, label={[above=-5pt]:$B$}] (b1) {$\bullet$};
\node[below=1 of a1, label={[below=5pt]:$C$}] (c1) {$\bullet$};
\node[right=1 of c1, label={[below=5pt]:$D$}] (d1) {$\bullet$};
\draw[->] (c1) to node[above left=-1pt and -1pt] {3} (b1);
\draw[bend right,->] (a1) to node[left] {3} (c1);
\draw[bend left,->] (d1) to node[below] {4} (c1);
\draw[bend right,->] (b1) to node[above] {2} (a1);
\draw[bend left,->] (b1) to node[right] {5} (d1);
\node[draw, inner sep=15pt, fit=(a1) (b1) (c1) (d1)] (X) {};
\draw[->, dashed, blue, bend left=20] (a) to node[above,pos=.47] {0} (a1);
\draw[->, dashed, blue, bend left=20] (b) to node[above,pos=.53] {0} (b1);
\draw[->, dashed, blue, bend right=20] (c) to node[below,pos=.47] {0} (c1);
\draw[->, dashed, blue, bend right=20] (d) to node[below,pos=.53] {0} (d1);
\end{tikzpicture}
\]

* Justify each of the four steps $(=, \leq, \leq, =)$ in

* In the case $\cat{V}=\Bool$, we can directly show each of the four steps
in <ref> is actually an equality. How?

* Justify each of the three steps $(=,\leq,\leq)$ in <ref>.

* The first equality is the unitality of $\cat{V}$
(<ref>(b)). The second step uses the monotonicity of
$\otimes$ (<ref>(a)) applied to the inequalities $I \le
\cat{P}(p,p)$ (the identity law for $\cat{P}$ at $p$,
<ref>(a)) and $\Phi(p,q) \le \Phi(p,q)$ (reflexivity of
preorder $\cat{V}$, <ref>(a)). The third step uses the definition
of join: for all $x$ and $y$, since any $x \le x$, we have $x \le x \vee y$. The
final equality is just the definition of profunctor composition,

* Note that in $\Bool$, $I=\true$. Since the identity law at $p$ says $\true
\le \cat{P}(p,p)$, and $\true$ is the largest element of the preorder $\Bool$, we
thus have $\cat{P}(p,p)=\true$ for all $p$. This shows that the first inequality
in <ref> is an equality.

The second inequality is more involved. Note that by the above, we can assume
the left hand side of the inequality is equal to $\Phi(p,q)$. We split into two
cases. Suppose $\Phi(p,q)= \true$. Then, again since $\true$ is the largest element of
$\BB$, we must have equality.

Next, suppose $\Phi(p,q) = \false$. Note that since $\Phi$ is a monotone map
$\cat{P}\op \times \cat{Q} \to \Bool$, if $p \le p_1$ in $\cat{P}$, then
$\Phi(p_1,q) \le \Phi(p,q)$ in $\Bool$. Thus if $\cat{P}(p,p_1) = \true$ then
$\Phi(p_1,q) = \Phi(p,q) =\false$. This implies that for all $p_1 \in \cat{P}$,
we have either $\cat{P}(p,p_1) =\false$ or $\Phi(p_1,q) = \false$, and hence
$\bigvee_{p_1\in \cat{P}} \cat{P}(p,p_1) \wedge \Phi(p_1,q) = \bigvee_{p_1 \in
\cat{P}} \false = \false$.

Thus, in either case, we see that $\Phi(p,q) = \bigvee_{p_1\in \cat{P}}
\cat{P}(p,p_1) \wedge \Phi(p_1,q)$, as required.

* The first equation is unitality in monoidal categories, $v\otimes I=v$ for any $v\in V$. The second is that $I\leq\cat{Q}(q,q)$ by unitality of enriched categories, see <ref>, together with monotonicity of monoidal product: $v_1\leq v_2$ implies $v\otimes v_1\leq v\otimes v_2$. The third was shown in <ref>.

Prove <ref>. (Hint: remember to use the fact that $\cat{V}$
is skeletal.)

This is very similar to <ref>: we exploit the associativity of
$\otimes$. Note, however, we also require $\cat{V}$ to be symmetric monoidal
closed, since this implies the distributivity of $\otimes$ over $\vee$
(<ref> 2), and $\cat{V}$ to be skeletal,
so we can turn equivalences into equalities.

\begin{align*}
((\Phi\cp \Psi) \cp \Upsilon)(p,s)
&= \bigvee_{r \in \cat{R}} \bigg(\bigvee_{q \in \cat{Q}} \Phi(p,q) \otimes
\Psi(q,r)\bigg) \otimes \Upsilon(r,s) \\
&= \bigvee_{r \in \cat{R}, q \in \cat{Q}} \Phi(p,q) \otimes
\Psi(q,r) \otimes \Upsilon(r,s) \\
&= \bigvee_{q \in \cat{Q}} \Phi(p,q) \otimes\bigvee_{r \in \cat{R}}
\bigg(\Psi(q,r) \otimes \Upsilon(r,s)\bigg) \\
&= (\Phi\cp(\Psi \cp \Upsilon))(p,s)
\end{align*}

Check that the companion $\comp{\id}$ of $\id\colon\cat{P}\to\cat{P}$ really has the formula given in <ref>.

This is very straightforward. We wish to check $\comp{\id}\colon \cat{P} \tickar
\cat{P}$ has the formula $\comp{\id}(p,q) = \cat{P}(p,q)$. By
<ref>, $\comp\id(p,q) \coloneqq \cat{P}(\id(p),q) =
\cat{P}(p,q)$. So they're the same.

Let $+\colon\RR\times\RR\times\RR\to\RR$ be as in <ref>. What is its conjoint $\conj{+}$?

The conjoint $\conj{+}\colon \RR \tickar \RR \times \RR \times \RR$ sends
$(a,b,c,d)$ to $\RR(a,b+c+d)$, which is $\true$ if $a \le b+c+d$, and false

Let $\cat{V}$ be a skeletal quantale, let $\cat{P}$ and $\cat{Q}$ be $\cat{V}$-categories, and let $F\colon\cat{P}\to\cat{Q}$ and $G\colon\cat{Q}\to\cat{P}$ be $\cat{V}$-functors.

* Show that $F$ and $G$ are $\cat{V}$-adjoints (as in
<ref>) if and only if the companion of the former
equals the conjoint of the latter: $\comp{F}=\conj{G}$.

* Use this to prove that $\comp{\id}=\conj{\id}$, as was stated in <ref>.

* By <ref>, $\comp{F}(p,q) = \cat{Q}(F(p),q)$ and
$\conj{G}(p,q) = \cat{Q}(p,G(q))$. Since $\cat{V}$ is skeletal, $F$ and $G$ are
$\cat{V}$ adjoints if and only if $\cat{Q}(F(p),q) = \cat{Q}(p,G(q))$. Thus $F$
and $G$ are adjoints if and only if $\comp{F} = \conj{G}$.

* Note that $\id\colon \cat{P} \to \cat{P}$ is $\cat{V}$-adjoint to
itself, since both sides of <ref> then equal
$\cat{P}(p,q)$. Thus $\comp{\id} = \conj{\id}$.

Draw a Hasse diagram for the collage of the profunctor shown here:

\[
\begin{tikzpicture}[font=\scriptsize, x=1cm, every label/.style={font=\tiny}, baseline=(Y)]
\node[label={[above=-5pt]:$A$}] (a) {$\bullet$};
\node[right=1 of a, label={[above=-5pt]:$B$}] (b) {$\bullet$};
\node[below=1 of a, label={[below=5pt]:$C$}] (c) {$\bullet$};
\node[right=1 of c, label={[below=5pt]:$D$}] (d) {$\bullet$};
\draw[->] (c) to node[above left=-1pt and -1pt] {3} (b);
\draw[bend right,->] (a) to node[left] {3} (c);
\draw[bend left,->] (d) to node[below] {4} (c);
\draw[bend right,->] (b) to node[above] {2} (a);
\draw[bend left,->] (b) to node[right] {5} (d);
\node[draw, inner sep=15pt, fit=(a) (b) (c) (d)] (X) {};
\node[left=0 of X, font=\normalsize] {$X\coloneqq$};
\node[right=4 of b] (x) {$\LMO{x}$};
\node[below=1 of x] (y) {$\LMO[under]{y}$};
\node at ($(x)!.5!(y)+(1.5cm,0)$) (z) {$\LMO{z}$};
\draw[bend left,->] (y) to node[left] {3} (x);
\draw[bend left,->] (x) to node[right] {4} (y);
\draw[bend left,->] (x) to node[above] {3} (z);
\draw[bend left,->] (z) to node[below right=-1pt and -1pt] {4} (y);
\node[draw, inner sep=15pt, fit=(x) (y) (z.west)] (Y) {};
\node[right=0 of Y, font=\normalsize] {$=:Y$};
\draw[->, dashed, blue, bend left] (b) to node[above] {11} (x);
\draw[->, dashed, blue, bend right] (d) to node[below] {9} (y);
\end{tikzpicture}
\]

The Hasse diagram for the collage of the given profunctor is quite simply this:

\[
\begin{tikzpicture}[font=\scriptsize, x=1cm, every label/.style={font=\tiny}]
\node[label={[above=-5pt]:$A$}] (a) {$\bullet$};
\node[right=1 of a, label={[above=-5pt]:$B$}] (b) {$\bullet$};
\node[below=1 of a, label={[below=5pt]:$C$}] (c) {$\bullet$};
\node[right=1 of c, label={[below=5pt]:$D$}] (d) {$\bullet$};
\draw[->] (c) to node[above left=-1pt and -1pt] {3} (b);
\draw[bend right,->] (a) to node[left] {3} (c);
\draw[bend left,->] (d) to node[below] {4} (c);
\draw[bend right,->] (b) to node[above] {2} (a);
\draw[bend left,->] (b) to node[right] {5} (d);
\node[right=2 of b, label={[above=-5pt]:$x$}] (x) {$\bullet$};
\node[below=1 of x, label={[below=5pt]:$y$}] (y) {$\bullet$};
\node[label={[above=-5pt]:$z$}] at ($(x)!.5!(y)+(1.5cm,0)$) (z) {$\bullet$};
\draw[bend left,->] (y) to node[left] {3} (x);
\draw[bend left,->] (x) to node[right] {4} (y);
\draw[bend left,->] (x) to node[above] {3} (z);
\draw[bend left,->] (z) to node[below right=-1pt and -1pt] {4} (y);
\draw[->, bend left=15pt] (b) to node[above] {11} (x);
\draw[->, bend right=15pt] (d) to node[below] {9} (y);
\node[draw, inner sep=15pt, fit=(a) (c) (z)] {};
\end{tikzpicture}
\]

Check that monoidal categories generalize monoidal preorders: a monoidal preorder is a
monoidal category $(\cat{P},I,\otimes)$ where, for every $p,q\in\cat{P}$, the
set $\cat{P}(p,q)$ has at most one element.

Since we only have a rough definition, we can only roughly check this: we won't
bother with the notion of well-behaved. Nonetheless, we can still compare
<ref> with <ref>.

First, recall from <ref> that a preorder is a
category $\cat{P}$ such that for every $p,q \in \cat{P}$, the set $\cat{P}(p,q)$
has at most one element.

On the surface, all looks promising: both definitions have two constituents and
four properties. In constituent (i), both <ref>
and <ref> call for the same: an element, or object, of the
preorder $\cat{P}$. So far so good. Constituent (ii), however, is where it gets
interesting: <ref> calls for merely a function
$\otimes\colon \cat{P} \times \cat{P} \to \cat{P}$, while
<ref> calls for a functor.

Recall from <ref> that functors between preorders are
exactly monotone maps. So we need for the function $\otimes$ in
<ref> to be a monotone map. This is exactly property (a)
of <ref>: it says that if $(x_1,x_2) \le (y_1,y_2)$ in
$\cat{P} \otimes \cat{P}$, then we must have $x_1 \otimes x_2 \le y_1 \otimes
y_2$ in $\cat{P}$. So it is also the case that in <ref>
that $\otimes$ is a functor.

The remaining properties compare easily, taking the natural isomorphisms to
be equality or equivalence in $\cat{P}$. Indeed, property (b) of
<ref> corresponds to both properties (a) and (b)
of <ref>, and then the respective properties (c) and (d)
similarly correspond.

Consider the monoidal category $(\Cat{Set},1,\times)$, together with the diagram

\[
\begin{tikzpicture}[oriented WD, string decoration={}]
\node[bb={1}{2}] (X11) {$f$};
\node[bb={2}{2}, below right=of X11] (X12) {$g$};
\node[bb={2}{1}, above right=of X12] (X13) {$h$};
\node[bb={0}{0}, fit={($(X11.north west)+(.3,1.5)$) (X12)  ($(X13.east)+(-.3,0)$)}] (Y1) {};
\begin{scope}[font=\small]
\draw[ar] (Y1.west|-X11_in1) to node[above] {$A$} (X11_in1);
\draw[ar] (Y1.west|-X12_in2) to node[above] {$B$} (X12_in2);
\draw[ar] (X11_out1) to node[above] {$C$} (X13_in1);
\draw[ar] (X11_out2) to node[above=5pt] {$D$} (X12_in1);
\draw[ar] (X12_out1) to node[above=5pt] {$E$} (X13_in2);
\draw[ar] (X12_out2) to node[above] {$F$} (X12_out2-|Y1.east);
\draw[ar] (X13_out1) to node[above] {$G$} (X13_out1-|Y1.east);
\end{scope}
\end{tikzpicture}
\]

Suppose that $A=B=C=D=F=G=\ZZ$ and $E=\BB=\{\true,\false\}$,
and suppose that $f_C(a)=|a|$, $f_D(a)=a*5$, $g_E(d,b)=d\leq b$, $g_F(d,b)=d-b$, and $h(c,e)=\tn{if }e\tn{ then }c\tn{ else }1-c$.

* What are $g_E(5,3)$ and $g_F(5,3)$?

* What are $g_E(3,5)$ and $g_F(3,5)$?

* What is $h(5,\true)$?

* What is $h(-5,\true)$?Error!

* What is $h(-5,\false)$?

The whole diagram now defines a function $A\times B\to G\times F$; call it $q$.

* What are $q_G(-2,3)$ and $q_F(-2,3)$?

* What are $q_G(2,3)$ and $q_F(2,3)$?

* $g_E(5,3) = \false$, $g_F(5,3) = 2$.

* $g_E(3,5) = \true$, $g_F(3,5) = -2$.

* $h(5,\true) = 5$.

* $h(-5,\true) = -5$.

* $h(-5,\false) = 6$.

* $q_G(-2,3) = 2$, $q_F(-2,3) =-13$.

* $q_G(2,3) = -1$, $q_F(2,3) =7$.

Recall from <ref> that $\cat{V}=(\smset,\{1\},\times)$ is a
symmetric monoidal category. This means we can apply
<ref>. Does the (rough) definition roughly agree with
the definition of category given in <ref>? Or is there a subtle

Yes, the rough definition roughly agrees: plain old categories are
$\smset$-categories! In detail, we need to compare
<ref> when $\cat{V} = (\smset,\{1\},\times)$ with <ref>.
In both cases, we see that (i) asks for a collection of objects and (ii) asks for,
for all pairs of objects $x,y$, a set $\cat{C}(x,y)$ of morphisms.
Moreover, recall that the monoidal unit $I$ is the one element set $\{1\}$. This
means a morphism $\id_x\colon I \to \cat{C}(x,x)$ is a function $\id_x\colon
\{1\} \to \cat{C}(x,x)$. This is the same data as simply an element $\id_x =
\id_x(1) \in \cat{C}(x,x)$; we call this data the identity morphism on $x$.
Finally, a morphism $\cp\colon \cat{C}(x,y) \otimes \cat{C}(y,z) \to
\cat{C}(x,z)$ is a function $\cp \colon \cat{C}(x,y) \times \cat{C}(y,z) \to
\cat{C}(x,z)$; this is exactly the composite required in <ref>

So in both cases the data agrees. In <ref> we also require this
data to satify two conditions, unitality and associativity. This is what is
meant by the last sentence of <ref>.

What are identity elements in Lawvere metric spaces (that is,
$\Cost$-categories)? How do we interpret this in terms of distances?

An identity element in a $\Cost$-category $\cat{X}$ is a morphism $I \to
\cat{X}(x,x)$ in $\Cost = ([0,\infty], \ge, 0, +)$, and hence the condition that
$0 \ge \cat{X}(x,x)$. This implies that $\cat{X}(x,x) = 0$. In terms of
distances, we interpret this to mean that the distance from any point to itself
is equal to $0$. We think this is a pretty sensible condition for a notion of
distance to obey.

Consider the set $\ord{3}=\{1,2,3\}$.

* Draw a picture of the unit corelation $\varnothing\to\ord{3}\sqcup\ord{3}$.

* Draw a picture of the counit corelation $\ord{3}\sqcup\ord{3}\to\varnothing$.

* Check that the snake equations (<ref>) hold. (Since every object is its own dual, you only need to check one of them.)

* Here is a picture of the unit corelation $\varnothing \to \ord{3} \sqcup
\ord{3}$, where we have drawn the empty set with an empty dotted rectangle on the

\[
\begin{tikzpicture}
\begin{pgfonlayer}{nodelayer}
\node [contact, outer sep=5pt] (1a) at (1, 1.25) {};
\node [contact, outer sep=5pt] (2a) at (1, 0.75) {};
\node [contact, outer sep=5pt] (3a) at (1, 0.25) {};
\node [contact, outer sep=5pt] (1b) at (1, -0.25) {};
\node [contact, outer sep=5pt] (2b) at (1, -0.75) {};
\node [contact, outer sep=5pt] (3b) at (1, -1.25) {};
\node [style=none] (11) at (-2.75, -0) {$\varnothing$};
\node [style=none, right] (12) at (1.75, -0) {$\ord{3} \sqcup \ord{3}$};
\coordinate (1outt) at ($(1a)!.5!(1b)+(-.7,.3)$);
\coordinate (1outb) at ($(1a)!.5!(1b)+(-.7,-.3)$);
\coordinate (1in) at ($(1a)!.5!(1b)-(.4,0)$);
\coordinate (2outt) at ($(2a)!.5!(2b)+(-.7,.3)$);
\coordinate (2outb) at ($(2a)!.5!(2b)+(-.7,-.3)$);
\coordinate (2in) at ($(2a)!.5!(2b)-(.4,0)$);
\coordinate (3outt) at ($(3a)!.5!(3b)+(-.7,.3)$);
\coordinate (3outb) at ($(3a)!.5!(3b)+(-.7,-.3)$);
\coordinate (3in) at ($(3a)!.5!(3b)-(.4,0)$);
\end{pgfonlayer}
\begin{pgfonlayer}{edgelayer}
\draw [dotted] (-2.25,1.5) -- (-2.25,-1.5) -- (-1.75,-1.5) --
(-1.75,1.5) -- cycle;
\begin{scope}[rounded corners=5pt, densely dotted, thick]
\draw[blue!50!black]
(node cs:name=1a, anchor=south west) --
(node cs:name=1a, anchor=south east) --
(node cs:name=1a, anchor=north east) --
(node cs:name=1a, anchor=north west) --
(node cs:name=1outt) --
(node cs:name=1outb) --
(node cs:name=1b, anchor=south west) --
(node cs:name=1b, anchor=south east) --
(node cs:name=1b, anchor=north east) --
(node cs:name=1b, anchor=north west) --
(node cs:name=1in) --
\draw[red!50!black]
(node cs:name=2a, anchor=south west) --
(node cs:name=2a, anchor=south east) --
(node cs:name=2a, anchor=north east) --
(node cs:name=2a, anchor=north west) --
(node cs:name=2outt) --
(node cs:name=2outb) --
(node cs:name=2b, anchor=south west) --
(node cs:name=2b, anchor=south east) --
(node cs:name=2b, anchor=north east) --
(node cs:name=2b, anchor=north west) --
(node cs:name=2in) --
\draw [green!50!black]
(node cs:name=3a, anchor=south west) --
(node cs:name=3a, anchor=south east) --
(node cs:name=3a, anchor=north east) --
(node cs:name=3a, anchor=north west) --
(node cs:name=3outt) --
(node cs:name=3outb) --
(node cs:name=3b, anchor=south west) --
(node cs:name=3b, anchor=south east) --
(node cs:name=3b, anchor=north east) --
(node cs:name=3b, anchor=north west) --
(node cs:name=3in) --
\end{scope}
\end{pgfonlayer}
\end{tikzpicture}
\]

* Here is a picture of the counit corelation $\ord{3} \sqcup
\ord{3} \to \varnothing$:

\[
\begin{tikzpicture}[scale=-1]
\begin{pgfonlayer}{nodelayer}
\node [contact, outer sep=5pt] (1a) at (1, 1.25) {};
\node [contact, outer sep=5pt] (2a) at (1, 0.75) {};
\node [contact, outer sep=5pt] (3a) at (1, 0.25) {};
\node [contact, outer sep=5pt] (1b) at (1, -0.25) {};
\node [contact, outer sep=5pt] (2b) at (1, -0.75) {};
\node [contact, outer sep=5pt] (3b) at (1, -1.25) {};
\node [style=none] (11) at (-2.75, -0) {$\varnothing$};
\node [style=none, left] (12) at (1.75, -0) {$\ord{3} \sqcup \ord{3}$};
\coordinate (1outt) at ($(1a)!.5!(1b)+(-.7,.3)$);
\coordinate (1outb) at ($(1a)!.5!(1b)+(-.7,-.3)$);
\coordinate (1in) at ($(1a)!.5!(1b)-(.4,0)$);
\coordinate (2outt) at ($(2a)!.5!(2b)+(-.7,.3)$);
\coordinate (2outb) at ($(2a)!.5!(2b)+(-.7,-.3)$);
\coordinate (2in) at ($(2a)!.5!(2b)-(.4,0)$);
\coordinate (3outt) at ($(3a)!.5!(3b)+(-.7,.3)$);
\coordinate (3outb) at ($(3a)!.5!(3b)+(-.7,-.3)$);
\coordinate (3in) at ($(3a)!.5!(3b)-(.4,0)$);
\end{pgfonlayer}
\begin{pgfonlayer}{edgelayer}
\draw [dotted] (-2.25,1.5) -- (-2.25,-1.5) -- (-1.75,-1.5) --
(-1.75,1.5) -- cycle;
\begin{scope}[rounded corners=5pt, densely dotted, thick]
\draw [blue!50!black]
(node cs:name=1a, anchor=south east) --
(node cs:name=1a, anchor=south west) --
(node cs:name=1a, anchor=north west) --
(node cs:name=1a, anchor=north east) --
(node cs:name=1in) --
(node cs:name=1b, anchor=south east) --
(node cs:name=1b, anchor=south west) --
(node cs:name=1b, anchor=north west) --
(node cs:name=1b, anchor=north east) --
(node cs:name=1outb) --
(node cs:name=1outt) --
\draw  [red!50!black]
(node cs:name=2a, anchor=south east) --
(node cs:name=2a, anchor=south west) --
(node cs:name=2a, anchor=north west) --
(node cs:name=2a, anchor=north east) --
(node cs:name=2in) --
(node cs:name=2b, anchor=south east) --
(node cs:name=2b, anchor=south west) --
(node cs:name=2b, anchor=north west) --
(node cs:name=2b, anchor=north east) --
(node cs:name=2outb) --
(node cs:name=2outt) --
\draw  [green!50!black]
(node cs:name=3a, anchor=south east) --
(node cs:name=3a, anchor=south west) --
(node cs:name=3a, anchor=north west) --
(node cs:name=3a, anchor=north east) --
(node cs:name=3in) --
(node cs:name=3b, anchor=south east) --
(node cs:name=3b, anchor=south west) --
(node cs:name=3b, anchor=north west) --
(node cs:name=3b, anchor=north east) --
(node cs:name=3outb) --
(node cs:name=3outt) --
\end{scope}
\end{pgfonlayer}
\end{tikzpicture}
\]

* Here is a picture of the snake equation on the left of <ref>.

\[
\begin{altikz}
\begin{pgfonlayer}{nodelayer}
\node [contact, outer sep=5pt] (1cA) at (-5, -1) {};
\node [contact, outer sep=5pt] (2cA) at (-5, -1.5) {};
\node [contact, outer sep=5pt] (3cA) at (-5, -2) {};
\node [contact, outer sep=5pt] (1aB) at (-2, 2) {};
\node [contact, outer sep=5pt] (2aB) at (-2, 1.5) {};
\node [contact, outer sep=5pt] (3aB) at (-2, 1) {};
\node [contact, outer sep=5pt] (1bB) at (-2, 0.5) {};
\node [contact, outer sep=5pt] (2bB) at (-2, 0) {};
\node [contact, outer sep=5pt] (3bB) at (-2, -.5) {};
\node [contact, outer sep=5pt] (1cB) at (-2, -1) {};
\node [contact, outer sep=5pt] (2cB) at (-2, -1.5) {};
\node [contact, outer sep=5pt] (3cB) at (-2, -2) {};
\node [contact, outer sep=5pt] (1aC) at (1, 2) {};
\node [contact, outer sep=5pt] (2aC) at (1, 1.5) {};
\node [contact, outer sep=5pt] (3aC) at (1, 1) {};
\coordinate (1outtB) at ($(1aB)!.5!(1bB)+(-.7,.3)$);
\coordinate (1outbB) at ($(1aB)!.5!(1bB)+(-.7,-.3)$);
\coordinate (1inB) at ($(1aB)!.5!(1bB)+(-.4,0)$);
\coordinate (2outtB) at ($(2aB)!.5!(2bB)+(-.7,.3)$);
\coordinate (2outbB) at ($(2aB)!.5!(2bB)+(-.7,-.3)$);
\coordinate (2inB) at ($(2aB)!.5!(2bB)+(-.4,0)$);
\coordinate (3outtB) at ($(3aB)!.5!(3bB)+(-.7,.3)$);
\coordinate (3outbB) at ($(3aB)!.5!(3bB)+(-.7,-.3)$);
\coordinate (3inB) at ($(3aB)!.5!(3bB)+(-.4,0)$);
\coordinate (1outt) at ($(1bB)!.5!(1cB)+(.7,.3)$);
\coordinate (1outb) at ($(1bB)!.5!(1cB)+(.7,-.3)$);
\coordinate (1in) at ($(1bB)!.5!(1cB)+(.4,0)$);
\coordinate (2outt) at ($(2bB)!.5!(2cB)+(.7,.3)$);
\coordinate (2outb) at ($(2bB)!.5!(2cB)+(.7,-.3)$);
\coordinate (2in) at ($(2bB)!.5!(2cB)+(.4,0)$);
\coordinate (3outt) at ($(3bB)!.5!(3cB)+(.7,.3)$);
\coordinate (3outb) at ($(3bB)!.5!(3cB)+(.7,-.3)$);
\coordinate (3in) at ($(3bB)!.5!(3cB)+(.4,0)$);
\end{pgfonlayer}
\begin{pgfonlayer}{edgelayer}
\begin{scope}[rounded corners=5pt, densely dotted, thick]
% unit
\draw  [blue!50!black]
(node cs:name=1aB, anchor=south west) --
(node cs:name=1aB, anchor=south east) --
(node cs:name=1aB, anchor=north east) --
(node cs:name=1aB, anchor=north west) --
(node cs:name=1outtB) --
(node cs:name=1outbB) --
(node cs:name=1bB, anchor=south west) --
(node cs:name=1bB, anchor=south east) --
(node cs:name=1bB, anchor=north east) --
(node cs:name=1bB, anchor=north west) --
(node cs:name=1inB) --
\draw  [red!50!black]
(node cs:name=2aB, anchor=south west) --
(node cs:name=2aB, anchor=south east) --
(node cs:name=2aB, anchor=north east) --
(node cs:name=2aB, anchor=north west) --
(node cs:name=2outtB) --
(node cs:name=2outbB) --
(node cs:name=2bB, anchor=south west) --
(node cs:name=2bB, anchor=south east) --
(node cs:name=2bB, anchor=north east) --
(node cs:name=2bB, anchor=north west) --
(node cs:name=2inB) --
\draw  [green!50!black]
(node cs:name=3aB, anchor=south west) --
(node cs:name=3aB, anchor=south east) --
(node cs:name=3aB, anchor=north east) --
(node cs:name=3aB, anchor=north west) --
(node cs:name=3outtB) --
(node cs:name=3outbB) --
(node cs:name=3bB, anchor=south west) --
(node cs:name=3bB, anchor=south east) --
(node cs:name=3bB, anchor=north east) --
(node cs:name=3bB, anchor=north west) --
(node cs:name=3inB) --
% counit
\draw  [blue!50!black]
(node cs:name=1bB, anchor=south east) --
(node cs:name=1bB, anchor=south west) --
(node cs:name=1bB, anchor=north west) --
(node cs:name=1bB, anchor=north east) --
(node cs:name=1outt) --
(node cs:name=1outb) --
(node cs:name=1cB, anchor=south east) --
(node cs:name=1cB, anchor=south west) --
(node cs:name=1cB, anchor=north west) --
(node cs:name=1cB, anchor=north east) --
(node cs:name=1in) --
\draw  [red!50!black]
(node cs:name=2bB, anchor=south east) --
(node cs:name=2bB, anchor=south west) --
(node cs:name=2bB, anchor=north west) --
(node cs:name=2bB, anchor=north east) --
(node cs:name=2outt) --
(node cs:name=2outb) --
(node cs:name=2cB, anchor=south east) --
(node cs:name=2cB, anchor=south west) --
(node cs:name=2cB, anchor=north west) --
(node cs:name=2cB, anchor=north east) --
(node cs:name=2in) --
\draw  [green!50!black]
(node cs:name=3bB, anchor=south east) --
(node cs:name=3bB, anchor=south west) --
(node cs:name=3bB, anchor=north west) --
(node cs:name=3bB, anchor=north east) --
(node cs:name=3outt) --
(node cs:name=3outb) --
(node cs:name=3cB, anchor=south east) --
(node cs:name=3cB, anchor=south west) --
(node cs:name=3cB, anchor=north west) --
(node cs:name=3cB, anchor=north east) --
(node cs:name=3in) --
% identities
\draw  [blue!50!black]
(node cs:name=1cA, anchor=south west) --
(node cs:name=1cB, anchor=south east) --
(node cs:name=1cB, anchor=north east) --
(node cs:name=1cA, anchor=north west) --
\draw  [red!50!black]
(node cs:name=2cA, anchor=south west) --
(node cs:name=2cB, anchor=south east) --
(node cs:name=2cB, anchor=north east) --
(node cs:name=2cA, anchor=north west) --
\draw  [green!50!black]
(node cs:name=3cA, anchor=south west) --
(node cs:name=3cB, anchor=south east) --
(node cs:name=3cB, anchor=north east) --
(node cs:name=3cA, anchor=north west) --
\draw  [blue!50!black]
(node cs:name=1aB, anchor=south west) --
(node cs:name=1aC, anchor=south east) --
(node cs:name=1aC, anchor=north east) --
(node cs:name=1aB, anchor=north west) --
\draw  [red!50!black]
(node cs:name=2aB, anchor=south west) --
(node cs:name=2aC, anchor=south east) --
(node cs:name=2aC, anchor=north east) --
(node cs:name=2aB, anchor=north west) --
\draw  [green!50!black]
(node cs:name=3aB, anchor=south west) --
(node cs:name=3aC, anchor=south east) --
(node cs:name=3aC, anchor=north east) --
(node cs:name=3aB, anchor=north west) --
\end{scope}
\end{pgfonlayer}
\end{altikz}
\quad
\quad
\begin{altikz}
\begin{pgfonlayer}{nodelayer}
\node [contact, outer sep=5pt] (1a) at (-2, 1) {};
\node [contact, outer sep=5pt] (2a) at (-2, 0.5) {};
\node [contact, outer sep=5pt] (3a) at (-2, 0) {};
\node [contact, outer sep=5pt] (1b) at (1, 1) {};
\node [contact, outer sep=5pt] (2b) at (1, 0.5) {};
\node [contact, outer sep=5pt] (3b) at (1, 0) {};
%		\node [style=none] (11) at (-2.75, 0.5) {$\ord{3}$};
%		\node [style=none] (12) at (1.75, 0.5) {$\ord{3}$};
\end{pgfonlayer}
\begin{pgfonlayer}{edgelayer}
\begin{scope}[rounded corners=5pt, densely dotted, thick]
\draw  [blue!50!black]
(node cs:name=1a, anchor=south west) --
(node cs:name=1b, anchor=south east) --
(node cs:name=1b, anchor=north east) --
(node cs:name=1a, anchor=north west) --
\draw  [red!50!black]
(node cs:name=2a, anchor=south west) --
(node cs:name=2b, anchor=south east) --
(node cs:name=2b, anchor=north east) --
(node cs:name=2a, anchor=north west) --
\draw  [green!50!black]
(node cs:name=3a, anchor=south west) --
(node cs:name=3b, anchor=south east) --
(node cs:name=3b, anchor=north east) --
(node cs:name=3a, anchor=north west) --
\end{scope}
\end{pgfonlayer}
\end{altikz}
\]

Interpret the monoidal products in $\Prof_{\Bool}$ in terms of feasibility. That is, preorders represent resources ordered by availability ($x\leq x'$ means that $x$ is available given $x'$) and a profunctor is a feasibility relation. Explain why $\cat{X}\times\cat{Y}$ makes sense as the monoidal product of resource preorders $\cat{X}$ and $\cat{Y}$ and why $\Phi\times\Psi$ makes sense as the monoidal product of feasibility relations $\Phi$ and $\Psi$.

Given two resource preorders $\cat{X}$ and $\cat{Y}$, the preorder $\cat{X}\times\cat{Y}$ represents the set of all pairs of resources, $x\in \cat{X}$ and $y\in \cat{Y}$, with $(x,y)\leq(x',y')$ iff $x\leq x'$ and $y\leq y'$. That is, if $x$ is available given $x'$ and $y$ is available given $y'$, then $(x,y)$ is available given $(x',y')$.

Given two profunctors $\Phi\colon\cat{X}_1\tickar\cat{X}_2$ and $\Psi\colon\cat{Y}_1\tickar\cat{Y}_2$, the profunctor $\Phi\times\Psi$ represents their conjunction, i.e. AND. In other words, if $y_1$ can be obtained given $x_1$ AND $y_2$ can be obtained given $x_2$, then $(y_1,y_2)$ can be obtained given $(x_1,x_2)$.

In order for $\Cat{1}$ to be a monoidal unit, there are supposed to be
isomorphisms $\cat{X}\times\Cat{1}\tickar\cat{X}$ and
$\Cat{1}\times\cat{X}\tickar\cat{X}$, for any $\cat{V}$-category $\cat{X}$. What
are they?

The profunctor $\cat{X} \times \Cat{1} \tickar \cat{X}$ defined by the functor
$\alpha\colon (\cat{X} \times \Cat{1})\op \times \cat{X} \to \cat{V}$ that maps
$\alpha((x,1),y)\coloneqq\cat{X}(x,y)$ is an isomorphism. It has inverse
$\alpha\inv\colon \cat{X} \tickar \cat{X} \times \Cat{1}$ defined by
$\alpha\inv(x,(y,1))\coloneqq\cat{X}(x,y)$. To see that $\alpha\inv \cp \alpha =
\Unit{\cat{X}}$, note first that the unit law for $\cat{X}$ at $z$ and the definition
of join imply

\[
\cat{X}(x,z) = \cat{X}(x,z) \otimes I \le \cat{X}(x,z) \otimes \cat{X}(z,z) \le
\bigvee_{y \in \cat{X}} \cat{X}(x,y) \otimes \cat{X}(y,z),
\]

while composition says $\cat{X}(x,y) \otimes \cat{X}(y,z) \le \cat{X}(x,z)$ and

\[
\bigvee_{y \in \cat{X}} \cat{X}(x,y) \otimes \cat{X}(y,z) \le \bigvee_{y \in
\cat{X}} \cat{X}(x,z) = \cat{X}(x,z).
\]

Thus, unpacking the definition of composition of profunctor, we have

\[
(\alpha\inv\cp \alpha) (x,z)
= \bigvee_{(y,1) \in \cat{X} \times \Cat{1}} \alpha(x,(y,1)) \otimes
\alpha\inv((y,1),z)
= \bigvee_{y \in \cat{X}} \cat{X}(x,y) \otimes \cat{X}(y,z) = \cat{X}(x,z).
\]

Similarly we can show $\alpha\cp\alpha\inv = \Unit{\cat{X} \times \Cat{1}}$, and
hence that $\alpha$ is an isomorphism $\cat{X} \times \Cat{1} \tickar \cat{X}$.

Moreover, we can similarly show that $\beta((1,x),y) \coloneqq \cat{X}(x,y)$ defines an
isomorphism $\beta\colon \Cat{1} \times \cat{X} \tickar \cat{X}$.

Check these proposed units and counits do indeed obey the snake equations

We check the first snake equation, the one on the left hand side of
<ref>. The proof of the one on the right hand side is analogous.

We must show that the composite $\Phi$ of profunctors

\[
\cat{X} \xrightarrow{\alpha\inv} \cat{X} \times \Cat{1} \xrightarrow{\Unit{\cat{X}}
\times \eta_{\cat{X}}} \cat{X} \times \cat{X}\op \times \cat{X}
\xrightarrow{\epsilon_{\cat{X}} \times \Unit{\cat{X}}} \Cat{1} \times \cat{X}
\xrightarrow{\alpha} \cat{X}
\]

is itself the identity (ie. the unit profunctor on $\cat{X}$), where $\alpha$
and $\alpha\inv$ are the isomorphisms defined in the solution to
<ref> above.

Freely using the distributivity of $\otimes$ over $\vee$, the value $\Phi(x,y)$ of this
composite at $(x,y) \in \cat{X}\op \times \cat{X}$ is given by

\begin{align*}
&\bigvee_{a,b,c,d,e \in \cat{X}}
\begin{multlined}[t][11cm]
\alpha\inv(x,(a,1)) \otimes
(\Unit{\cat{X}}\times \eta_{\cat{X}})((a,1),(b,c,d))\\
\otimes (\epsilon_{\cat{X}} \times \Unit{\cat{X}})((b,c,d),(1,e)) \otimes
\alpha((1,e),y)
\end{multlined}
\\
=&\bigvee_{a,b,c,d,e \in \cat{X}}
\begin{multlined}[t][11cm]
\alpha\inv(x,(a,1)) \otimes
\Unit{\cat{X}}(a,b) \otimes \eta_{\cat{X}}(1,c,d) \\
\otimes
\epsilon_{\cat{X}}(b,c,1) \otimes \Unit{\cat{X}}(d,e) \otimes
\alpha((1,e),y)
\end{multlined}
\\
=& \bigvee_{a,b,c,d,e \in \cat{X}} \cat{X}(x,a) \otimes \cat{X}(a,b) \otimes
\cat{X}(c,d) \otimes \cat{X}(b,c) \otimes \cat{X}(d,e) \otimes \cat{X}(e,y) \\
=&\quad \cat{X}(x,y)
\end{align*}

where in the final step we repeatedly use the argument the
<ref> that shows that composing with the unit profunctor
$\Unit{\cat{X}}(a,b) = \cat{X}(a,b)$ is the identity.

This shows that $\Phi(x,y)$ is the identity profunctor, and hence shows the
first snake equation holds. Again, checking the other snake equation is

§ SOLUTIONS FOR <REF>.

In <ref> we said that the identities, symmetries, and
composition rule in $\Cat{FinSet}$ “are obvious.” In math lingo, this just
means “we trust that the reader can figure them out, if she spends the time tracking
down the definitions and fitting them together.”

* Draw a morphism $f\colon 3\to 2$ and a morphism $g\colon 2\to 4$ in $\finset$.

* Draw $f+g$.

* What is the composition rule for morphisms $f\colon m\to n$ and $g\colon n\to p$ in $\Cat{FinSet}$?

* What are the identities in $\Cat{FinSet}$? Draw some.

* Choose $m,n \in \NN$, and draw the symmetric map $\sigma_{m,n}$
in $\Cat{FinSet}$?

* Below we draw a morphism $f\colon 3\to 2$ and a morphism $g\colon 2\to 4$ in $\finset$:

\[
\begin{tikzpicture}
\boxofbullets{3}{(0,0)}{B1};
\node[left=0.5 of box_B1] (lab_B1) {3};
\boxofbullets{2}{(0,-1.5)}{B2};
\node at (lab_B1|-box_B2) (lab_B2) {2};
\boxofbullets{4}{(4,-1.5)}{C2};
\node[right=0.5 of box_C2] (lab_C2) {4};
\boxofbullets{2}{(4,0)}{C1};
\node at (lab_C2|-box_C1) (lab_C1) {2};
\draw[->] (lab_B1) to node[left] {$f$} (lab_B2);
\draw[->] (lab_C1) to node[right] {$g$} (lab_C2);
\begin{scope}[short=0pt, mapsto]
\draw (pt_B1_1) -- (pt_B2_1);
\draw (pt_B1_2) -- (pt_B2_1);
\draw (pt_B1_3) -- (pt_B2_2);
\draw (pt_C1_1) -- (pt_C2_3);
\draw (pt_C1_2) -- (pt_C2_3);
\end{scope}
\end{tikzpicture}
\]

* Here is a picture of $f+g$

\[
\begin{tikzpicture}
\boxofbullets{5}{(0,0)}{B1};
\node[left=0.5 of box_B1] (lab_B1) {3+2};
\boxofbullets{6}{(0,-1.5)}{B2};
\node at (lab_B1|-box_B2) (lab_B2) {2+4};
\draw[->] (lab_B1) to node[left] {$f+g$} (lab_B2);
\begin{scope}[short=0pt, mapsto]
\draw (pt_B1_1) -- (pt_B2_1);
\draw (pt_B1_2) -- (pt_B2_1);
\draw (pt_B1_3) -- (pt_B2_2);
\draw (pt_B1_4) -- (pt_B2_5);
\draw (pt_B1_5) -- (pt_B2_5);
\end{scope}
\end{tikzpicture}
\]

* The composite of morphisms $f\colon m\to n$ and $g\colon n\to p$ in $\Cat{FinSet}$ is the function $(f\cp g)\colon m\to p$ given by $(f\cp g)(i)=g(f(i))$ for all $1\leq i\leq m$.

* The identity $\id_m\colon m\to m$ is given by $\id_m(i)=i$ for all $1\leq i\leq m$. Here is a picture of $\id_2$ and $\id_8$:

\[
\begin{tikzpicture}
\boxofbullets{2}{(0,0)}{B1};
\node[left=0.5 of box_B1] (lab_B1) {2};
\boxofbullets{2}{(0,-1.5)}{B2};
\node[left=0.5 of box_B2] (lab_B2) {2};
\boxofbullets{8}{(6,0)}{C1};
\node[right=0.5 of box_C1] (lab_C1) {8};
\boxofbullets{8}{(6,-1.5)}{C2};
\node[right=0.5 of box_C2] (lab_C2) {8};
\draw[->] (lab_B1) to node[left] {$\id_2$} (lab_B2);
\draw[->] (lab_C1) to node[right] {$\id_8$} (lab_C2);
\begin{scope}[short=0pt, mapsto]
\foreach \i in {1,2} {
\draw[mapsto] (pt_B1_\i) -- (pt_B2_\i);
\foreach \i in {1,...,8} {
\draw (pt_C1_\i) -- (pt_C2_\i);
\end{scope}
\end{tikzpicture}
\]

* Here is a picture of the symmetry $\sigma_{3,5}\colon 8\to 8$:

\[
\begin{tikzpicture}
\boxofbullets{8}{(6,0)}{C1};
\node[right=0.5 of box_C1] (lab_C1) {8};
\boxofbullets{8}{(6,-1.5)}{C2};
\node[right=0.5 of box_C2] (lab_C2) {8};
\draw[->] (lab_C1) to node[right] {$\sigma_{3,5}$} (lab_C2);
\begin{scope}[short=0pt, mapsto]
\foreach \i/\j in {1/6,2/7,3/8} {
\draw (pt_C1_\i.south) -- (pt_C2_\j.north);
\foreach \i/\j in {4/1, 5/2, 6/3, 7/4, 8/5} {
\draw (pt_C1_\i.south) -- (pt_C2_\j.north);
\end{scope}
\end{tikzpicture}
\]

A posetal prop is a prop that is also a poset. That is, a posetal prop is a
symmetric monoidal preorder of the form $(\NN,\preceq)$, for some poset relation
$\preceq$ on $\NN$, where the monoidal product on objects is addition. We've
spent a lot of time discussing order structures on the natural numbers. Give
three examples of a posetal prop.

We need to give examples posetal props, i.e. each will be a poset whose set of objects is $\nn$, whose order is denoted $m\preceq n$, and with the property that whenever $m_1\preceq n_1$ and $m_2\preceq n_2$ hold then $m_1+m_2\preceq n_1+n_2$ does too.

The question only asks for three, but we will additionally give a quasi-example and a non-example.

* Take $\preceq$ to be the discrete order: $m\preceq n$ iff $m=n$.

* Take $\preceq$ to be the usual order, $m\preceq n$ iff there exists $d\in\nn$ with $d+m=n$.

* Take $\preceq$ to be the reverse of the usual order, $m\preceq n$ iff there exists $d\in\nn$ with $m=n+d$.

* Take $\preceq$ to be the co-discrete order $m\preceq n$ for all $m,n$. Some may object that this is a preorder, not a poset, so we call it a quasi-example.

* (Non-example.) Take $\preceq$ to be the division order, $m\preceq n$ iff there exists $q\in\nn$ with $m*q=d$. This is a perfectly good poset, but it does not satisfy the monotonicity property: we have $2\preceq 4$ and $3\preceq 3$ but not $5\preceq^?7$.

Choose one of <ref> and explicitly provide the five aspects of props discussed below <ref>.

<ref>: The prop $\Cat{Bij}$ has

* $\Cat{Bij}(m,n)\coloneqq\{f\colon\ord{m}\to\ord{n}\mid f\text{ is a bijection}\}$. Note that $\Cat{Bij}(m,n)=\varnothing$ if $m\neq n$ and it has $n!$ elements if $m=n$.

* The identity map $n\to n$ is the bijection $\ord{n}\to\ord{n}$ sending $i\mapsto i$.

* The symmetry map $m+n\to n+m$ is the bijection $\sigma_{m,n}\colon\ord{m+n}\to\ord{n+m}$ given by

\[
\sigma_{m,n}(i)\coloneqq
\begin{cases}
i+n&\tn{ if }i\leq m\\
i-m&\tn{ if }m+1\leq i
\end{cases}
\]

* Composition of bijections $m\to n$ and $n\to p$ is just their composition as functions, which is again a bijection.

* Given bijections $f\colon m\to m'$ and $g\colon n\to n'$, their monoidal product $(f+g)\colon (m+n)\to(m'+n')$ is given by

\[
\begin{cases}
f(i)&\tn{ if }i\leq m\\
g(i-m)&\tn{ if }m+1\leq i
\end{cases}
\]

<ref>: The prop $\Cat{Corel}$ has

* $\Cat{Corel}(m,n)$ is the set of equivalence relations on $\ord{m+n}$.

* The identity map $n\to n$ is the smallest equivalence relation, which is the smallest reflexive relation, i.e. where $i\sim j$ iff $i=j$.

* The symmetry map $\sigma_{m,n}$, as an equivalence relation on $\ord{m+n+n+m}$ is “the obvious thing,” namely “equating corresponding $m$'s together and also equating corresponding $n$'s together.” To be pedantic, $i\sim j$ iff either

* $|i-j|=m+n+n$, or

* $m+1\leq i\leq m+n+n$ and $m+1\leq j\leq m+n+n$ and $|i-j|=n$.

* Composition of an equivalence relation $\sim$ on $\ord{m+n}$ and an equivalence relation $\dot\sim$ on $\ord{n+p}$ is the equivalence relation $\simeq$ on $\ord{m+p}$ given by $i\simeq k$ iff there exists $j\in\ord{n}$ with $i\sim j$ and $j\dot\sim k$.

* Given equivalence relations $\sim$ on $\ord{m+n}$ and $\sim'$ on $\ord{m'+n'}$, we need an equivalence relation $(\sim+\sim')$ on $\ord{m+n+m'+n'}$. We take it to be “the obvious thing,” namely “using $\sim$ on the unprimed stuff and using $\sim'$ on the primed stuff, with no other interaction.” To be pedantic, $i\sim j$ iff either

* $i\leq m+n$ and $j\leq m+n$ and $i\sim j$, or

* $m+n+1\leq i$ and $m+n+1\leq j$ and $i\sim'j$.

<ref>: The prop $\Cat{Rel}$ has

* $\Cat{Rel}(m,n)$ is the set of relations on the set $\ord{m}\times\ord{n}$, i.e. the set of subsets of $\ord{m}\times\ord{n}$, i.e. its powerset.

* The identity map $n\to n$ is the subset $\{(i,j)\in\ord{n}\times\ord{n}\mid i=j\}$.

* The symmetry map $m+n\to n+m$ is the subset of pairs $(i,j)\in(\ord{m+n})\times(\ord{n+m})$ such that either

* $i\leq m$ and $m+1\leq j$ and $i+m=j$, or

* $m+1\leq i$ and $j\leq m$ and $j+m=i$.

* Composition of relations is as in <ref>.

* Given a relation $R\ss\ord{m}\times\ord{n}$ and a relation $R'\ss\ord{m'}\times\ord{n'}$, we need a relation $(R+R')\ss\ord{m+m'}\times\ord{n+n'}$. As stated in the example (footnote), this can be given by a universal property: The monoidal product $R_1+R_2$ of relations $R_1\ss \ord{m_1}\times \ord{n_1}$ and $R_2\ss \ord{m_2}\times \ord{n_2}$ is given by $R_1\sqcup R_2\ss(\ord{m_1}\times \ord{n_1})\sqcup(\ord{m_2}\times \ord{n_2})\ss(\ord{m_1}\sqcup \ord{m_2})\times(\ord{n_1}\sqcup \ord{n_2})$.

Describe how port graph composition looks, with respect to the visual
representation of <ref>, and give a nontrivial example.

Composition of an $(m,n)$-port graph $G$ and an $(n,p)$-port graph $H$ looks visually like sticking them end to end, connecting the wires in order, removing the two outer boxes, and adding a new outer box.

For example, suppose we want to compose the following in the order shown:

\[
\begin{tikzpicture}[oriented WD, bbx=1.2cm, bb min width=.5cm, bb port length=2pt, bb port sep=.75, baseline=(X2.north)]
\node[bb={1}{3}] (X1) {$a$};
\node[bb={3}{3}, below right=-.5 and 1 of X1] (X2) {$b$};
\node[bb={2}{1}, above right=-.5 and 1 of X2] (X3) {$c$};
\node[bb={0}{0}, fit={($(X1.north west)+(.3,.0)$) (X2)  ($(X3.east)+(-.3,0)$)}] (X) {};
\node[coordinate] at (X.west|-X1_in1) (X_in1) {};
\node[coordinate] at (X.west|-X2_in3) (X_in2) {};
\node[coordinate] at (X3_out1-|X.east) (X_out1) {};
\node[coordinate] at (X2_out2-|X.east) (X_out2) {};
\node[coordinate] at (X2_out3-|X.east) (X_out3) {};
\draw (X_in1) to (X1_in1);
\draw (X_in2) to (X2_in3);
\draw (X1_out1) to (X3_in1);
\draw (X1_out2) to (X2_in2);
\draw (X1_out3) to (X2_in1);
\draw (X2_out1) to (X3_in2);
\draw (X3_out1) to (X_out1);
\draw (X2_out2) to (X_out2);
\draw (X2_out3) to (X_out3);
\node[bb={1}{1}, right=3 of X3] (Y1) {$d$};
\node[bb={2}{1}, below right=-1 and .5 of Y1] (Y2) {$e$};
\node[bb={0}{0}, fit={(Y1) ($(Y2.south east)+(0,-1)$)}] (Y) {};
\node[coordinate] at (Y.west|-Y1_in1) (Y_in1) {};
\node[coordinate] at (Y.west|-Y2_in2) (Y_in2) {};
\node[coordinate] at ($(Y_in2)+(0,-1.5)$) (Y_in3) {};
\node[coordinate] at (Y.east|-Y2_out1) (Y_out1) {};
\node[coordinate] at (Y.east|-Y_in3) (Y_out2) {};
\draw (Y_in1) to (Y1_in1);
\draw (Y_in2) to (Y2_in2);
\draw (Y_in3) to (Y_out2);
\draw (Y1_out1) to (Y2_in1);
\draw (Y2_out1) to (Y_out1);
\node at ($(X.east)!.5!(Y.west)$) {\Huge$\cp$};
\end{tikzpicture}
\]

The result is:

\[
\begin{tikzpicture}[oriented WD, bbx=1.2cm, bb min width=.5cm, bb port length=2pt, bb port sep=.75, baseline=(X2.north)]
\node[bb={1}{3}] (X1) {$a$};
\node[bb={3}{3}, below right=-.5 and 1 of X1] (X2) {$b$};
\node[bb={2}{1}, above right=-.5 and 1 of X2] (X3) {$c$};
\node[bb={1}{1}, right= of X3] (Y1) {$d$};
\node[bb={2}{1}, below right=-1.5 and 1 of Y1] (Y2) {$e$};
\node[bb={0}{0}, fit={($(X1.north west)+(.3,0)$) (X2)  ($(X3.east)+(-.3,0)$) ($(Y2.south east)+(0,-2)$)}] (outer) {};
\node[coordinate] at (outer.west|-X1_in1) (outer_in1) {};
\node[coordinate] at (outer.west|-X2_in3) (outer_in2) {};
\node[coordinate] at (outer.east|-Y2_out1) (outer_out1) {};
\node[coordinate] at (outer.east|-X2_out3) (outer_out2) {};
\draw (outer_in1) to (X1_in1);
\draw (outer_in2) to (X2_in3);
\draw (X1_out1) to (X3_in1);
\draw (X1_out2) to (X2_in2);
\draw (X1_out3) to (X2_in1);
\draw (X2_out1) to (X3_in2);
\draw (X3_out1) to (Y1_in1);
\draw (X2_out2) -- (X2_out2-|Y1.east) to (Y2_in2);
\draw (X2_out3) to (outer_out2);
\draw (Y1_out1) to (Y2_in1);
\draw (Y2_out1) to (outer_out1);
\end{tikzpicture}
\]

Draw the monoidal product of the morphism shown in <ref> with itself. It will be a $(4,6)$-port graph, i.e. a morphism $4\to 6$ in $\Cat{PG}$.

The monoidal product of two morphisms is drawn by stacking the corresponding port graphs. For this problem, we just stack the left-hand picture on top of itself to obtain the righthand picture:

\[
\begin{tikzpicture}[oriented WD, bb small, baseline=(Y.south)]
\node[bb={1}{3}] (X1) {$a$};
\node[bb={3}{3}, below right=of X1] (X2) {$b$};
\node[bb={2}{1}, above right=of X2] (X3) {$c$};
\node[bb={0}{0}, fit={($(X1.north west)+(.3,1.5)$) (X2)  ($(X3.east)+(-.3,0)$)}] (Y) {};
\node[coordinate] at (Y.west|-X1_in1) (Y_in1) {};
\node[coordinate] at (Y.west|-X2_in3) (Y_in2) {};
\node[coordinate] at (X3_out1-|Y.east) (Y_out1) {};
\node[coordinate] at (X2_out2-|Y.east) (Y_out2) {};
\node[coordinate] at (X2_out3-|Y.east) (Y_out3) {};
\draw (Y_in1) to (X1_in1);
\draw (Y_in2) to (X2_in3);
\draw (X1_out1) to (X3_in1);
\draw (X1_out2) to (X2_in2);
\draw (X1_out3) to (X2_in1);
\draw (X2_out1) to (X3_in2);
\draw (X3_out1) to (Y_out1);
\draw (X2_out2) to (Y_out2);
\draw (X2_out3) to (Y_out3);
\end{tikzpicture}
\hspace{1in}
\begin{tikzpicture}[oriented WD, bb small, baseline=(Y.south)]
\node[bb={1}{3}] (X1) {$a$};
\node[bb={3}{3}, below right=of X1] (X2) {$b$};
\node[bb={2}{1}, above right=of X2] (X3) {$c\color{white}'$};
\node[bb={1}{3}, below=6 of X1] (X1') {$a$};
\node[bb={3}{3}, below right=of X1'] (X2') {$b'$};
\node[bb={2}{1}, above right=of X2'] (X3') {$c'$};
\node[bb={0}{0}, fit={($(X1.north west)+(.3,1.5)$) (X2')  ($(X3'.east)+(-.3,0)$)}] (Y) {};
\node[coordinate] at (Y.west|-X1_in1) (Y_in1) {};
\node[coordinate] at (Y.west|-X2_in3) (Y_in2) {};
\node[coordinate] at (X3_out1-|Y.east) (Y_out1) {};
\node[coordinate] at (X2_out2-|Y.east) (Y_out2) {};
\node[coordinate] at (X2_out3-|Y.east) (Y_out3) {};
\node[coordinate] at (Y.west|-X1'_in1) (Y_in1') {};
\node[coordinate] at (Y.west|-X2'_in3) (Y_in2') {};
\node[coordinate] at (X3'_out1-|Y.east) (Y_out1') {};
\node[coordinate] at (X2'_out2-|Y.east) (Y_out2') {};
\node[coordinate] at (X2'_out3-|Y.east) (Y_out3') {};
\draw (Y_in1) to (X1_in1);
\draw (Y_in2) to (X2_in3);
\draw (X1_out1) to (X3_in1);
\draw (X1_out2) to (X2_in2);
\draw (X1_out3) to (X2_in1);
\draw (X2_out1) to (X3_in2);
\draw (X3_out1) to (Y_out1);
\draw (X2_out2) to (Y_out2);
\draw (X2_out3) to (Y_out3);
\draw (Y_in1') to (X1'_in1);
\draw (Y_in2') to (X2'_in3);
\draw (X1'_out1) to (X3'_in1);
\draw (X1'_out2) to (X2'_in2);
\draw (X1'_out3) to (X2'_in1);
\draw (X2'_out1) to (X3'_in2);
\draw (X3'_out1) to (Y_out1');
\draw (X2'_out2) to (Y_out2');
\draw (X2'_out3) to (Y_out3');
\end{tikzpicture}
\]

Let $P$ be a set, let $R\ss P \times P$ a relation, let $(P,\leq_P)$ be the preorder
obtained by taking the reflexive, transitive closure of $R$, and let $(Q,\leq_Q)$ be an arbitrary preorder. Finally, let $f\colon P\to Q$ be a function, not assumed monotone.

* Suppose that for every $x,y\in P$, if $R(x,y)$ then $f(x)\leq f(y)$. Show that $f$ defines a monotone map $f\colon (P,\leq_P)\to (Q,\leq_Q)$.

* Suppose that $f$ defines a monotone map $f\colon (P,\leq_P)\to (Q,\leq_Q)$. Show that for every $x,y\in P$, if $R(x,y)$ then $f(x)\leq_Q f(y)$.

We call this the universal property of the free preorder.universal

We have a relation $R\ss P\times P$ which generates a preorder $\leq_P$ on $P$, we have an arbitrary preorder $(Q,\leq_Q)$ and a function $f\colon P\to Q$, not necessarily monotonic.

* Assume that for every $x,y\in P$, if $R(x,y)$ then $f(x)\leq f(y)$; we want to show that $f$ is monotone, i.e. that for every $x\leq_Py$ we have $f(x)\leq_Qf(y)$. By definition of $P$ being the reflexive, transitive closure of $R$, we have $x\leq_Py$ iff there exists $n\in\nn$ and $x_0,\ldots,x_n$ in $P$ with $x_0=x$ and $x_n=y$ and $R(x_i,x_{i+1})$ for each $0\leq i\leq n-1$. (The case $n=0$ handles reflexivity.) But then by assumption, $R(x_i,x_{i+1})$ implies $f(x_i)\leq_Q f(x_{i+1})$ for each $i$. By induction on $i$ we show that $f(x_0)\leq_Q f(x_i)$ for all $0\leq i\leq n$, at which point we are done.

* Suppose now that $f$ is monotone, and take $x,y\in P$ for which $R(x,y)$ holds. Then $x\leq_Py$ because $\leq_P$ is the smallest preorder relation containing $R$. (Another way to see this based on the above description is with $n=1$, $x_0=x$, and $x_n=y$, which we said implies $x\leq_Py$.) Since $f$ is monotone, we indeed have $f(x)\leq_Qf(y)$.

Let $P$, $Q$, $R$, etc. be as in <ref>. We want to see that the universal property is really about maps out of—and not maps in to—the reflexive, transitive closure $(P,\leq)$. So let $g\colon Q\to P$ be a function.

* Suppose that for every $a,b\in Q$, if $a\leq b$ then $(g(a),g(b))\in R$. Is it automatically true that $g$ defines a monotone map $g\colon(Q,\leq_Q)\to(P,\leq_P)$?

* Suppose that $g$ defines a monotone map $g\colon(Q,\leq_Q)\to(P,\leq_P)$. Is it automatically true that for every $a,b\in Q$, if $a\leq b$ then $(g(a),g(b))\in R$?

The lesson is that maps between structured objects are defined to preserve
structure. This means the domain of a map must be more constrained than the
codomain. Thus having the fewest additional constraints coincides with having
the most maps out—every function that respects our generating constraints
should define a map.
[A higher-level justification understands freeness
as a left adjoint—of an adjunction often called the syntax/semantics
adjunction—but we will not discuss that here.]

Suppose that $P$, $Q$, and $R$ are as in <ref> and we have a function $g\colon Q\to P$.

* If $R(g(a),g(b))$ holds for all $a\leq_Qb$ then $g$ is monotone, because $R(x,y)$ implies $x\leq_Py$.

* It is possible for $g\colon(Q,\leq_Q)\to(P,\leq_P)$ to be monotone and yet have some $a,b\in Q$ with $a\leq_Qb$ and $(g(a),g(b))\not\in R$. Indeed, take $Q\coloneqq\{1\}$ to be the free preorder on one element, and take $P\coloneqq\{1\}$ with $R=\varnothing$. Then the unique function $g\colon Q\to P$ is monotone (because $\leq_P$ is reflexive even though $R$ is empty), and yet $(g(1),g(1))\not\in R$.

Let $G=(V,A,s,t)$ be a graph, and let $\cat{G}\coloneqq\Cat{Free}(G)$ be the free category on $G$. Let $\cat{C}$ be another category whose set of morphisms is denoted $\Mor(\cat{C})$.

* Someone tells you that there are “domain and codomain” functions $\dom,\cod\colon\Mor(\cat{C})\to\Ob(\cat{C})$; interpret this statement.

* Show that the set of functors $\cat{G} \to
\cat{C}$ are in one-to-one correspondence with the set of pairs of functions
$(f,g)$, where $f\colon V \to \Ob(\cat{C})$ and $g\colon A\to\Mor(\cat{C})$ such that $\dom(g(a))=f(s(a))$ and $\cod(g(a))=f(t(a))$ for all $a\in A$.

* Is $(\Mor(\cat{C}),\Ob(\cat{C}),\dom,\cod)$ a graph? If so, see if you can use the word “adjunction” in a sentence that describes the statement in part 2. If not, explain why not.

Let $G=(V,A,s,t)$ be a graph, let $\cat{G}$ be the free category on $G$, and let $\cat{C}$ be another category, whose set of morphisms is denoted $\Mor(\cat{C})$.

* To give a function $\Mor(\cat{C})\to\Ob(\cat{C})$ means that for every element $\Mor(\cat{C})$ we need to give exactly one element of $\Ob(\cat{C})$. So for $\dom$ we take any $q\in\Mor(\cat{C})$, view it as a morphism $q\colon y\to z$, and send it to its domain $y$. Similarly for $\cod$: we put $\cod(q)\coloneqq z$.

* Suppose first that we are given a functor $F\colon\cat{G}\to\cat{C}$. On objects we have a function $\Ob(\cat{G})\to\Ob(\cat{C})$, and this defines $f$ since $\Ob(\cat{G})=V$. On morphisms, first note that the arrows of graph $G$ are exactly the length=1 paths in $G$, whereas $\Mor(\cat{G})$ is the set of all paths in $G$, so we have an inclusion $A\ss\Mor(\cat{G})$. The functor $F$ provides a function $\Mor(\cat{G})\to\Mor(\cat{C})$, which we can restrict to $A$ to obtain $g\colon A\to\Mor(\cat{C})$. All functors satisfy $\dom(F(r))=F(\dom(r))$ and $\cod(F(r))=F(\cod(r))$ for any $r\colon w\to x$. In particular when $r\in A$ is an arrow we have $\dom(r)=s(r)$ and $\cod(r)=t(r)$. Thus we have found $(f,g)$ with the required properties.

Suppose second that we are given a pair of functions $(f,g)$ where $f\colon V \to \Ob(\cat{C})$ and $g\colon A\to\Mor(\cat{C})$ such that $\dom(g(a))=f(s(a))$ and $\cod(g(a))=f(t(a))$ for all $a\in A$. Define $F\colon\cat{G}\to\cat{C}$ on objects by $f$. An arbitrary morphism in $\cat{G}$ is a path $p\coloneqq(v_0,a_1,a_2,\ldots,a_n)$ in $G$, where $v_0\in V$, $a_i\in A$, $v_0=s(a_1)$, and $t(a_i)=s(a_{i+1})$ for all $1\leq i\leq n-1$. Then $g(a_i)$ is a morphism in $\cat{C}$ whose domain is $f(v_0)$ and the morphisms $g(a_i)$ and $g(a_{i+1})$ are composable for every $1\leq i\leq n-1$. We then take $F(p)\coloneqq \id_{f(v_0)}\cp g(a_1)\cp\cdots\cp g(a_n)$ to be the composite. It is easy to check that this is indeed a functor (preserves identities and compositions).

Third, we want to see that the two operations we just gave are mutually inverse. On objects this is straightforward, and on morphisms it is straightforward to see that, given $(f,g)$, if we turn them into a functor $F\colon\cat{G}\to\cat{C}$ and then extract the new pair of functions $(f',g')$, then $f=f'$ and $g=g'$. Finally, given a functor $F\colon\cat{G}\to\cat{C}$, we extract the pair of functions $(f,g)$ as above and then turn them into a new functor $F'\colon\cat{G}\to\cat{C}$. It is clear that $F$ and $F'$ act the same on objects, so what about on morphisms. The formula says that $F'$ acts the same on morphisms of length $1$ in $\cat{G}$ (i.e. on the elements of $A$). But an arbitrary morphism in $\cat{G}$ is just a path, i.e. a sequence of composable arrows, and so by functoriality, both $F$ and $F'$ must act the same on arbitrary paths.

* $(\Mor(\cat{C}),\Ob(\cat{C}),\dom,\cod)$ is a graph; let's denote it $U(\cat{C})\in\Cat{Grph}$. We have functors $\free\colon\Cat{Grph}\leftrightarrows\smcat\cocolon U$, and $\free$ is left adjoint to $U$.

Recall that monoids are one-object categories. For any set $A$, there is a graph with one vertex and an arrow from the vertex to itself for each $a\in A$. Thus we can construct a free monoid from just the data of a set $A$.

* What are the elements of the free monoid on the set $A=\{a\}$?

* Can you find a well-known monoid that is isomorphic to the free monoid on $\{a\}$?

* What are the elements of the free monoid on the set $A=\{a,b\}$?

* The elements of the free monoid on the set $\{a\}$ are:

\[a^0, a^1, a^2,a^3,\ldots, a^{2019},\ldots\]

with monoid multiplication $*$ given by the usual natural number addition on the exponents, $a^i*a^j=a^{i+j}$.

* This is isomorphic to $\nn$, by sending $a^i\mapsto i$.

* The elements of the free monoid on the set $\{a,b\}$ are `words in $a$ and $b$,' each of which we will represent as a list whose entries are either $a$ or $b$. Here are some:

\[[\;],\quad [a],\quad [b],\quad [a,a],\quad [a,b],\quad \ldots,\quad [b,a,b,b,a,b,a,a,a,a],\quad\ldots\]

Consider the following prop signature:

\[
G\coloneqq\{\rho_{m,n}\colon m \to n \mid m, n \in \nn\},\qquad s(\rho_{m,n})\coloneqq m,\quad t(\rho_{m,n})\coloneqq n,
\]

i.e. having one generating morphism for each $(m,n)\in\nn^2$. Show that $\free(G)$ is the prop of port graphs.

We have two props: the prop of port graphs and the free prop $\free(G,s,t)$ where

\[
G\coloneqq\{\rho_{m,n}\colon m \to n \mid m, n \in \nn\},\qquad s(\rho_{m,n})\coloneqq m,\quad t(\rho_{m,n})\coloneqq n;
\]

we want to show they are the same prop. As categories they have the same set of objects (in both cases, $\nn$), so we need to show that for every $m,n\in\nn$, they have the same set of morphisms (and that their composition formulas and monoidal product formulas agree).

By <ref>, a morphism $m\to n$ in $\free(G)$ is a $G$-labeled port graph, i.e. a pair $(\Gamma,\ell)$, where $\Gamma=(V,\pgin,\pgout,\iota)$ is an $(m,n)$-port graph and $\ell\colon V \to G$ is a function, such that the `arities agree.' What does this mean? Recall that every vertex $v\in V$ is drawn as a box with some left-hand ports and some right-hand ports—an arity—and $\ell(v)\in G$ is supposed to have the correct arity; precisely, $s(\ell(v))=\pgin(v)$ and $t(\ell(v)) = \pgout(v)$. But $G$ was chosen so that it has exactly one element with any given arity, so the function $\ell$ has only one choice, and thus contributes nothing: it neither increases nor decreases the freedom. In other words, a morphism in our particular $\free(G)$ can be identified with an $(m,n)$ port graph $\Gamma$, as desired.

Again by definition <ref>, the `composition and the monoidal structure are just those for port graphs
$\Cat{PG}$ (see <ref>); the labelings (the $\ell$'s) are just carried along.' So we are done.

Consider again the free prop on generators $G=\{f\colon 1 \to 1, g\colon 2 \to 2, h\colon 2 \to
1\}$. Draw a picture of $(f+\id_1+\id_1)\cp(\sigma+\id_1)\cp(\id_1+h)\cp \sigma\cp g$.

Here is a picture of $(f+\id_1+\id_1)\cp(\sigma+\id_1)\cp(\id_1+h)\cp \sigma\cp g$, in the free prop on generators $G=\{f\colon 1 \to 1, g\colon 2 \to 2, h\colon 2 \to

\[
\begin{tikzpicture}[oriented WD, bb port length=0pt, bbx=.7cm, bb port sep=1pt]
\node[bb={1}{1}] (f) {$f$};
\node[bb={2}{1}, below right=1 and 1.5 of f] (h) {$h$};
\node[bb={2}{2}, above right=0 and 1.5 of h] (g) {$g$};
\node[bb={0}{0}, fit=(f) (g) (h)] (outer) {};
\coordinate (outer_in1) at (outer.west|-f_in1);
\coordinate (outer_in2) at (outer.west|-h_in1);
\coordinate (outer_in3) at (outer.west|-h_in2);
\coordinate (outer_out1) at (outer.east|-g_out1);
\coordinate (outer_out2) at (outer.east|-g_out2);
\coordinate (A1) at ($(f_out1)+(0.5,0)$);
\coordinate (A2) at (A1|-outer_in2);
\coordinate (A3) at (A1|-outer_in3);
\coordinate (B1) at ($(A1)+(0.5,0)$);
\coordinate (B2) at (B1|-A2);
\coordinate (B3) at (B1|-A3);
\coordinate (C2) at ($(h_out1)+(0.5,0)$);
\coordinate (C1) at (C2|-A1);
\coordinate (D1) at ($(g_in1)-(0.5,0)$);
\coordinate (D2) at ($(g_in2)-(0.5,0)$);
\draw (outer_in1) -- (f_in1);
\draw (f_out1) -- (A1) -- (B2) -- (h_in1);
\draw (outer_in2) -- (A2) -- (B1) -- (C1) -- (D2) -- (g_in2);
\draw (outer_in3) -- (A3) -- (B3) -- (h_in2);
\draw (h_out1) -- (C2) -- (D1) -- (g_in1);
\draw (g_out1) -- (outer_out1);
\draw (g_out2) -- (outer_out2);
\end{tikzpicture}
\]

Is it the case that the free prop on generators $(G,s,t)$, defined in <ref>, is the same thing as the prop presented by $(G,s,t,\varnothing)$, having no relations, as defined in <ref>? Or is there a subtle difference somehow?

The free prop on generators $(G,s,t)$, defined in <ref>, is—for all intents and purposes—the same thing as the prop presented by $(G,s,t,\varnothing)$, having no relations. The only possible “subtle difference” we might have to admit is if someone said that a set $S$ is “subtly different” than its quotient by the trivial equivalence relation. In the latter, the elements are the singleton subsets of $S$. So for example the quotient of $S=\{1,2,3\}$ by the trivial equivalence relation is the set $\{\{1\}, \{2\}, \{3\}\}$. It is subtly different than $S$, but the two are naturally isomorphic, and category-theoretically, the difference will never make a difference.

* We said in <ref> that for any rig $R$, the set $\Set{Mat}_n(R)$ forms a rig. What is its multiplicative identity $1\in\Set{Mat}_n(R)$?

* We also said that $\Set{Mat}_n(R)$ is generally not commutative. Pick an $n$ and show that that $\Set{Mat}_n(\NN)$ is not commutative, where $\NN$ is as in <ref>.

* If $(R,0,+,1,*)$ is a rig, then the multiplicative identity $1\in\Set{Mat}_n(R)$ is the usual $n$-by-$n$ identity matrix: 1's on the diagonal and 0's everywhere else (where by `1' and `0', we mean those elements of $R$). So for $n=4$ it is:

\[
\left(
\begin{tabular}{cccc}
\end{tabular}
\right).
\]

* We choose $n=2$ and hence need to find two elements $A,B\in\Set{Mat}_2(\nn)$ such that $A*B\neq B*A$.

\[
\begin{array}{cc}
\end{array}
\right)
\left(
\begin{array}{cc}
\end{array}
\right)
\neq
\left(
\begin{array}{cc}
\end{array}
\right)
\left(
\begin{array}{cc}
\end{array}
\right)
\]

One can calculate from the multiplication formula (recalled in <ref>) says $(A*B)(1,1)=0*0+1*1=1$ and $(B*A)(1,1)=0*0+0*0=0$, which are not equal.

The flow graph

\[
\begin{tikzpicture}[scale=.7]
\begin{pgfonlayer}{nodelayer}
\node [style=none] (0) at (-6, -0) {};
\node [style=bdot] (1) at (-5, -0) {};
\node [style=wamp] (2) at (-4, 0.5) {$\scriptstyle 3$};
\node [style=none] (3) at (-4, -0.5) {};
\node [style=wdot] (4) at (-3, -0) {};
\node [style=none] (5) at (-6, 1.5) {};
\node [style=bdot] (6) at (-2.5, 1.5) {};
\node [style=none] (7) at (-1.5, 1) {};
\node [style=wdot] (8) at (-0.5, 0.5) {};
\node [style=none] (9) at (-1.5, 2) {};
\node [style=wamp] (10) at (-0.75, 2) {$\scriptstyle 5$};
\node [style=wdot] (11) at (2.25, 1.5) {};
\node [style=none] (12) at (1.25, 1) {};
\node [style=bdot] (13) at (0.25, 0.5) {};
\node [style=none] (14) at (1.25, -0) {};
\node [style=none] (15) at (3, -0) {};
\node [style=wamp] (16) at (0.5, 2) {$\scriptstyle {3}$};
\node [style=none] (17) at (1.25, 2) {};
\node [style=none] (18) at (-1.5, -0) {};
\node [style=none] (19) at (3, 1.5) {};
\end{pgfonlayer}
\begin{pgfonlayer}{edgelayer}
\draw (0.center) to (1);
\draw [bend left, looseness=1.00] (1) to (2.center);
\draw [bend right, looseness=1.00] (1) to (3.center);
\draw [bend left, looseness=1.00] (2.center) to (4);
\draw [bend right, looseness=1.00] (3.center) to (4);
\draw (4) to (18.center);
\draw [bend right, looseness=1.00] (18.center) to (8);
\draw [bend right, looseness=1.00] (8) to (7.center);
\draw [bend left, looseness=1.00] (7.center) to (6);
\draw (6) to (5);
\draw [bend left, looseness=1.00] (6) to (9.center);
\draw (9.center) to (10.center);
\draw (10.center) to (16.center);
\draw (16.center) to (17.center);
\draw [bend left, looseness=1.00] (17.center) to (11);
\draw [bend left, looseness=1.00] (11) to (12.center);
\draw (11) to (19);
\draw [bend right, looseness=1.00] (12.center) to (13);
\draw (8) to (13);
\draw [bend right, looseness=1.00] (13) to (14.center);
\draw (14.center) to (15.center);
\end{pgfonlayer}
\end{tikzpicture}
\]

takes in two natural numbers, $x$ and $y$, and produces two
output signals. What are they?

Semantically, if we apply the flow graph below to the input signal $(x,y)$

\[
\begin{tikzpicture}[scale=.7]
\begin{pgfonlayer}{nodelayer}
\node [style=none] (0) at (-6, -0) {};
\node [style=bdot] (1) at (-5, -0) {};
\node [style=wamp] (2) at (-4, 0.5) {$\scriptstyle 3$};
\node [style=none] (3) at (-4, -0.5) {};
\node [style=wdot] (4) at (-3, -0) {};
\node [style=none] (5) at (-6, 1.5) {};
\node [style=bdot] (6) at (-2.5, 1.5) {};
\node [style=none] (7) at (-1.5, 1) {};
\node [style=wdot] (8) at (-0.5, 0.5) {};
\node [style=none] (9) at (-1.5, 2) {};
\node [style=wamp] (10) at (-0.75, 2) {$\scriptstyle 5$};
\node [style=wdot] (11) at (2.25, 1.5) {};
\node [style=none] (12) at (1.25, 1) {};
\node [style=bdot] (13) at (0.25, 0.5) {};
\node [style=none] (14) at (1.25, -0) {};
\node [style=none] (15) at (3, -0) {};
\node [style=wamp] (16) at (0.5, 2) {$\scriptstyle {3}$};
\node [style=none] (17) at (1.25, 2) {};
\node [style=none] (18) at (-1.5, -0) {};
\node [style=none] (19) at (3, 1.5) {};
\end{pgfonlayer}
\begin{pgfonlayer}{edgelayer}
\draw (0.center) to (1);
\draw [bend left, looseness=1.00] (1) to (2.center);
\draw [bend right, looseness=1.00] (1) to (3.center);
\draw [bend left, looseness=1.00] (2.center) to (4);
\draw [bend right, looseness=1.00] (3.center) to (4);
\draw (4) to (18.center);
\draw [bend right, looseness=1.00] (18.center) to (8);
\draw [bend right, looseness=1.00] (8) to (7.center);
\draw [bend left, looseness=1.00] (7.center) to (6);
\draw (6) to (5);
\draw [bend left, looseness=1.00] (6) to (9.center);
\draw (9.center) to (10.center);
\draw (10.center) to (16.center);
\draw (16.center) to (17.center);
\draw [bend left, looseness=1.00] (17.center) to (11);
\draw [bend left, looseness=1.00] (11) to (12.center);
\draw (11) to (19);
\draw [bend right, looseness=1.00] (12.center) to (13);
\draw (8) to (13);
\draw [bend right, looseness=1.00] (13) to (14.center);
\draw (14.center) to (15.center);
\end{pgfonlayer}
\end{tikzpicture}
\]

the resulting output signal is $(16x+4y, x+4y)$.

Let $A$ and $B$ be the following matrices with values in $\NN$:

\[
\begin{array}{ccc}
\end{array}
\right)
\hspace{1in}
\begin{array}{cccc}
\end{array}
\right)
\]

What is the monoidal product matrix $A+B$?

The monoidal product of
\begin{array}{ccc}
\end{array}
\right)
\begin{array}{cccc}
\end{array}
\right)

\[
\begin{array}{ccccccc}
\end{array}
\right)
\]

* What matrices does the signal flow graph

\[
\begin{aligned}
\begin{tikzpicture}[spider diagram]
\node[spider={1}{2}, fill=black] (a) {};
\node[special spider={1}{2}{0}{\leglen}, fill=black, right=.1 of a_out1] (b) {};
\draw (a_out1) to (b_in1);
\draw (a_out2) to (b_out1|-a_out2);
\end{tikzpicture}
\end{aligned}
\]

* What about the signal flow graph

\[
\begin{aligned}
\begin{tikzpicture}[spider diagram]
\node[spider={1}{2}, fill=black] (a) {};
\node[special spider={1}{2}{0}{\leglen}, fill=black, right=.1 of a_out2] (b) {};
\draw (a_out2) to (b_in1);
\draw (a_out1) to (b_out1|-a_out1);
\end{tikzpicture}
\end{aligned}
\]

* Are they equal?

* The signal flow graph on the left represents the matrix on the right:

\[
\parbox{1in}{
\begin{aligned}
\begin{tikzpicture}[spider diagram]
\node[spider={1}{2}, fill=black] (a) {};
\node[special spider={1}{2}{0}{\leglen}, fill=black, right=.1 of a_out1] (b) {};
\draw (a_out1) to (b_in1);
\draw (a_out2) to (b_out1|-a_out2);
\end{tikzpicture}
\end{aligned}
\hspace{1in}
\parbox{1in}{$\left(\begin{array}{ccc}1&1&1\end{array}\right)$}
\]

* The signal flow graph on the left represents the matrix on the right:

\[
\parbox{1in}{
\begin{aligned}
\begin{tikzpicture}[spider diagram]
\node[spider={1}{2}, fill=black] (a) {};
\node[special spider={1}{2}{0}{\leglen}, fill=black, right=.1 of a_out2] (b) {};
\draw (a_out2) to (b_in1);
\draw (a_out1) to (b_out1|-a_out1);
\end{tikzpicture}
\end{aligned}$
\hspace{1in}
\parbox{1in}{$\left(\begin{array}{ccc}1&1&1\end{array}\right)$}
\]

* They are equal.

Draw signal flow graphs that represent the following matrices:

* $
\begin{pmatrix}
1 \\
\end{pmatrix}$

* $
\begin{pmatrix}
0 & 0 \\
0 & 0
\end{pmatrix}$

* $
\begin{pmatrix}
1 & 2 & 3\\
4 & 5 & 6
\end{pmatrix}$

\[
\begin{pmatrix}
0 \\
1 \\
\end{pmatrix}\qquad \sim \qquad
\begin{aligned}
\begin{tikzpicture}[oriented WD, spider diagram, bbx=3ex, bby=2ex]
\node[spider={2}{1}, fill=white] (add) {};
\node[spider={1}{1}, wamp,left=.2 of add_in2] (scalar) {$2$};
\node[spider={1}{0}, fill=black, above =1 of add_in1] (unit) {};
\draw (add_in1-|scalar_in1) -- (add_in1);
\draw (unit_in1-|scalar_in1) -- (unit_in1);
\end{tikzpicture}
\end{aligned}
\]

\[
\begin{pmatrix}
0 & 0 \\
0 & 0
\end{pmatrix}\qquad \sim \qquad
\begin{aligned}
\begin{tikzpicture}[oriented WD, spider diagram, bbx=3ex, bby=2ex]
\node[spider={1}{0}, fill=black] (b1) {};
\node[spider={1}{0}, fill=black, below=.5 of b1] (b2) {};
\node[spider={0}{1}, fill=white, right=1 of b1] (w1) {};
\node[spider={0}{1}, fill=white, below=.5 of w1] (w2) {};
\end{tikzpicture}
\end{aligned}
\]

\[
\begin{pmatrix}
1 & 2 & 3\\
4 & 5 & 6
\end{pmatrix}\qquad \sim \qquad
\begin{aligned}
\begin{tikzpicture}[oriented WD, spider diagram, bbx=3ex, bby=2ex]
\coordinate (s1) at (0,0) ;
\node[spider={1}{1}, wamp,below=.4 of s1] (s2) {$2$};
\node[spider={1}{1}, wamp,below=.4 of s2] (s3) {$3$};
\node[spider={1}{1}, wamp,below=.4 of s3] (s4) {$4$};
\node[spider={1}{1}, wamp,below=.4 of s4] (s5) {$5$};
\node[spider={1}{1}, wamp,below=.4 of s5] (s6) {$6$};
\node[spider={2}{1}, fill=white] (add1) at ($(s1)!.5!(s2)+(5,0)$) {};
\node[spider={2}{1}, fill=white] (add2) at ($(s3)!.5!(s4)+(5,0)$) {};
\node[spider={2}{1}, fill=white] (add3) at ($(s5)!.5!(s6)+(5,0)$) {};
\node[spider={1}{2}, fill=black] (copy1) at ($(s2)-(5,0)$) {};
\node[spider={1}{2}, fill=black] (copy2) at ($(copy1_out2)+(1,0)$) {};
\node[spider={1}{2}, fill=black] (copy3) at ($(s5)-(5,0)$) {};
\node[spider={1}{2}, fill=black] (copy4) at ($(copy3_out2)+(1,0)$) {};
\draw (copy1_out1) to (s1);
\draw (copy1_out2) to (copy2_in1);
\draw (copy2_out1) to (s2_in1);
\draw (copy2_out2) to (s3_in1);
\draw (copy3_out1) to (s4_in1);
\draw (copy3_out2) to (copy4_in1);
\draw (copy4_out1) to (s5_in1);
\draw (copy4_out2) to (s6_in1);
\draw (s1) to (add1_in1);
\draw (s2_out1) to (add2_in1);
\draw (s3_out1) to (add3_in1);
\draw (s4_out1) to (add1_in2);
\draw (s5_out1) to (add2_in2);
\draw (s6_out1) to (add3_in2);
\end{tikzpicture}
\end{aligned}
\]

Write down a detailed proof of <ref>. Suppose $M$ is an $m \times
n$-matrix. Follow the idea of the $(2\times 2)$-case in <ref>,
and construct the signal flow graph $g$—having $m$ inputs and $n$ outputs—as
the composite of four layers, respectively comprising (i) copy maps, (ii)
scalars, (iii) swaps and identities, (iv) addition maps.

* For the first layer $g_1$, take the monoidal product of $m$ copies of $c_n$,

\[
g_1\coloneq c_n +\dots+ c_n\colon m \to (m \times n),
\]

where $c_n$ is the signal flow diagram that makes $n$ copies of a single input:

\[
\comult{1em}\cp (1+\comult{1em})\cp (1+1+\comult{1em})\cp \dots\cp (1+\dots+1+\comult{1em})\colon
1 \to n
\]

* Next, define

\begin{align*}
g_2\coloneq &\quad s_{M(1,1)}+\cdots+s_{M(1,n)} \\
& +s_{M(2,1)}+\cdots+s_{M(2,n)} \\
&+\cdots \\
&+s_{M(m,1)}+\cdots+s_{M(m,n)}\colon (m\times n) \to (m\times n),
\end{align*}

where $s_a\colon 1 \to 1$ is the signal flow
graph generator “scalar multiplication by $a$.” This layer amplifies each copy of the input signal by the
relevant rig element.

* The third layer rearranges wires. We will not write this down
explicitly, but simply say it is the signal flow graph $g_3\colon m \times
n \to m \times n$, that is the
composite and monoidal product of swap and identity maps, such that the
$(i-1)m+j$th input is sent to the $(j-1)n+i$th output, for all $1 \le i \le n$
and $1 \le j \le m$.

* Finally, the fourth layer is similar to the first, but instead adds the
amplified input signals. We define

\[
g_4\coloneq a_m+\dots+a_m \colon (m \times n)\to n,
\]

where $a_m$ is the signal flow graph that adds $m$ inputs to produce a single output:

\[
(1+\dots+1+\add{1em})\cp \cdots\cp(1+1+\add{1em})\cp(1+\add{1em})\cp\add{1em}\colon
m \to 1
\]

Using <ref>, it is a straightforward but tedious calculation to show that $g=g_1\cp g_2\cp g_3\cp g_4\colon m \to n$ has the property that $S(g)=M$.

* For each matrix in <ref>, draw another signal flow graph that
represents that matrix.

* Using the above equations and the prop axioms, prove
that the two signal flow graphs represent the same matrix.

* The matrices in <ref> may also be drawn as the following
signal flow graphs:

\[
\begin{pmatrix}
0 \\
1 \\
\end{pmatrix}\qquad \sim \qquad
\begin{aligned}
\begin{tikzpicture}[oriented WD, spider diagram, bbx=3ex, bby=2ex]
\node[spider={2}{1}, fill=white] (add2) {};
\node[special spider={2}{1}{\leglen}{0}, fill=white, left=.2 of add2_in2] (add) {};
\node[spider={1}{2}, fill=black,left=2 of add] (copy) {};
\node[spider={1}{0}, fill=black, above =2 of add_in1] (unit) {};
\draw (add2_in1-|copy_in1) -- (add2_in1);
\draw (unit_in1-|copy_in1) -- (unit_in1);
\draw (copy_out1) -- (add_in1);
\draw (copy_out2) -- (add_in2);
\draw (add.0) -- (add2_in2);
\end{tikzpicture}
\end{aligned}
\]

\[
\begin{pmatrix}
0 & 0 \\
0 & 0
\end{pmatrix}\qquad \sim \qquad
\begin{aligned}
\begin{tikzpicture}[oriented WD, spider diagram, bbx=3ex, bby=2ex]
\node[spider={2}{1}, fill=white] (add) {};
\node[special spider={1}{1}{.1}{0}, wamp, right=0 of add_out1]
(scalar) {$0$};
\node[spider={1}{2}, fill=black,right=.8 of scalar] (copy) {};
\draw (add_out1) -- (scalar.180);
\draw (scalar.0) -- (copy_in1);
\end{tikzpicture}
\end{aligned}
\]

\[
\begin{pmatrix}
1 & 2 & 3\\
4 & 5 & 6
\end{pmatrix}\qquad \sim \qquad
\begin{aligned}
\begin{tikzpicture}[oriented WD, spider diagram, bbx=3ex, bby=2ex]
\coordinate (s1) at (0,0) ;
\node[spider={1}{1}, wamp,below=.3 of s1] (s2) {$2$};
\node[spider={1}{1}, wamp,below=.6 of s2] (s3) {$3$};
\node[spider={1}{1}, wamp,below=1.2 of s3] (s5) {$5$};
\node[spider={1}{1}, wamp] (s4) at ($(s3)!.5!(s5)+(4,0)$) {$4$};
\node[spider={1}{1}, wamp,below left=.4 of s5] (s6) {$6$};
\node[special spider={2}{1}{\leglen}{.2}, fill=white] (add2) at ($(s1)!.5!(s2)+(6,-1)$) {};
\node[special spider={2}{1}{\leglen}{.2}, fill=white] (add1) at ($(s2)!.5!(s5)+(6,-.38)$) {};
\node[special spider={2}{1}{\leglen}{.2}, fill=white] (add3) at ($(s5)!.5!(s6)+(4,0)$) {};
\node[spider={1}{2}, fill=black] (copy1) at ($(s2)-(5,0)$) {};
\node[spider={1}{2}, fill=black] (copy2) at ($(copy1_out2)+(1,0)$) {};
\node[spider={1}{2}, fill=black] (copy3) at ($(s5)-(5,0)$) {};
\node[spider={1}{2}, fill=black] (copy4) at ($(copy3_out1)+(1,0)$) {};
\coordinate (out1) at ($(add2)+(2,0)$) ;
\coordinate (out2) at ($(add1)+(2,0)$) ;
\coordinate (out3) at (add3-|out1) ;
\draw (copy1_out1) to (s1);
\draw (copy1_out2) to (copy2_in1);
\draw (copy2_out1) to (s2_in1);
\draw (copy2_out2) to (s3_in1);
\draw (copy3_out1) to (copy4_in1);
\draw (copy4_out1) to (s4_in1);
\draw (copy4_out2) to (s5_in1);
\draw (copy3_out2) to (s6_in1);
\draw (s1) to (add1_in1);
\draw (s2_out1) to (add2_in1);
\draw (s3_out1) to (add3_in1);
\draw (s4_out1) to (add1_in2);
\draw (s5_out1) to (add2_in2);
\draw (s6_out1) to (add3_in2);
\draw (add1_out1) to (out1);
\draw (add2_out1) to (out2);
\draw (add3_out1) to (out3);
\end{tikzpicture}
\end{aligned}
\]

* Here are graphical proofs that the representations we chose in our
solution to <ref> agree with those chosen in Part 1 above.

\[
\begin{aligned}
\begin{tikzpicture}[oriented WD, spider diagram, bbx=3ex, bby=2ex]
\node[spider={2}{1}, fill=white] (add2) {};
\node[special spider={2}{1}{\leglen}{0}, fill=white, left=.2 of add2_in2] (add) {};
\node[spider={1}{2}, fill=black,left=2 of add] (copy) {};
\node[spider={1}{0}, fill=black, above =2 of add_in1] (unit) {};
\draw (add2_in1-|copy_in1) -- (add2_in1);
\draw (unit_in1-|copy_in1) -- (unit_in1);
\draw (copy_out1) -- (add_in1);
\draw (copy_out2) -- (add_in2);
\draw (add.0) -- (add2_in2);
\end{tikzpicture}
\end{aligned}
\quad=\quad
\begin{aligned}
\begin{tikzpicture}[oriented WD, spider diagram, bbx=3ex, bby=2ex]
\node[spider={2}{1}, fill=white] (add2) {};
\node[special spider={2}{1}{\leglen}{0}, fill=white, left=.2 of add2_in2] (add) {};
\node[special spider={1}{1}{.1}{0}, wamp,left=0 of add_in1] (scalar1) {$1$};
\node[special spider={1}{1}{.1}{0}, wamp,left=0 of add_in2] (scalar2) {$1$};
\node[spider={1}{2}, fill=black,left=3 of add] (copy) {};
\node[spider={1}{0}, fill=black, above =2 of add_in1] (unit) {};
\draw (add2_in1-|copy_in1) -- (add2_in1);
\draw (unit_in1-|copy_in1) -- (unit_in1);
\draw (copy_out1) -- (scalar1.180);
\draw (copy_out2) -- (scalar2.180);
\draw (scalar1.0) -- (add_in1);
\draw (scalar2.0) -- (add_in2);
\draw (add.0) -- (add2_in2);
\end{tikzpicture}
\end{aligned}
\quad=\quad
\begin{aligned}
\begin{tikzpicture}[oriented WD, spider diagram, bbx=3ex, bby=2ex]
\node[spider={2}{1}, fill=white] (add) {};
\node[spider={1}{1}, wamp,left=.2 of add_in2] (scalar) {$2$};
\node[spider={1}{0}, fill=black, above =1 of add_in1] (unit) {};
\draw (add_in1-|scalar_in1) -- (add_in1);
\draw (unit_in1-|scalar_in1) -- (unit_in1);
\end{tikzpicture}
\end{aligned}
\]

\[
\begin{aligned}
\begin{tikzpicture}[oriented WD, spider diagram, bbx=3ex, bby=2ex]
\node[spider={2}{1}, fill=white] (add) {};
\node[special spider={1}{1}{.1}{0}, wamp, right=0 of add_out1]
(scalar) {$0$};
\node[spider={1}{2}, fill=black,right=.8 of scalar] (copy) {};
\draw (add_out1) -- (scalar.180);
\draw (scalar.0) -- (copy_in1);
\end{tikzpicture}
\end{aligned}
\quad = \quad
\begin{aligned}
\begin{tikzpicture}[oriented WD, spider diagram, bbx=3ex, bby=2ex]
\node[spider={2}{1}, fill=white] (add) {};
\node[special spider={1}{0}{.1}{0}, fill=black]	(counit) at (add_out1) {};
\node[spider={1}{2}, fill=black,right=3 of add] (copy) {};
\node[special spider={0}{1}{.1}{0}, fill=white]	(unit) at (copy_in1) {};
\end{tikzpicture}
\end{aligned}
\quad = \quad
\begin{aligned}
\begin{tikzpicture}[oriented WD, spider diagram, bbx=3ex, bby=2ex]
\node[spider={1}{0}, fill=black] (b1) {};
\node[spider={1}{0}, fill=black, below=.5 of b1] (b2) {};
\node[spider={0}{1}, fill=white, right=1 of b1] (w1) {};
\node[spider={0}{1}, fill=white, below=.5 of w1] (w2) {};
\end{tikzpicture}
\end{aligned}
\]

\begin{align*}
\begin{aligned}
\begin{tikzpicture}[oriented WD, spider diagram, bbx=3ex, bby=2ex,font=\small, scale=.8]
\coordinate (s1) at (0,0) ;
\node[spider={1}{1}, wamp,below=.3 of s1] (s2) {$2$};
\node[spider={1}{1}, wamp,below=.6 of s2] (s3) {$3$};
\node[spider={1}{1}, wamp,below=1.2 of s3] (s5) {$5$};
\node[spider={1}{1}, wamp] (s4) at ($(s3)!.5!(s5)+(4,0)$) {$4$};
\node[spider={1}{1}, wamp,below left=.4 of s5] (s6) {$6$};
\node[special spider={2}{1}{\leglen}{.2}, fill=white] (add2) at ($(s1)!.5!(s2)+(6,-1)$) {};
\node[special spider={2}{1}{\leglen}{.2}, fill=white] (add1) at ($(s2)!.5!(s5)+(6,-.38)$) {};
\node[special spider={2}{1}{\leglen}{.2}, fill=white] (add3) at ($(s5)!.5!(s6)+(4,0)$) {};
\node[spider={1}{2}, fill=black] (copy1) at ($(s2)-(5,0)$) {};
\node[spider={1}{2}, fill=black] (copy2) at ($(copy1_out2)+(1,0)$) {};
\node[spider={1}{2}, fill=black] (copy3) at ($(s5)-(5,0)$) {};
\node[spider={1}{2}, fill=black] (copy4) at ($(copy3_out1)+(1,0)$) {};
\coordinate (out1) at ($(add2)+(2,0)$) ;
\coordinate (out2) at ($(add1)+(2,0)$) ;
\coordinate (out3) at (add3-|out1) ;
\draw (copy1_out1) to (s1);
\draw (copy1_out2) to (copy2_in1);
\draw (copy2_out1) to (s2_in1);
\draw (copy2_out2) to (s3_in1);
\draw (copy3_out1) to (copy4_in1);
\draw (copy4_out1) to (s4_in1);
\draw (copy4_out2) to (s5_in1);
\draw (copy3_out2) to (s6_in1);
\draw (s1) to (add1_in1);
\draw (s2_out1) to (add2_in1);
\draw (s3_out1) to (add3_in1);
\draw (s4_out1) to (add1_in2);
\draw (s5_out1) to (add2_in2);
\draw (s6_out1) to (add3_in2);
\draw (add1_out1) to (out1);
\draw (add2_out1) to (out2);
\draw (add3_out1) to (out3);
\end{tikzpicture}
\end{aligned}
= \quad
\begin{aligned}
\begin{tikzpicture}[oriented WD, spider diagram, bbx=3ex, bby=2ex,font=\small, scale=.7]
\coordinate (s1) at (0,0) ;
\node[spider={1}{1}, wamp,below=.35 of s1] (s2) {$2$};
\node[spider={1}{1}, wamp,below=.35 of s2] (s3) {$3$};
\node[spider={1}{1}, wamp,below=.35 of s3] (s4) {$4$};
\node[spider={1}{1}, wamp,below=.35 of s4] (s5) {$5$};
\node[spider={1}{1}, wamp,below=.35 of s5] (s6) {$6$};
\node[special spider={2}{1}{\leglen}{.2}, fill=white] (add2) at ($(s1)!.5!(s2)+(5,0)$) {};
\node[special spider={2}{1}{\leglen}{.2}, fill=white] (add1) at ($(s3)!.5!(s4)+(5,-.5)$) {};
\node[special spider={2}{1}{\leglen}{.2}, fill=white] (add3) at ($(s5)!.5!(s6)+(5,0)$) {};
\node[spider={1}{2}, fill=black] (copy1) at ($(s2)-(5,0)$) {};
\node[spider={1}{2}, fill=black] (copy2) at ($(copy1_out2)+(1,0)$) {};
\node[spider={1}{2}, fill=black] (copy3) at ($(s5)-(5,0)$) {};
\node[spider={1}{2}, fill=black] (copy4) at ($(copy3_out1)+(1,0)$) {};
\coordinate (out1) at ($(add2)+(2,0)$) ;
\coordinate (out2) at ($(add1)+(2,0)$) ;
\coordinate (out3) at ($(add3)+(2,0)$) ;
\draw (copy1_out1) to (s1);
\draw (copy1_out2) to (copy2_in1);
\draw (copy2_out1) to (s2_in1);
\draw (copy2_out2) to (s3_in1);
\draw (copy3_out1) to (copy4_in1);
\draw (copy4_out1) to (s4_in1);
\draw (copy4_out2) to (s5_in1);
\draw (copy3_out2) to (s6_in1);
\draw (s1) to (add1_in1);
\draw (s2_out1) to (add2_in1);
\draw (s3_out1) to (add3_in1);
\draw (s4_out1) to (add1_in2);
\draw (s5_out1) to (add2_in2);
\draw (s6_out1) to (add3_in2);
\draw (add1_out1) to (out1);
\draw (add2_out1) to (out2);
\draw (add3_out1) to (out3);
\end{tikzpicture}
\end{aligned}\\
\qquad&= \quad
\begin{aligned}
\begin{tikzpicture}[oriented WD, spider diagram, bbx=3ex, bby=2ex,font=\small, scale=.7]
\coordinate (s1) at (0,0) ;
\node[spider={1}{1}, wamp,below=.3 of s1] (s2) {$2$};
\node[spider={1}{1}, wamp,below=.3 of s2] (s3) {$3$};
\node[spider={1}{1}, wamp,below=.3 of s3] (s4) {$4$};
\node[spider={1}{1}, wamp,below=.3 of s4] (s5) {$5$};
\node[spider={1}{1}, wamp,below=.3 of s5] (s6) {$6$};
\node[spider={2}{1}, fill=white] (add1) at ($(s1)!.5!(s2)+(5,0)$) {};
\node[spider={2}{1}, fill=white] (add2) at ($(s3)!.5!(s4)+(5,0)$) {};
\node[spider={2}{1}, fill=white] (add3) at ($(s5)!.5!(s6)+(5,0)$) {};
\node[spider={1}{2}, fill=black] (copy1) at ($(s2)-(5,0)$) {};
\node[spider={1}{2}, fill=black] (copy2) at ($(copy1_out2)+(1,0)$) {};
\node[spider={1}{2}, fill=black] (copy3) at ($(s5)-(5,0)$) {};
\node[spider={1}{2}, fill=black] (copy4) at ($(copy3_out1)+(1,0)$) {};
\draw (copy1_out1) to (s1);
\draw (copy1_out2) to (copy2_in1);
\draw (copy2_out1) to (s2_in1);
\draw (copy2_out2) to (s3_in1);
\draw (copy3_out1) to (copy4_in1);
\draw (copy3_out2) to (s6_in1);
\draw (copy4_out1) to (s4_in1);
\draw (copy4_out2) to (s5_in1);
\draw (s1) to (add1_in1);
\draw (s2_out1) to (add2_in1);
\draw (s3_out1) to (add3_in1);
\draw (s4_out1) to (add1_in2);
\draw (s5_out1) to (add2_in2);
\draw (s6_out1) to (add3_in2);
\end{tikzpicture}
\end{aligned} = \quad
\begin{aligned}
\begin{tikzpicture}[oriented WD, spider diagram, bbx=3ex, bby=2ex,font=\small, scale=.7]
\coordinate (s1) at (0,0) ;
\node[spider={1}{1}, wamp,below=.3 of s1] (s2) {$2$};
\node[spider={1}{1}, wamp,below=.3 of s2] (s3) {$3$};
\node[spider={1}{1}, wamp,below=.3 of s3] (s4) {$4$};
\node[spider={1}{1}, wamp,below=.3 of s4] (s5) {$5$};
\node[spider={1}{1}, wamp,below=.3 of s5] (s6) {$6$};
\node[spider={2}{1}, fill=white] (add1) at ($(s1)!.5!(s2)+(5,0)$) {};
\node[spider={2}{1}, fill=white] (add2) at ($(s3)!.5!(s4)+(5,0)$) {};
\node[spider={2}{1}, fill=white] (add3) at ($(s5)!.5!(s6)+(5,0)$) {};
\node[spider={1}{2}, fill=black] (copy1) at ($(s2)-(5,0)$) {};
\node[spider={1}{2}, fill=black] (copy2) at ($(copy1_out2)+(1,0)$) {};
\node[spider={1}{2}, fill=black] (copy3) at ($(s5)-(5,0)$) {};
\node[spider={1}{2}, fill=black] (copy4) at ($(copy3_out2)+(1,0)$) {};
\draw (copy1_out1) to (s1);
\draw (copy1_out2) to (copy2_in1);
\draw (copy2_out1) to (s2_in1);
\draw (copy2_out2) to (s3_in1);
\draw (copy3_out1) to (s4_in1);
\draw (copy3_out2) to (copy4_in1);
\draw (copy4_out1) to (s5_in1);
\draw (copy4_out2) to (s6_in1);
\draw (s1) to (add1_in1);
\draw (s2_out1) to (add2_in1);
\draw (s3_out1) to (add3_in1);
\draw (s4_out1) to (add1_in2);
\draw (s5_out1) to (add2_in2);
\draw (s6_out1) to (add3_in2);
\end{tikzpicture}
\end{aligned}
\end{align*}

Consider the signal flow graphs

\begin{equation}\label{eqn.exc_two_sfgs}
\begin{aligned}
\begin{tikzpicture}[scale=.7]
\begin{pgfonlayer}{nodelayer}
\node [style=none] (0) at (4, -0) {};
\node [style=none] (1) at (0, 1) {};
\node [style=none] (2) at (0, -0) {};
\node [style=none] (3) at (4, 1) {};
\node [style=bdot] (4) at (1.5, 1) {};
\node [style=wdot] (5) at (2.5, 1) {};
\node [style=bdot] (6) at (1.5, -0) {};
\node [style=wdot] (7) at (2.5, -0) {};
\end{pgfonlayer}
\begin{pgfonlayer}{edgelayer}
\draw (1.center) to (4);
\draw (5) to (3.center);
\draw (2.center) to (6);
\draw (7) to (0.center);
\end{pgfonlayer}
\end{tikzpicture}
\end{aligned}
\quad \mbox{and} \quad
\begin{aligned}
\begin{tikzpicture}[scale=.7]
\begin{pgfonlayer}{nodelayer}
\node [style=none] (3) at (-9, 2) {};
\node [style=none] (22) at (-9, -0) {};
\node [style=bdot] (21) at (-8, -0) {};
\node [style=none] (20) at (-7, -0.5) {};
\node [style=wamp] (23) at (-7, 0.625) {$\scriptstyle 3$};
\node [style=wamp] (19) at (-6.5, 2) {$\scriptstyle 5$};
\node [style=bdot] (26) at (-6.25, 0.625) {};
\node [style=wamp] (18) at (-5.25, 2) {$\scriptstyle {3}$};
\node [style=wamp] (24) at (-5.25, 1) {$\scriptstyle 3$};
\node [style=none] (25) at (-5.25, 0.25) {};
\node [style=none] (28) at (-4.25, 1) {};
\node [style=none] (29) at (-4.25, 2) {};
\node [style=wamp] (0) at (-4, 0.25) {$\scriptstyle 3$};
\node [style=none] (1) at (-4, -0.5) {};
\node [style=wdot] (27) at (-3.25, 1.5) {};
\node [style=wdot] (2) at (-3, -0.125) {};
\node [style=bdot] (4) at (-2.5, 1.5) {};
\node [style=none] (5) at (-1.5, 1) {};
\node [style=none] (7) at (-1.5, 2) {};
\node [style=none] (16) at (-1.5, -0.125) {};
\node [style=wamp] (8) at (-0.75, 2) {$\scriptstyle 5$};
\node [style=wdot] (6) at (-0.5, 0.5) {};
\node [style=bdot] (11) at (0.25, 0.5) {};
\node [style=wamp] (14) at (0.5, 2) {$\scriptstyle {3}$};
\node [style=none] (10) at (1.25, 1) {};
\node [style=none] (12) at (1.25, -0) {};
\node [style=none] (15) at (1.25, 2) {};
\node [style=wdot] (9) at (2.25, 1.5) {};
\node [style=none] (13) at (3, -0) {};
\node [style=none] (17) at (3, 1.5) {};
\end{pgfonlayer}
\begin{pgfonlayer}{edgelayer}
\draw [bend left, looseness=1.00] (0.center) to (2);
\draw [bend right, looseness=0.9] (1.center) to (2);
\draw (2) to (16.center);
\draw [bend right, looseness=1.00] (16.center) to (6);
\draw [bend right, looseness=1.00] (6) to (5.center);
\draw [bend left, looseness=1.00] (5.center) to (4);
\draw [bend left, looseness=1.00] (4) to (7.center);
\draw (7.center) to (8.center);
\draw (8.center) to (14.center);
\draw (14.center) to (15.center);
\draw [bend left, looseness=1.00] (15.center) to (9);
\draw [bend left, looseness=1.00] (9) to (10.center);
\draw (9) to (17.center);
\draw [bend right, looseness=1.00] (10.center) to (11);
\draw (6) to (11);
\draw [bend right, looseness=1.00] (11) to (12.center);
\draw (12.center) to (13.center);
\draw (19) to (18);
\draw (3.center) to (19);
\draw (19) to (18);
\draw (22.center) to (21);
\draw [bend left, looseness=1.00] (21) to (23);
\draw [bend right, looseness=1.00] (21) to (20.center);
\draw [bend left, looseness=1.00] (26) to (24);
\draw [bend right, looseness=0.9] (26) to (25.center);
\draw (23) to (26);
\draw (20.center) to (1.center);
\draw [bend left, looseness=1.00] (29.center) to (27);
\draw [bend left, looseness=1.00] (27) to (28.center);
\draw (27) to (4);
\draw (18) to (29.center);
\draw (24) to (28.center);
\draw (25.center) to (0);
\end{pgfonlayer}
\end{tikzpicture}
\end{aligned}
\end{equation}

* Let $R=(\NN,0,+,1,*)$. By examining the presentation of $\mat(R)$ in <ref>, and without computing the
matrices that they represent, conjecture whether they represent the same matrix. How could you prove your conjecture?

* Now suppose the rig is $R=\NN/3$; if you do not know what this means, just replace all 3's with 0's in the right-hand diagram of <ref>. Find what you would call a minimal representation of this diagram, using the presentation in <ref>.

* The signal flow graphs

\[
\begin{aligned}
\begin{tikzpicture}[scale=.7]
\begin{pgfonlayer}{nodelayer}
\node [style=none] (0) at (4, -0) {};
\node [style=none] (1) at (0, 1) {};
\node [style=none] (2) at (0, -0) {};
\node [style=none] (3) at (4, 1) {};
\node [style=bdot] (4) at (1.5, 1) {};
\node [style=wdot] (5) at (2.5, 1) {};
\node [style=bdot] (6) at (1.5, -0) {};
\node [style=wdot] (7) at (2.5, -0) {};
\end{pgfonlayer}
\begin{pgfonlayer}{edgelayer}
\draw (1.center) to (4);
\draw (5) to (3.center);
\draw (2.center) to (6);
\draw (7) to (0.center);
\end{pgfonlayer}
\end{tikzpicture}
\end{aligned}
\quad \mbox{and} \quad
\begin{aligned}
\begin{tikzpicture}[scale=.7]
\begin{pgfonlayer}{nodelayer}
\node [style=none] (3) at (-9, 2) {};
\node [style=none] (22) at (-9, -0) {};
\node [style=bdot] (21) at (-8, -0) {};
\node [style=none] (20) at (-7, -0.5) {};
\node [style=wamp] (23) at (-7, 0.625) {$\scriptstyle 3$};
\node [style=wamp] (19) at (-6.5, 2) {$\scriptstyle 5$};
\node [style=bdot] (26) at (-6.25, 0.625) {};
\node [style=wamp] (18) at (-5.25, 2) {$\scriptstyle {3}$};
\node [style=wamp] (24) at (-5.25, 1) {$\scriptstyle 3$};
\node [style=none] (25) at (-5.25, 0.25) {};
\node [style=none] (28) at (-4.25, 1) {};
\node [style=none] (29) at (-4.25, 2) {};
\node [style=wamp] (0) at (-4, 0.25) {$\scriptstyle 3$};
\node [style=none] (1) at (-4, -0.5) {};
\node [style=wdot] (27) at (-3.25, 1.5) {};
\node [style=wdot] (2) at (-3, -0.125) {};
\node [style=bdot] (4) at (-2.5, 1.5) {};
\node [style=none] (5) at (-1.5, 1) {};
\node [style=none] (7) at (-1.5, 2) {};
\node [style=none] (16) at (-1.5, -0.125) {};
\node [style=wamp] (8) at (-0.75, 2) {$\scriptstyle 5$};
\node [style=wdot] (6) at (-0.5, 0.5) {};
\node [style=bdot] (11) at (0.25, 0.5) {};
\node [style=wamp] (14) at (0.5, 2) {$\scriptstyle {3}$};
\node [style=none] (10) at (1.25, 1) {};
\node [style=none] (12) at (1.25, -0) {};
\node [style=none] (15) at (1.25, 2) {};
\node [style=wdot] (9) at (2.25, 1.5) {};
\node [style=none] (13) at (3, -0) {};
\node [style=none] (17) at (3, 1.5) {};
\end{pgfonlayer}
\begin{pgfonlayer}{edgelayer}
\draw [bend left, looseness=1.00] (0.center) to (2);
\draw [bend right, looseness=0.9] (1.center) to (2);
\draw (2) to (16.center);
\draw [bend right, looseness=1.00] (16.center) to (6);
\draw [bend right, looseness=1.00] (6) to (5.center);
\draw [bend left, looseness=1.00] (5.center) to (4);
\draw [bend left, looseness=1.00] (4) to (7.center);
\draw (7.center) to (8.center);
\draw (8.center) to (14.center);
\draw (14.center) to (15.center);
\draw [bend left, looseness=1.00] (15.center) to (9);
\draw [bend left, looseness=1.00] (9) to (10.center);
\draw (9) to (17.center);
\draw [bend right, looseness=1.00] (10.center) to (11);
\draw (6) to (11);
\draw [bend right, looseness=1.00] (11) to (12.center);
\draw (12.center) to (13.center);
\draw (19) to (18);
\draw (3.center) to (19);
\draw (19) to (18);
\draw (22.center) to (21);
\draw [bend left, looseness=1.00] (21) to (23);
\draw [bend right, looseness=1.00] (21) to (20.center);
\draw [bend left, looseness=1.00] (26) to (24);
\draw [bend right, looseness=0.9] (26) to (25.center);
\draw (23) to (26);
\draw (20.center) to (1.center);
\draw [bend left, looseness=1.00] (29.center) to (27);
\draw [bend left, looseness=1.00] (27) to (28.center);
\draw (27) to (4);
\draw (18) to (29.center);
\draw (24) to (28.center);
\draw (25.center) to (0);
\end{pgfonlayer}
\end{tikzpicture}
\end{aligned}
\]

cannot represent the same morphism because one has a path from a vertex on the left to one on the right, and the other does not. To prove this, observe that the only graphical equation in <ref> that breaks a path from left to right is the equation

\[
\begin{aligned}
\begin{tikzpicture}[spider diagram, leg length=20pt]
\node[spider={1}{1}, wamp] (a) {$\scriptstyle \mathsf 0$};
\end{tikzpicture}
\end{aligned}
\begin{aligned}
\begin{tikzpicture}[spider diagram]
\node[spider={1}{0}, fill=black] (a) {};
\node[spider={0}{1}, fill=white, right=.3 of a] (b) {};
\end{tikzpicture}
\end{aligned}
\]

So a $0$ scalar must within a path from left to right before we could rewrite the diagram to break that path. No such $0$ scalar can appear, however, because the diagram does not contain any, and the sum and product of any two nonzero natural numbers is always nonzero.

* Replacing each of the $3$s with $0$ allows us to rewrite the diagram to

\[
\begin{tikzpicture}[spider diagram, leg length=20pt]
\node[spider={1}{0}, fill=black] (a) {};
\node[spider={1}{2}, fill=black, below=.25 of a] (b) {};
\draw (a_in1|-b_in1) to (b_in1);
\end{tikzpicture}
\]

Consider the set $\RR$ of real numbers.

* Show that if $\mu\colon\RR\times\RR\to\RR$ is defined by $\mu(a,b)=a*b$ and if $\eta\in\RR$ is defined to be $\eta=1$, then $(\RR,*,1)$ satisfies all three conditions of <ref>.

* Show that if $\mu\colon\RR\times\RR\to\RR$ is defined by $\mu(a,b)=a+b$ and if $\eta\in\RR$ is defined to be $\eta=0$, then $(\RR,+,0)$ satisfies all three conditions of <ref>.

The three conditions of <ref> are

* $(\mu \otimes \id)\cp\mu = (\id \otimes \mu)\cp\mu$,

* $(\eta \otimes \id)\cp\mu = \id = (\id \otimes \eta)\cp\mu$, and

* $\sigma_{M,M}\cp\mu = \mu$.

where $\sigma_{M,M}$ is the swap map on $M$ in $\cat{C}$.

* Suppose $\mu\colon\RR\times\RR\to\RR$ is defined by $\mu(a,b)=a*b$ and  $\eta\in\RR$ is defined to be $\eta=1$. The conditions, written diagrammatically, say that starting in the upper left of each diagram below, the result in the lower right is the same regardless of which path you take:

\[
\begin{tikzcd}[ampersand replacement=\&, column sep=30pt]
(a,b,c)\ar[r, |->, "(\mu\otimes\id)"]\ar[d, |->, "(\id\otimes\mu)"']\&
(a*b, c)\ar[d, |->, "\mu"]\\
(a,b*c)\ar[r, |->, "\mu"']\&
\end{tikzcd}
\qquad
\begin{tikzcd}[ampersand replacement=\&, column sep=30pt]
a\ar[r, |->, "(\eta\otimes\id)"]\ar[d, |->, "(\id\otimes\eta)"']\ar[dr, |->, "\id_a" description]\&
(1, a)\ar[d, |->, "\mu"]\\
(a, 1)\ar[r, |->, "\mu"']\&
\end{tikzcd}
\qquad
\begin{tikzcd}[ampersand replacement=\&]
(a,b)\ar[r, |->, "\sigma"]\ar[dr, |->, "\mu"']\&
(b, a)\ar[d, |->, "\mu"]\\\&
\end{tikzcd}
\]

and this is true for $(\rr,*,1)$.

* The same reasoning works for $(\rr,+,0)$, shown below:

\[
\begin{tikzcd}[ampersand replacement=\&, column sep=30pt]
(a,b,c)\ar[r, |->, "(\mu\otimes\id)"]\ar[d, |->, "(\id\otimes\mu)"']\&
(a{+}b, c)\ar[d, |->, "\mu"]\\
(a,b{+}c)\ar[r, |->, "\mu"']\&
\end{tikzcd}
\qquad
\begin{tikzcd}[ampersand replacement=\&, column sep=30pt]
a\ar[r, |->, "(\eta\otimes\id)"]\ar[d, |->, "(\id\otimes\eta)"']\ar[dr, |->, "\id_a" description]\&
(0, a)\ar[d, |->, "\mu"]\\
(a, 0)\ar[r, |->, "\mu"']\&
\end{tikzcd}
\qquad
\begin{tikzcd}[ampersand replacement=\&]
(a,b)\ar[r, |->, "\sigma"]\ar[dr, |->, "\mu"']\&
(b, a)\ar[d, |->, "\mu"]\\\&
\end{tikzcd}
\]

Recall that in $\mat(R)$, the monoidal unit is $0$ and the monoidal product is $+$, because it is a prop. Recall also that in (the usual monoidal structure on) $\smset$, the monoidal unit is $\{1\}$, a set with one element, and the monoidal product is $\times$ (see <ref>).

* Check that the functor $U\colon\mat(R)\to\smset$, defined above, preserves the monoidal unit and the monoidal product.

* Find a function $p\colon R^n\times R^n\to R^n$ such that $p(0,v)=v$ and $p(v,0)=v$ for any $v\in R^n$.

* Use your $p$ to show that if $(M,\mu,\eta)$ is a monoid object in $\mat(R)$ then $(U(M),U(\mu),U(\eta))$ is a monoid object in $\smset$. (This works for any monoidal functor—which we will define in <ref>—not just for $U$ in particular.)

* In <ref>, we said that the triple
$(1,\add{1em},\zero{1em})$ is a commutative monoid object in the prop $\mat(R)$. If $R=\RR$ is the rig of real numbers, this means that we have a monoid structure on the set $\RR$. But in <ref> we gave two such monoid structures. Which one is it?

The functor $U\colon\mat(R)\to\smset$ is given on objects by sending $n$ to the set $R^n$, and on morphisms by matrix-vector multiplication. Here $R^n$ means the set of $n$-tuples or $n$-dimensional vectors in $R$. In particular, $R^0=\{()\}$ consists of a single vector of dimension 0.

* $U$ preserves the monoidal unit because $0$ is the monoidal unit of any prop ($\mat(R)$ is a prop), $\{1\}$ is the monoidal unit of $\smset$, and $R^0$ is canonically isomorphic to $\{1\}$. $U$ also preserves the monoidal product because there is a canonical isomorphism $R^m\times R^n\cong R^{m+n}$.

* A monoid object in $\mat(R)$ is a tuple $(m,\mu,\eta)$ where $m\in\nn$, $\mu\colon m+m\to m$, and $\eta\colon 0\to m$ satisfy the properties $\mu(\eta,x)=x=\mu(x,\eta)$ and $\mu(x,\mu(y,z))=\mu(\mu(x,y),z)$. Note that there is only one morphism $0\to m$ in $\mat(R)$ for any $m$. It is not hard to show that for any $m\in\nn$ there is only one monoid structure. For example, when $m=2$, $\mu$ must be the following matrix

\[
\mu\coloneqq
\left(
\begin{array}{cc}
\end{array}
\right)
\]

Anyway, for any monoid $(m,\mu,\eta)$, the morphism $U(\eta)\colon R^0\to R^m$ is given by $U(\eta)(1)\coloneqq (0,\ldots,0)$, and the morphism $U(\mu)\colon R^m\times R^m\to R^m$ is given by

\[
U(\mu)((a_1,\ldots,a_m),(b_1,\ldots,b_m))\coloneqq (a_1+b_1,\ldots,a_m+b_m).
\]

These give $R^m$ the structure of a monoid.

* The triple $(1,\add{1em},\zero{1em})$ corresponds to the additive monoid structure on $\rr$, e.g. with $(5,3)\mapsto 8$.

* What is the behavior $\beh(\coadd{1.3em})$ of the reversed addition icon $\coadd{1.3em}\colon 1 \to 2$?

* What is the behavior $\beh(\mult{1.3em})$ of the reversed copy icon, $\mult{1.3em}\colon 2\to 1$?

* The behavior $\beh(\coadd{1.3em})$ of the reversed addition icon $\coadd{1.3em}\colon 1 \to 2$ is the relation $\{(x,y,z)\in R^3\mid x=y+z\}$.

* The behavior $\beh(\mult{1.3em})$ of the reversed copy icon, $\mult{1.3em}\colon 2\to 1$ is the relation $\{(x,y,z)\in R^3\mid x=y=z\}$.

In <ref> we went quickly through monoidal products $+$ in the prop $\rel_R$. If $B\ss R^m\times R^n$ and $C\ss R^p\times R^q$ are morphisms in $\rel_R$, write down $B+C$ in set-notation.

If $B\ss R^m\times R^n$ and $C\ss R^p\times R^q$ are morphisms in $\rel_R$, then take $B+C\ss R^{m+p}\times R^{n+q}$ to be the set

\[
B+C\coloneqq\{(w,y,x,z)\in R^{m+p}\times R^{n+q}\mid (w,x)\in B\text{ and }(y,z)\in C\}.
\]

Let $g\colon m \to n$, $h\colon \ell \to n$ be signal flow graphs. Note that
$h\op\colon n \to \ell$ is a signal flow graph, and we can form the
composite $g\cp h\op$:

\[
\begin{tikzpicture}[oriented WD, bb port length=0pt, bb port sep=1pt]
\node[bb={4}{4}, minimum width = 2cm] (X)
{$\begin{array}{c} \longrightarrow \\ g \end{array}$};
\node[bb={4}{4}, right= 1 of X, minimum width = 2cm] (Y)
{$\begin{array}{c} \longleftarrow \\ h\op \end{array}$};
\draw ($(X_in1)-(.2,0)$) to (X_in1);
\draw ($(X_in2)-(.2,0)$) to (X_in2);
\draw ($(X_in4)-(.2,0)$) to (X_in4);
\draw (X_out1) to (Y_in1);
\draw (X_out2) to (Y_in2);
\draw (X_out4) to (Y_in4);
\draw (Y_out1) to ($(Y_out1)+(.2,0)$);
\draw (Y_out2) to ($(Y_out2)+(.2,0)$);
\draw (Y_out4) to ($(Y_out4)+(.2,0)$);
\draw[label]
node at ($.5*(X_out3)+.5*(Y_in3)$) {$\vdots$}
node[left=3pt of X_in3] {$\vdots$}
node[right=3pt of Y_out3] {$\vdots$}
\end{tikzpicture}
\]

Show that the behavior of $g\cp(h\op)$ is equal to

\[
\beh(g\cp(h\op))=\{(x,y)\,\mid\, S(g)(x)=S(h)(y)\}\ss R^m\times R^\ell.
\]

The behavior of $g\colon m\to n$ and $h\op\colon n\to\ell$ are respectively

\begin{align*}
\beh(g)&=\{(x,z)\in R^m\times R^n\,\mid\, S(g)(x)=z\}\\
\beh(h\op)&=\{(z,y)\in R^n\times R^\ell\,\mid\,z=S(h)(y)\}
\end{align*}

and by <ref>, the composite $\beh(g\cp (h\op))=\beh(g)\cp\beh(h\op)$ is:

\[
\{(x,y)\mid\text{ there exists } z\in R^n\text{ such that } S(g)(x)=z\text{ and }z=S(h)(y)\}.
\]

Since $S(g)$ and $S(h)$ are functions, the above immediately reduces to the desired formula:

\[  \beh(g\cp(h\op))=\{(x,y)\,\mid\, S(g)(x)=S(h)(y)\}.\]

Let $g\colon m \to n$, $h\colon m \to p$ be signal flow graphs. Note that
$g\op\colon n \to m$ is a signal flow graph, and we can form the
composite $g\op\cp h$

\[
\begin{tikzpicture}[oriented WD, bb port length=0pt, bb port sep=1pt]
\node[bb={4}{4}, minimum width = 2cm] (X)
{$\begin{array}{c} \longleftarrow \\ g\op \end{array}$};
\node[bb={4}{4}, right= 1 of X, minimum width = 2cm] (Y)
{$\begin{array}{c} \longrightarrow \\ h \end{array}$};
\draw ($(X_in1)-(.2,0)$) to (X_in1);
\draw ($(X_in2)-(.2,0)$) to (X_in2);
\draw ($(X_in4)-(.2,0)$) to (X_in4);
\draw (X_out1) to (Y_in1);
\draw (X_out2) to (Y_in2);
\draw (X_out4) to (Y_in4);
\draw (Y_out1) to ($(Y_out1)+(.5,0)$);
\draw (Y_out2) to ($(Y_out2)+(.5,0)$);
\draw (Y_out4) to ($(Y_out4)+(.5,0)$);
\draw[label]
node at ($.5*(X_out3)+.5*(Y_in3)$) {$\scriptstyle\vdots$}
node[above left=-4pt and 3pt of X_in3] {$\vdots$}
node[above right=-4pt and 3pt of Y_out3] {$\vdots$}
\end{tikzpicture}
\]

Show that the behavior of $g\op\cp h$ is equal to

\[
\{(S(g)(x),S(h)(x))\,\mid\, x \in R^m\}.
\]

The behavior of $g\op\colon n\to m$ and $h\colon m\to p$ are respectively

\begin{align*}
\beh(g\op)&=\{(y,x)\in R^n\times R^m\,\mid\, y=S(g)(x)\}\\
\beh(h)&=\{(x,z)\in R^m\times R^p\,\mid\,S(h)(x)=z\}
\end{align*}

and by <ref>, the composite $\beh((g\op)\cp h)=\beh(g\op)\cp\beh(h)$ is:

\[
\{(y,z)\mid\text{ there exists } x\in R^m\text{ such that } y=S(g)(x)\text{ and }S(h)(x)=z\}.
\]

This immediately reduces to the desired formula:

\[
\beh((g\op)\cp h)=\{(S(g)(x),S(h)(x))\,\mid\, x \in R^m\}.
\]

Here is an exercise for those that know linear algebra. Let $R$ be a field, and $g\colon
m \to n$ a signal flow graph and let $S(g)\in\mat(R)$ be the associated $(m\times n)$-matrix (see <ref>).

* Show that the composite of $g$ with $0$-reverses, shown here

\[
\begin{tikzpicture}[oriented WD, bb port length=0pt, bb port sep=1pt]
\node[bb={4}{4}, minimum width = 2cm] (X)
{$\begin{array}{c} \longrightarrow \\ g \end{array}$};
\draw ($(X_in1)-(.5,0)$) to (X_in1);
\draw ($(X_in2)-(.5,0)$) to (X_in2);
\draw ($(X_in4)-(.5,0)$) to (X_in4);
\draw (X_out1) to ($(X_out1)+(.5,0)$);
\draw (X_out2) to ($(X_out2)+(.5,0)$);
\draw (X_out4) to ($(X_out4)+(.5,0)$);
\draw[label]
node[above left=-4pt and 3pt of X_in3] {$\vdots$}
node[above right=-4pt and 3pt of X_out3] {$\vdots$}
node[wdot] at ($(X_out1)+(.5,0)$) {}
node[wdot] at ($(X_out2)+(.5,0)$) {}
node[wdot] at ($(X_out4)+(.5,0)$) {}
\end{tikzpicture}
\]

is equal to the kernel of the matrix $S(g)$.

* Show that the composite of discard-reverses with $g$, shown here

\[
\begin{tikzpicture}[oriented WD, bb port length=0pt, bb port sep=1pt]
\node[bb={4}{4}, minimum width = 2cm] (X)
{$\begin{array}{c} \longrightarrow \\ g \end{array}$};
\draw ($(X_in1)-(.5,0)$) to (X_in1);
\draw ($(X_in2)-(.5,0)$) to (X_in2);
\draw ($(X_in4)-(.5,0)$) to (X_in4);
\draw (X_out1) to ($(X_out1)+(.2,0)$);
\draw (X_out2) to ($(X_out2)+(.2,0)$);
\draw (X_out4) to ($(X_out4)+(.2,0)$);
\draw[label]
node[above left=-4pt and 3pt of X_in3] {$\vdots$}
node[above left=-4pt and 3pt of X_out3] {$\vdots$}
node[bdot] at ($(X_in1)-(.5,0)$) {}
node[bdot] at ($(X_in2)-(.5,0)$) {}
node[bdot] at ($(X_in4)-(.5,0)$) {}
\end{tikzpicture}
\]

is equal to the image of the matrix $S(g)$.

* Show that for any signal flow graph $g$, the subset
$\beh(g)\subseteq R^m \times R^n$ is a linear subspace. That is, if $b_1,b_2\in \beh(g)$ then so are $b_1+b_2$ and $r*b_1$, for any $r\in R$.

* The behavior of the 0-reverse $\cozero{1.5em}$ is the subset $\{y\in R\mid y=0\}$, and its $n$-fold tensor is similarly $\{y\in R^n\mid y=0\}$. Composing this relation with $S(g)\ss R^m\times R^n$ gives $\{x\in R^m\mid S(g)=0\}$, which is the kernel of $S(g)$.

* The behavior of the discard-inverse $\unit{1.5em}$ is the subset $\{x\in R\}$, i.e. the largest subset of $R$, and similarly its $m$-fold tensor is $R^n\ss R^n$. Composing this relation with $S(g)\ss R^m\times R^n$ gives $\{y\in R^n\mid \text{ there exists }x\in R^m\text{ such that }S(g)(x)=y\}$, which is exactly the image of $S(g)$.

* For any $g\colon m\to n$, we first claim that the behavior $\beh(g)=\{(x,y)\mid S(g)(x)=y\}$ is linear, i.e. it is closed under addition and scalar multiplication. Indeed, $S(g)$ is multiplication by a matrix, so if $S(g)(x)=y$ then $S(g)(rx)=ry$ and $S(g)(x_1+x_2)=S(g)(x_1)+S(g)(x_2)$. Thus we conclude that $(x,y)\in\beh(g)$ implies $(rx,ry)\in\beh(g)$, so it's closed under scalar multiplication, and $(x_1,y_1),(x_2,y_2)\in\beh(g)$ implies $(x_1+x_2,y_1+y_2)\in\beh(g)$ so it's closed under addition. Similarly, the behavior $\beh(g\op)$ is also linear; the proof is similar.

Finally, we need to show that the composite of any two linear relations is linear. Suppose that $B\ss R^m\times R^n$ and $C\ss R^n\times R^p$ are linear. Take $(x_1,z_1),(x_2,z_2)\in B\cp C$ and take $r\in R$. By definition, there exist $y_1,y_2\in R^n$ such that $(x_1,y_1),(x_2,y_2)\in B$ and $(y_1,z_1),(y_2,z_2)\in C$. Since $B$ and $C$ are linear, $(rx_1,ry_1)\in B$ and $(ry_1,rz_1)\in C$, and also $(x_1+x_2,y_1+y_2)\in B$ and $(y_1+y_2,z_1+z_2)\in C$. Hence $(rx_1,rz_1)\in (B\cp C)$ and $(x_1+x_2,z_1+z_2)\in (B\cp C)$, as desired.

One might want to show that linear relations on $R$ form a prop, $\Cat{LinRel}_R$. That is, one might want to show that there is a sub-prop of the prop $\rel_R$ from <ref>, where the morphisms $m\to n$ are the subsets $B\ss R^m\times R^n$ such that $B$ is linear. In other words, where for any $(x,y)\in B$ and $r\in R$, the element $(r*x,r*y)\in R^m\times R^n$ is in $B$, and for any $(x',y')\in B$, the element $(x+x',y+y')$ is in $B$.

This is certainly doable, but for this exercise, we only ask that you prove that the composite of two linear relations is linear.

Suppose that $B\ss R^m\times R^n$ and $C\ss R^n\times R^p$ are linear. Their composite is the relation $(B\cp C)\ss R^m\times R^p$ consisting of all $(x,z)$ for which there exists $y\in R^n$ with $(x,y)\in B$ and $(y,z)\in C$. We want to show that the set $(B\cp C)$ is linear, i.e. closed under scalar multiplication and addition.

For scalar multiplication, take an $(x,z)\in (B\cp C)$ and any $r\in R$. Since $B$ is linear, we have $(r*x,r*y)\in B$ and since $C$ is linear we have $(r*y,r*z)\in C$, so then $(r*x,r*z)\in (B\cp C)$. For addition, if we also have $(x',z')\in(B\cp C)$ then there is some $y'\in R^n$ with $(x',y')\in B$ and $(y',z')\in C$, so since $B$ and $C$ are linear we have $(x+x',y+y')\in B$ and $(y+y',z+z')\in C$, hence $(x+x',z+z')\in (B\cp C)$.

§ SOLUTIONS FOR <REF>.

Consider the set $A=\{a,b\}$. Find a preorder relation $\leq$ on $A$ such that

* $(A,\leq)$ has no initial object.

* $(A,\leq)$ has exactly one initial object.

* $(A,\leq)$ has two initial objects.

Let $A=\{a,b\}$, and consider the preorders shown here: $\LMO{a}\quad\LMO{b}$ ,   $\LMO{a}\to\LMO{b}$ ,   $\LMO{a}\leftrightarrows\LMO{b}$ .

* The left-most (the discrete preorder on $A$) has no initial object, because $a\not\leq b$ and $b\not\leq a$.preorder!discrete

* The middle one has one initial object, namely $a$.

* The right-most (the co-discrete preorder on $A$) has two initial objects.preorder!codiscrete

For each of the graphs below, consider the free category on that graph, and say whether it has an initial object.

* $\LMO{a}$

* $\LMO{a}\to\LMO{b}\to\LMO{c}$

* $\LMO{a}\qquad\LMO{b}$

* $\begin{tikzcd}\LMO{a}\ar[loop right]\end{tikzcd}$

Recall that the objects of a free category on a graph are the vertices of the
graph, and the morphisms are paths. Thus the free category on a graph $G$ has an
initial object if there exists a vertex $v$ that has a unique path to every
object. In 1. and 2., the vertex $a$ has this property, so the free categories
on graphs 1. and 2. have initial objects. In graph 3., neither $a$ nor $b$
have a path to each other, and so there is no initial object. In graph 4., the
vertex $a$ has many paths to itself, and hence its free category does not have
an initial object either.

Recall the notion of rig from <ref>. A rig homomorphism from $(R,0_R,+_R,1_R,*_R)$ to $(S,0_S,+_S,,1_S, *_S)$ is a function $f\colon R\to S$ such that $f(0_R)=0_S$, $f(r_1+_Rr_2)=f(r_1)+_Sf(r_2)$, etc.

* We said “etc.” Guess the remaining conditions for $f$ to be a rig homomorphism.

* Let $\Cat{Rig}$ denote the category whose objects are rigs and whose morphisms are rig homomorphisms. We claim $\Cat{Rig}$ has an initial object. What is it?

* The remaining conditions are that $f(1_R)=1_S$, and that $f(r_1\ast_R r_2)
= f(r_1) \ast_S f(r_2)$.

* The initial object in the category $\Cat{Rig}$ is the natural numbers rig
$(\nn,0,+,1,\ast)$. The fact that is initial means that for any other rig
$R=(R,0_R,+_R,1_R,\ast_R)$, there is a unique rig homomorphism $f\colon \nn \to

What is this homomorphism? Well, to be a rig homomorphism, $f$ must send
$0$ to $0_R$, $1$ to $1_R$. Furthermore, we must also have $f(m + n) =
f(m) +_Rf(n)$, and hence

\[
f(m) = f(\underbrace{1+1+\dots+1}_{m \text{ summands}}) =
\underbrace{f(1)+f(1)+\dots+f(1)}_{m \text{ summands}} = \underbrace{1_R+1_R+
\dots+1_R}_{m \text{ summands}}.
\]

So if there is a rig homomorphism $f\colon\nn\to R$, it must be given by the above formula. But does this formula work correctly for multiplication?

It remains to check $f(m \ast n) = f(m) \ast_R f(n)$, and this will follow from
distributivity. Noting that $f(m\ast n)$ is equal to the sum of $mn$ copies of
$1_R$, we have

\begin{align*}
f(m) \ast_R f(n) &= (\underbrace{1_R+\dots+1_R}_{m \text{ summands}}) \ast_R
(\underbrace{1_R+\dots+1_R}_{n \text{ summands}}) \\
&= \underbrace{1_R \ast (\underbrace{1_R+\dots+1_R}_{n \text{ summands}}) + \dots
+1_R\ast (\underbrace{1_R+\dots+1_R}_{n \text{ summands}})}_{m \text{ summands}} \\
&= \underbrace{1_R+\dots+1_R}_{mn \text{ summands}} = f(m\ast n).
\end{align*}

Thus $(\nn,0,+,1,\ast)$ is the initial object in $\Cat{Rig}$.

Explain the statement “the hallmark of universality is the existence of a
unique map to any other comparable object,” in the context of
<ref>. In particular, what is universal? What is the
“comparable object”?

In <ref>, it is the initial object $\varnothing\in\cat{C}$ that is
universal. In this case, all objects $c\in\cat{C}$ are `comparable objects'.
So the universal property of the initial object is that to any object $c\in\cat{C}$,
there is a unique map $\varnothing\to c$ coming from the initial object.

Let $\cat{C}$ be a category, and suppose that $c_1$ and $c_2$ are initial objects. Find an isomorphism between them, using the universal property from <ref>.

If $c_1$ is initial then by the universal property, for any $c$ there is a unique morphism $c_1\to c$; in particular, there is a unique morphism $c_1\to c_2$, call it $f$. Similarly, if $c_2$ is initial then there is a unique morphism $c_2\to c_1$, call it $g$. But how do we know that $f$ and $g$ are mutually inverse? Well since $c_1$ is initial there is a unique morphism $c_1\to c_1$. But we can think of two: $\id_{c_1}$ and $f\cp g$. Thus they must be equal. Similarly for $c_2$, so we have $f\cp g=\id_{c_1}$ and $g\cp f=\id_{c_2}$, which is the definition of $f$ and $g$ being mutually inverse.

Explain why coproducts in a preorder are the same as joins.

Let $(P,\le)$ be a preorder, and $p,q \in P$. Recall that a preorder is a
category with at most one morphism, denoted $\le$, between any two objects.
Also recall that all diagrams in a preorder commute, since this means any two
morphisms with the same domain and codomain are equal.

Translating <ref> to this case, a coproduct $p+q$ is $P$ is an
element of $P$ such that $p \le p+q$ and $q\le p+q$, and such that for all elements $x
\in P$ with maps $p \le x$ and $q \le x$, we have $p+q \le x$. But this says
exactly that $p+q$ is a join: it is a least element above both $p$ and
$q$. Thus coproducts in preorders are exactly the same as joins.

Suppose $T=\{a,b,c,\ldots,z\}$ is the set of letters in the alphabet, and let $A$ and $B$ be the sets from <ref>. Consider the function $f\colon A\to T$ sending each element of $A$ to the first letter of its label, e.g. $f(\mathrm{apple})=a$. Let $g\colon B\to T$ be the function sending each element of $B$ to the last letter of its label, e.g. $g(\mathrm{apple})=e$. Write down the function $\copair{f,g}(x)$ for all elements of $A\sqcup B$.

The function $\copair{f,g}$ is defined by

\begin{align*}
\copair{f,g}\colon A \sqcup B &\longrightarrow T \\
\mathrm{apple1} &\longmapsto a \\
\mathrm{banana1} &\longmapsto b \\
\mathrm{pear1} &\longmapsto p \\
\mathrm{cherry1} &\longmapsto c \\
\mathrm{orange1} &\longmapsto o \\
\mathrm{apple2} &\longmapsto e \\
\mathrm{tomato2} &\longmapsto o \\
\mathrm{mango2} &\longmapsto o.
\end{align*}

Let $f \colon A \to C$, $g \colon B \to C$, and $h\colon C \to D$ be morphisms
in a category $\cat{C}$ with coproducts. Show that

* $\iota_A \cp \copair{f,g} = f$.

* $\iota_B \cp \copair{f,g} = g$.

* $\copair{f,g}\cp h = \copair{f \cp h,g\cp h}$.

* $\copair{\iota_A,\iota_B} = \id_{A+B}$.

* The equation $\iota_A \cp \copair{f,g} = f$ is the commutativity of the
left hand triangle in the commutative diagram
(<ref>) defining $\copair{f,g}$.

* The equation $\iota_B \cp \copair{f,g} = g$ is the commutativity of the
right hand triangle in the commutative diagram
(<ref>) defining $\copair{f,g}$.

* The equation $\copair{f,g}\cp h = \copair{f \cp h,g\cp h}$ follows from
the universal property of the coproduct. Indeed, the diagram

\[
\begin{tikzcd}[ampersand replacement=\&, column sep=large, cramped]
A \ar[r,"\iota_A"] \ar[dr,"f"' near end]  \ar[ddr, "f\cp h"']
\& A+B \ar[d, "\copair{f,g}" description]
\& B \ar[l,"\iota_B"'] \ar[dl, "g" near end] \ar[ddl, "g\cp h"] \\[10pt]
\& C \ar[d, "h" description] \\[10pt]
\& D
\end{tikzcd}
\]

commutes, and the universal property says there is a unique map $\copair{f\cp
h, g \cp h}\colon A+B \to D$ for which this occurs. Hence we must have $[f,g]
\cp h = \copair{f \cp h, g \cp h}$.

* Similarly, to show $\copair{\iota_A,\iota_B} = \id_{A+B}$, observe that
the diagram

\[
\begin{tikzcd}[ampersand replacement=\&, cramped]
A \ar[r,"\iota_A"] \ar[dr,"\iota_A"'] \& A+B \ar[d,equal, "\id_{A+B}" description] \& B
\ar[l,"\iota_B"'] \ar[dl, "\iota_B"] \\[15pt]
\& A+B
\end{tikzcd}
\]

trivially commutes. Hence by the uniqueness in
(<ref>), $\copair{\iota_{A}, \iota_{B}}=\id_{A+B}$.

Suppose a category $\cat C$ has coproducts, denoted $+$, and an initial object,
denoted $\varnothing$. Then we can show $(\cat C,+,\varnothing)$ is a symmetric
monoidal category (recall <ref>). In this exercise we develop
the data.

* Show that $+$ extends to a functor $\cat C \times \cat C \to \cat C$. In particular, how does it act on morphisms in $\cat{C}\times\cat{C}$?

* Using the universal properties of the initial object and coproduct, show
that there are isomorphisms $A+\varnothing \to A$ and $\varnothing +A \to A$.

* Using the universal property of the coproduct, write down morphisms

* $(A+B)+C \to A+(B+C)$.

* $A+B \to B+A$.

If you like, check that these are isomorphisms.

It can then be checked that this data obeys the axioms of a symmetric monoidal
category, but we'll end the exercise here.

This exercise is about showing that coproducts and an initial object give a
symmetric monoidal category. Since all we have are coproducts and an initial
object, and since these are defined by their universal properties, the solution
is to use these universal properties over and over, to prove that all the data
of <ref> can be constructed.

* To define a functor $+\colon \cat{C} \times \cat{C} \to \cat{C}$ we must
define its action on objects and morphisms. In both cases, we just take the
coproduct. If $(A,B)$ is an object of $\cat{C} \times \cat{C}$, its image $A+B$
is, as usual, the coproduct of the two objects of $\cat{C}$. If $(f,g) \colon
(A,B)\to (C,D)$ is a morphism, then we can form a morphism $f+g = \copair{f \cp
\iota_C, g \cp \iota_D}\colon A+B \to C+D$, where $\iota_C \colon C \to C+D$ and
$\iota_D\colon D \to C+D$ are the canonical morphisms given by the definition of
the coproduct $A+B$.

Note that this construction sends identity morphisms to identity morphisms,
since by <ref> 4 we have

\[
\id_A + \id_B = \copair{\id_A\cp \iota_{A}, \id_B \cp \iota_{B}} =\copair{\iota_{A}, \iota_{B}}=\id_{A+B}.
\]

To show that $+$ is a functor, we need to also show it preserves composition.
Suppose we also have a morphism $(h,k)\colon (C,D) \to (E,F)$ in $\cat{C} \times
\cat{C}$. We need to show that $(f+g) \cp (h+k) = (f \cp h) + (g \cp k)$. This
is a slightly more complicated version of the argument in
<ref> 3. It follows from the fact the diagram below

\[
\begin{tikzcd}[ampersand replacement=\&]
A \ar[rr,"\iota_A"] \ar[dr,"f"'] \& \& A+B \ar[d, "f+g"] \&\& B
\ar[ll,"\iota_B"'] \ar[dl, "g"] \\[5pt]
\& C \ar[r, "\iota_C"] \ar[dr,"h\cp \iota_E"'] \& C+D \ar[d,"h+k" near
start] \& D
\ar[l,"\iota_D"'] \ar[dl, "k \cp \iota_F"] \\[5pt]
\&\& E+F
\end{tikzcd}
\]

Indeed, we again use the uniqueness of the copairing in
(<ref>), this time to show that $(f \cp h) + (g \cp
k)=\copair{f\cp h \cp \iota_E, g\cp k \cp \iota_F} = (f+g) \cp (h+k)$, as

* Recall the universal property of the initial object gives a unique map
$!_A\colon \varnothing \to A$. Then the copairing $\copair{\id_A,!_A}$ is a map
$A+\varnothing \to A$. Moreover, it is an isomorphism with inverse $\iota_A
\colon A \to A +\varnothing$. Indeed, using the properties in
<ref> and the universal property of the initial object,
we have $\iota_A \cp \copair{\id_A,!_A} = \id_A$, and

\[
\copair{\id_A,!_A} \cp \iota_A = \copair{\id_A \cp \iota_A, !_A \cp \iota_A} =
\copair{\iota_A,!_{A+\varnothing}} = \copair{\iota_A,\iota_\varnothing} =
\id_{A+\varnothing}.
\]

An analogous argument shows $\copair{!_A,\id_A} \colon \varnothing +A \to A$ is
an isomorphism.

* We'll just write down the maps and their inverses; we leave it to you, if
you like, to check that they indeed are inverses.

* The map $\copair{\id_A +\iota_B,\iota_C} = \copair{\copair{\iota_A,\iota_B \cp
\iota_{B+C}},\iota_C\cp\iota_{B+C}} \colon (A+B)+C \to A+(B+C)$ is an isomorphism,
with inverse $\copair{\iota_A, \iota_B+\id_C} \colon A+(B+C) \to (A+B)+C$.

* The map $\copair{\iota_A,\iota_B}\colon A+B \to B+A$ is an isomorphism.
Note our notation here is slightly confusing: there are two maps named
$\iota_A$, (i) $\iota_A \colon A \to A+B$, and (ii) $\iota_A\colon A \to B+A$, and
similarly for $\iota_B$. In the above we mean the map (ii). It has inverse
$\copair{\iota_A,\iota_B}\colon B+A \to A+B$, where in this case we mean the
map (i).

For any set $S$, we have the discrete category $\Cat{Disc}_S$, with $S$ as objects and only identity morphisms.

* Show that all pushouts exist in $\Cat{Disc}_S$, for any set $S$.

* For what sets $S$ does $\Cat{Disc}_S$ have an initial object?

* Suppose given an arbitrary diagram of the form $B\from A\to C$ in $\Cat{Disc}_S$; we need to show that it has a pushout. The only morphisms in $\Cat{Disc}_S$ are identities, so in particular $A=B=C$, and the square consisting of all identities is its pushout.

* Suppose $\Cat{Disc}_S$ has an initial object $s$. Then $S$ cannot be empty! But it also cannot have more than one object, because if $s'$ is another object then there is a morphism $s\to s'$, but the only morphisms in $S$ are identities so $s=s'$. Hence the set $S$ must consist of exactly one element.

What is the pushout of the functions $f\colon \ord{4} \to \ord{5}$ and $g\colon \ord{4} \to
\ord{3}$ pictured below?

\[
\begin{tikzpicture}[x=.6cm,y=.4cm, baseline=(3a)]
\node at (2,-1.5) {$f\colon \ord{4} \to \ord{5}$};
\node[contact] at (0,3) (1) {};
\node[contact] at (0,2) (2) {};
\node[contact] at (0,1) (3) {};
\node[contact] at (0,0) (4) {};
\node[contact] at (4,3.5) (1a) {};
\node[contact] at (4,2.5) (2a) {};
\node[contact] at (4,1.5) (3a) {};
\node[contact] at (4,0.5) (4a) {};
\node[contact] at (4,-0.5) (5a) {};
\node[draw, rounded corners, inner xsep=7pt, inner ysep=4pt, fit=(1) (4)] (B) {};
\node[draw, rounded corners, inner xsep=7pt, inner ysep=4pt, fit=(1a) (5a)] (B) {};
\begin{scope}[function]
\draw (1) to (1a);
\draw (2) to (1a);
\draw (3) to (3a);
\draw (4) to (5a);
\end{scope}
\end{tikzpicture}
\hspace{.25\textwidth}
\begin{tikzpicture}[x=.6cm,y=.4cm, baseline=(2a)]
\node at (2,-1.35) {$g\colon \ord{4} \to \ord{3}$};
\node[contact] at (0,3) (1) {};
\node[contact] at (0,2) (2) {};
\node[contact] at (0,1) (3) {};
\node[contact] at (0,0) (4) {};
\node[contact] at (4,2.5) (1a) {};
\node[contact] at (4,1.5) (2a) {};
\node[contact] at (4,0.5) (3a) {};
\node[draw, rounded corners, inner xsep=7pt, inner ysep=4pt, fit=(1) (4)] (B) {};
\node[draw, rounded corners, inner xsep=7pt, inner ysep=4pt, fit=(1a) (3a)] (B) {};
\begin{scope}[function]
\draw (1) to (1a);
\draw (2) to (2a);
\draw (3) to (3a);
\draw (4) to (3a);
\end{scope}
\end{tikzpicture}
\]

Check your answer using the abstract description from <ref>.

The pushout is the set $\ord{4}$, as depicted in the top right in the diagram
below, equipped also with the depicted functions:

\begin{equation}\label{eqn.pushout_4534}
\begin{tikzpicture}[x=.5cm,y=.5cm, node distance=.5cm]
\node[contact] at (0,0) (1) {};
\node[contact, below left of=1] (2) {};
\node[contact, below left of=2]  (3) {};
\node[contact, below left of=3] (4) {};
\node[draw, rotate fit=45, rounded corners, inner xsep=7pt, inner
ysep=7pt, fit=(1) (4)] (I) {};
\node at (2,-3.2) {$f$};
\node[contact,] at (4,0) (1a) {};
\node[contact, below right of =1a] (2a) {};
\node[contact, below right of =2a] (3a) {};
\node[contact, below right of =3a] (4a) {};
\node[contact, below right of =4a] (5a) {};
\node[draw, rotate fit=45, rounded corners, inner xsep=7pt, inner
ysep=7pt, fit=(1a) (5a)] (A) {};
\node at (-2.8,2) {$g$};
\node[contact] at (0,4) (1b) {};
\node[contact, above left of=1b] (2b) {};
\node[contact, above left of=2b] (3b) {};
\node[draw, rotate fit=45, rounded corners, inner xsep=7pt, inner
ysep=7pt, fit=(1b) (3b)] (B) {};
\node[contact] at (4,4) (1p) {};
\node[contact, above right of=1p] (2p) {};
\node[contact, above right of=2p]  (3p) {};
\node[contact, above right of=3p] (4p) {};
\node[draw, rotate fit=45, rounded corners, inner xsep=7pt, inner
ysep=7pt, fit=(1p) (4p)] (P) {};
\node at (8,5) {\small pushout};
\begin{scope}[function]
\draw (1) to (1a);
\draw (2) to (1a);
\draw (3) to (3a);
\draw (4) to (5a);
\end{scope}
\begin{scope}[function]
\draw (1) to (1b);
\draw (2) to (2b);
\draw (3) to (3b);
\draw (4) to (3b);
\end{scope}
\begin{scope}[function]
\draw (1a) to (1p);
\draw (2a) to (2p);
\draw (3a) to (3p);
\draw (4a) to (4p);
\draw (5a) to (3p);
\end{scope}
\begin{scope}[function]
\draw (1b) to (1p);
\draw (2b) to (1p);
\draw (3b) to (3p);
\end{scope}
\end{tikzpicture}
\end{equation}