Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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"?

share|improve this question
    
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
1  
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

1 Answer 1

up vote 2 down vote accepted

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$

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.