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

\homework{Factorizations}

\begin{document}
\maketitle

\begin{exercise}
Prove that the category of ranked preorder semigroups has a particular $(\alg{E}, \alg{M})$-factorization structure.
A ranked preordered semigroup is a preordered semigroup $\langle M, \leq, * \rangle$ along with a function $r : M \mto \R$ such that $r(m_1 * m_2) = r(m_1) + r(m_2)$, and $m \leq m'$ implies $r(m) \leq r(m')$.
A morphism of ranked preorder semigroups $\mo{f} : \alg{M}_1 \mto \alg{M}_2$ is a morphism of preorded semigroups with the additional property that $r_2(f(m_1)) = r_1(m_1)$.

This category has an underlying functor to $\cat{Prost}$, which we use to define the particular $\alg{E}$ and $\alg{M}$ we want a factorization structure for.
A morphism belongs to $\alg{E}$ iff its underlying morphism is an epimorphism in $\cat{Prost$}.
A source belongs to $\alg{M}$ iff its underlying source is an initial monosource in $\cat{Prost}$.

Show how to construct the category of ranked preorder semigroups from $\cat{Prost}$ using the techniques from class.
I am happy if you give the correct construction, even if you do not do the detailed work of proving the result is isomorphic to the category of ranked preorder semigroups.
\end{exercise}

\begin{proof}
Let $F(\alg{X}) = \alg{X} \with \alg{X}$ be an endofunctor on $\cat{Prost}$.
Its algebras are a preordered set with a binary relation-preserving operation.
Its algebra morphisms are relation-preserving functions that preserving those operations.
It has the property that it maps surjections to surjections.
The identity functor has the property that it maps initial mono-sources to initial mono-sources.
Consequently, $\cat{Alg}(F)$ inherits the factorization structure on $\cat{Prost}$.

The free $F$-algebra on a preordered set $\alg{X}$ is the set of trees with binary nodes and $X$-labeled leaf nodes, such that two leaf nodes are less than each other iff their labels are, and two binary nodes are less than each other iff their left children are and their right children are.
Call this preordered set $\alg{T}(\alg{X})$.
An $F$-algebra is associative if and only if every morphism from $\alg{T}(\langle \mathbb{3}, = \rangle)$ factors through the flattening function to $\List_+(\langle \mathbb{3}, = \rangle)$.
The flattening function is surjective, thus the full subcategory satisfying this implication inherits the factorization structure on $\cat{Alg}(F)$.
Call this subcategory $\cat{Sgr}_\leq$.

$\langle \R, \leq, + \rangle$ is a preordered semigroup, i.e.~an object of $\cat{Sgr}_\leq$.
A ranked preordered semigroup is an object $\alg{S}$ of $\cat{Sgr}_\leg$ with a morphism $\mo{r} : \alg{S} \mto \langle \R, \leq, + \rangle$; in other words, an object of $\cat{Sgr}_\leq \downarrow \langle \R, \leq, + \rangle$.
A morphism of ranked preordered semigroups is a morphism of $\cat{Sgr}_\leq \downarrow \langle \R, \leq, + \rangle$.
Since this is a slice category, it inherits the factorization structure on $\cat{Sgr}_\leq$.
\end{proof}

\end{document}