\documentclass{article}
\input{packages}
\input{def}

\homework{Multicategories}

\begin{document}
\maketitle

\begin{exercise}
Prove that there is a multicategory~$\cat{Mon}$ whose objects are monoids and whose morphisms are the multilinear homomorphisms with composition and identity are inherited from $\cat{Set}$.
This amounts to defining what nullary multilinear homomorphisms are, and proving that multilinear homomorphisms are closed under composition and identity.
\end{exercise}

\begin{proof}
An $n$-ary multilinear homomorphism is an $n$-ary function such that, for each input, fixing all other inputs always produces a monoid homomorphism.
Thus, the $n = 1$ case is simply a monoid homomorphism.
For the $n > 1$ case, this means fixing any one input to any value produces an $(n-1)$-ary multilinear homomorphism.
Since the nullary case has no inputs, this means that all nullary functions are nullary multilinear homomorphisms.
Composing with a unary monoid homomorphism produces a nullary function, which is a nullary multilinear homomorphism.
Composing with a multi-input multilinear homomorphism effectively fixes an input of the function, which by the definition of a multilinear homomorphism still results in a mulitlinear homomoprhism.

As for composing non-nullary multilinear homomorphisms, I show this produces a multilinear homomorphism for arbitrary $f : [\alg{M}_1, \alg{M}_2] \mto \alg{N}_1$ and $g : [\alg{N}_1, \alg{N}_2] \mto \alg{O}$ and the remaining non-nullary cases follow from similar arguments.
Suppose we have $m_1, m_1' : M_1$, $m_2, m_2' : M_2$, and $n_2, n_2' : N_2$. We need to prove the following:
\begin{description}
\item[$g(f(m_1, m_2), e) = e$:] Follows immediately from multilinearity of $g$
\item[$g(f(m_1, m_2), n_2 * n_2') = g(f(m_1, m_2), n_2) * g(f(m_1, m_2), n_2')$:] Follows immediately from multilinearity of $g$
\item[$g(f(m_1, e), n_2) = e$:] The left is equal to $g(e, n_2)$ by multilinearity of $f$, which equals the right by multilinearity of $g$
\item[$g(f(m_1, m_2 * m_2'), n_2) = g(f(m_1, m_2), n_2) * g(f(m_1, m_2'), n_2')$:] The left is equal to $g(f(m_1, m_2) * f(m_1, m_2'), n_2)$ by multilinearity of $f$, which equals the right by multilinearity of $g$
\item[$g(f(e, m_2), n_2) = e$:] The left is equal to $g(e, n_2)$ by multilinearity of $f$, which equals the right by multilinearity of $g$
\item[$g(f(m_1 * m_1', m_2), n_2) = g(f(m_1, m_2), n_2) * g(f(m_1', m_2), n_2')$:] The left is equal to $g(f(m_1, m_2) * f(m_1', m_2), n_2)$ by multilinearity of $f$, which equals the right by multilinearity of $g$
\end{description}

The identity function is clearly a monoid homomorphism: $\id(e) = e$ and $\id(m_1 * m_2) = m_1 * m_2 = \id(m_1) * \id(m_2)$.
\end{proof}

\begin{exercise}
Prove that there is a bijection between the set of categories and the set of pairs~$\langle O, M \rangle$ where $O$~is an element of~$\TYPE{1}$ and $M$~is a functor of multicategories from~$\cat{Path}(O)$ to~$\cat{Set}$.
\end{exercise}

\begin{proof}
Suppose we have a category $\cat{C}$.
Let $O$ be the set $O_\cat{C}$.
Then objects of $\cat{Pair}(O_\cat{C})$ are pairs of objects of $\cat{C}$.
Let the functor $M$ map each pair $\langle \ob{A}, \ob{B} \rangle$ to $M_\cat{C}(A,B)$, the set of $\cat{C}$-morphisms from $\ob{A}$ to $\ob{B}$.
Now, suppose $\langle \ob{A}, \ob{B} \rangle$ is the codomain of a morphism of $\cat{Pair}(O_\cat{C})$.
Then $M$ needs to map this morphism to a function from morphism paths in $\cat{C}$ from $\ob{A}$ to $\ob{B}$ to morphisms in $\cat{C}$ from $\ob{A}$ to $\ob{B}$.
Thus, $M$ maps each morphism in $\cat{Path}(O_\cat{C})$ to the composition operation on the appropriate paths.
Distributivity of $M$ is given by associativity of unbiased composition in $\cat{C}$, and identity preservation of $M$ is given by identity of unbiased composition in $\cat{C}$.

Suppose we have a set $O$ and a functor of multicategories $M$ from $\cat{Path}(O)$ to $\cat{Set}$.
Let $O_\cat{C}$ be the set $O$.
Let $M_\cat{C}(A, B)$ be $M(\langle A, B \rangle)$.
For composition, each path has the form $A_1 \mto \dots \mto A_n$, so compose a path by applying the function that $M$ maps the unique morphism from $[\langle A_1, A_2 \rangle, \dots, \langle A_{n-1}, A_n \rangle]$ to $\langle A_1, A_n \rangle$ to.
Associativity of unbiased composition is given by distributivity of $M$ and thinness of $\cat{Path}(O)$.
For example, suppose $\mo{c}_{A,B,C}$ is the unique morphism in $\cat{Path}(O)$ from $[\langle A, B \rangle, \langle B, C \rangle]$ to $\langle A, C \rangle$.
Then $\mo{c}_{A,B,C}$ composed appropriately with $\mo{c}_{A,C,D}$ equals the unique morphism from $[\langle A, B \rangle, \langle B, C \rangle, \langle C, D \rangle]$ to $\langle A, D \rangle$, and so does $\mo{c}_{B,C,D}$ composed appropriately with $\mo{c}_{A,B,D}$.
Because of this, distributivity of the functor $M$ implies binary composition is associative.
Lastly, unbiased identity is given by the fact that $M$ preserves identities.

These two processes are clearly inverses of each other.
\end{proof}

\begin{exercise}
Give an example of an internal monoid of~$\cat{Mon}$ whose underlying set is~$\N$.
\end{exercise}

\begin{proof}
Multiplication of natural numbers is a multilinear homomorphism from $[\N_{+,0}, \N_{+,0}]$ to $\N_{+,0}$ that is associative and has $1 : \nil \mto \N_{+,0}$ as its identity. All proofs are basic arithmetic.
\end{proof}

\begin{exercise}
Define a multicategory~$\cat{M}$ with the property that, for any multicategory $\cat{C}$, there is a bijection between the set of functors from~$\cat{M}$ to~$\cat{C}$ and the set of internal monoids of~$\cat{C}$.
\end{exercise}

\begin{proof}
Define $\cat{M}$ to be the multicategory $\cat{Path}(\mathbb{1})$ with exactly one object and exactly one morphism for each arity.
A functor from $\cat{M}$ to $\cat{C}$ picks out a single object $\ob{C}$ of $\cat{C}$ and for each arity picks out a $\ob{C}$-endomorphism of that arity.
Due to the thinness of $\cat{M}$, functoriality implies that this collection of morphisms satisfies the associativity and identity requirements of unbiased internal monoids, which are in 1-to-1 correspondence with biased internal monoids (via the same proof as for non-internal monoids). For example, if $\mo{m}_n$ is the unique $n$-ary morphism in $\cat{M}$, and $\mo{o}$ is the binary morphism of $\cat{M}$ that the functor maps $\mo{m}_2$, then distributivity implies $\mo{o}$ is associative since the two ways to compose $\mo{m}_2$ with itself to get a ternary morphism both equal the same morphism of $\cat{M}$, namely $\mo{m}_3$, and so must both equal whatever the functor maps $\mo{m}_3$ to.
\end{proof}

\begin{exercise}
Prove that the category~$\cat{CommMon}$ can be enriched in the multicategory~$\cat{CommMon}$. That is, show that there is a functor of multicategories from~$\cat{Path}(O_\cat{CommMon})$ to~$\cat{CommMon}$ that when composed with the underlying functor of multicategories from~$\cat{CommMon}$ to~$\cat{Set}$ produces the functor of multicategories from~$\cat{Path}(O_\cat{CommMon})$ to~$\cat{Set}$ defining the category~$\cat{CommMon}$.
\end{exercise}

\begin{proof}
This amounts to imposing a commutative monoidal structure on the set of monoid homomorphisms between any two commutative monoids and proving that composition and identity are multilinear; everything else follows from the fact that $\cat{CommMon}$ is a category.
So, given monoid homomorphisms $f$ and $g$, define $f * g$ to be $\lambda x.\; f(x) * g(x)$.
$f*g$ is a monoid homomorphism because $(f*g)(e) = f(e)*g(e) = e*e = e$ and $(f*g)(x*y) = f(x*y)*g(x*y) = f(x)*f(y)*g(x)*g(y) = f(x)*g(x)*f(y)*g(y) = (f*g)(x)*(f*g)(y)$.
This operation is commutative and associative because $*$ in the codomain is commutative and associative.
Also, define $e$ to be $\lambda x.\; e$, which is trivially a monoid homomorphism.
It is the identity of $*$ because $e$ is the identity of $*$ in the codomain.

Next, we need to show that composition is multilinear.
$e \cocomp f_2 = e$ because $e$ always returns the identity element and $f_2$, being a monoid homomorphism, maps that to the identity.
$(f_1*g_1) \cocomp f_2 = \lambda x.\; f_2((f_1*g_1)(x)) = \lambda x.\; f_2(f_1(x)*g_1(x)) = \lambda x.\; f_2(f_1(x))*f_2(g_1(x)) = (f_1 \cocomp f_2)*(g_1 \cocomp f_2)$.
$f_1 \cocomp e = e$ by definition of $e$.
$f_1 \cocomp (f_2*g_2) = \lambda x.\; (f_2*g_2)(f_1(x)) = \lambda x.\; f_2(f_1(x)) * g_2(f_1(x)) = (f_1 \cocomp f_2)*(f_1 \cocomp g_2)$.

Lastly, the identity is multilinear because any nullary function is multilinear.
\end{proof}

\end{document}