# Products and coproducts in the simplex category

I wonder if the category $\Delta$ of finite totally ordered sets and monotone functions has binary products and coproducts. In particular, is the ordinal sum a categorical coproduct and/or is there any comparable "ordinal product"?

• If $[n]=\{1,2,..,n\}$, and $f:[n]\rightarrow [k]$ and $g:[m]\rightarrow [k]$ are monotone functions, can you always find a $h:[n+m]=[n]+[m]\rightarrow [k]$ which is a monotone function on and which, when restricted to the first $n$ elements is $f$ and last $m$ elements is equal to $g$? – Thomas Andrews Nov 21 '11 at 16:05
• I believe we can. Define $h(x) = f(x)$ if $x \le n$ and $h(x) = g(x - n)$ otherwise. – saintali Nov 21 '11 at 16:13
• Ah, but now I think my $h$ is not necessarily monotone :( – saintali Nov 21 '11 at 16:15
• Products have a similar problem - specifically, there has to be a category isomorphism between $[n]\times[m]$ and $[m]\times[n]$ which commutes with projections to $[n]$ and $[m]$. – Thomas Andrews Nov 21 '11 at 16:23
• @saintali: Take Thomas' example with $n=m=k$. Can there be a monotone function from $n+n$ into $n$? – Asaf Karagila Nov 21 '11 at 19:57

Rewritten completely, same conclusions.

Let $\mathbf{TOrd}$ be the category of totally ordered sets with monotone maps (maps such that $a\leq b\Rightarrow f(a)\leq f(b)$); let $\mathbf{TOrd}_s$ b the category of totally ordered sets with strictly monotone maps (maps such that $a\lt b \leftrightarrow f(a)\lt f(b)$); and let $\mathbf{FTord}$ and $\mathbf{FTord}_s$ be the full subcategories of finite totally ordered sets. (The diference between $\mathbf{TOrd}$ and $\mathbf{TOrd}_s$ is that in the former we can have $a\lt b$ and $f(a)=f(b)$, whereas in the latter we cannot.

Theorem 1. Let $\mathcal{C}$ be any of $\mathbf{TOrd}$, $\mathbf{TOrd}_s$, $\mathbf{FTOrd}$, or $\mathbf{TOrd}_s$. If $A$ and $B$ each have at least two elements, then there is no product of $A$ and $B$ in $\mathcal{C}$.

Proof. Assume that $A$ and $B$ are totally ordered sets, and each has at least two elements. Let $a_1,a_2\in A$, $a_1\lt a_2$; and let $b_1,b_2\in B$, with $b_1\lt b_2$. Consider the maps from the singleton totally ordered set $S=\{\bullet\}$ to $A$ and $B$ given by $f_A\colon S\to A$, $f_B\colon S\to A$, $f_A(\bullet)=a_2$, $f_B(\bullet)=b_1$; and $g_A\colon S\to A$, $g_B\colon S\to B$ given by $g_A(\bullet)=a_1$, $g_B(\bullet)=b_2$.

If there is a totally ordered set $X$ with monotone maps $p_A\colon X\to A$ and $p_B\colon X\to B$ such that both $f_A,f_B$ and $g_A,g_B$ factors through $(X,p_A,p_B)$ via maps $F,G\colon S\to X$, then note that since $p_A(F(\bullet))=a_2\gt a_1= p_A(G(\bullet))$, we must have $F(\bullet)\gt G(\bullet)$. But then we must have $b_1 = p_B(F(\bullet)) \gt p_B(G(\bullet))=b_2$, contradicting the choice of $b_1$ and $b_2$. Thus, no such $X$ exists, and therefore there is no product of $A$ and $B$ in $\mathcal{C}$. $\Box$

Theorem 2. Let $\mathcal{C}$ be any of $\mathbf{TOrd}$, $\mathbf{TOrd}_s$, $\mathbf{FTOrd}$, or $\mathbf{TOrd}_s$. If $A$ and $B$ each have at least one element each, then there is no coproduct of $A$ and $B$ in $\mathcal{C}$.

Proof. Let $X = \{1\}\times A\cup \{2\}\times B\cup \{3\}\times A$; order $X$ lexicographically; that is, $(i,x)\leq (j,y)$ if and only if $i\lt j$, or $i=j$ and $x\leq y$. Let $f_1,f_3\colon A\to X$ be given by $f_i(a) = (i,a)$, and let $g\colon B\to X$ be given by $g(b)=(2,b)$.

If there is an object $C$ in $\mathcal{C}$ and maps $\iota_A\colon A\to C$ and $\iota_B\colon B\to C$ such that both $f_1,g$ and $f_3,g$ factor through $(C,\iota_A,\iota_B)$, then there exist maps $F_1\colon C\to X$ and $F_3\colon C\to X$ such that $f_1=F_1\circ\iota_A$, $f_3=F_3\circ\iota_A$, and $g=F_1\circ\iota_B = F_3\circ\iota_B$. Let $a\in A$ and $b\in B$. Since $f_1(a)\lt g(b)$, then $\iota_A(a)\lt iota_B(b)$; but since $g(b)\lt f_3(a)$, we must have $\iota_B(b)\lt \iota_A(a)$. This is impossible, so no such object $C$ exists. That is, $A$ and $B$ do not have a coproduct in $\mathcal{C}$. $\Box$

For the remaining cases, we have:

Theorem 3. Let $\mathcal{C}$ be $\mathbf{TOrd}$ or $\mathbf{FTOrd}$.

1. If $A$ is a singleton, and $B$ is arbitrary, then $(B,p_A,\mathrm{id}_B)$ is a product of $A$ and $B$ in $\mathcal{C}$, where $p_A\colon B\to A$ is the unique map from $B$ to $A$.
2. If $A$ is empty, and $B$ is arbitrary, then $(A,\mathrm{id}_A,n)$ is a product of $A$ and $B$ in $\mathcal{C}$, where $n$ is the empty map with domain $A$ and codomain $b$.

Proof.

1. Let $X$ be any object of $\mathcal{C}$, and let $f\colon X\to A$ and $g\colon X\to B$ be maps. Then the maps factor uniquely through $B$ via $f$, so $(B,p_A,\mathrm{iid}_B)$ is a product of $A$ and $B$.

2. Let $X$ be an object of $\mathcal{C}$ and $f\colon X\to A$ and $g\colon X\to B$ be maps; since $A$ is empty, then $X$ must be empty, so the unique map $X\to A$ shows that $(A,\mathrm{id}_A,n)$ has the desired universal property. $\Box$

Theorem 4. Let $\mathcal{C}$ be $\mathbf{TOrd}_s$ or $\mathbf{FTOrd}_s$.

1. If $A$ is a singleton and $B$ is not empty and not a singleton, then there is no product of $A$ and $B$ in $\mathcal{C}$.
2. If $A$ and $B$ are both singletons, then $(A,\mathrm{id}_A,p)$ is a product of $A$ and $B$, where $p$ is the unique map $p\colon A\to B$.
3. If $A$ is empty, and $B$ is arbitrary, then $(A,\mathrm{id}_A,n)$ is a product of $A$ and $B$ in $\mathcal{C}$, where $n\colon A\to B$ is the empty map.

Proof.

1. Since maps in $\mathcal{C}$ must be one-to-one, a product of $A$ and $B$ must be either empty or a singleton (otherwise, there are no maps into $A$). But then $p_B(C)\neq B$; letting $S=\{\bullet\}$ be a singleton, let $b\in B-p_B(C)$; then the pair $(f,g)$, where $f\colon S\to A$ is the unique map between singletons and $g\colon S\to B$ has $g(\bullet)=b$ cannot factor through $(C,p_A,p_B)$. So $A$ and $B$ do not have a product in $\mathcal{C}$.

2. The only objects that can map to $A$ and $B$ are the emptyset and singletons, and the maps clearly factor through $(A,\mathrm{id}_A,p)$.

3. The only object that can map to $A$ is the empty set. $\Box$

Theorem 5. Let $\mathcal{C}$ be $\mathbf{TOrd}$, $\mathbf{FTOrd}$, $\mathbf{TOrd}_s$, or $\mathbf{FTOrd}_s$. If $A$ is empty and $B$ is arbitrary, then $(B,n,\mathrm{id}_B)$ is a coproduct of $A$ and $B$, where $n\colon A\to B$ is the empty map.

Proof. Let $X$ be an object of $\mathcal{C}$, $f\colon A\to X$, and $g\colon B\to X$. Then $f$ must be the empty map, so $f$ and $g$ factor uniquely through $(B,n,\mathrm{id}_B)$. Thus, this is a coproduct for $A$ and $B$. $\Box$