Today I Learned

May 11th

Today I learned a little about maps between totally ordered sets. The main observation here is that ordered sets behave more or less like algebraic structures in that they are "sets with extra structure'' even if that structure doesn't come in the form of a binary operation. To make this easier to codify, we work in with category theory.

It should not be immediately clear why this gives a partial order, but we run through the axioms to compare. Namely, we turn a partial order $(\mathcal C,\le)$ into a category by saying $C_1\le C_2$ induces a unique morphism $C_1\to C_2.$

• Reflexivitiy: this is equivalent to the existence of morphisms $C\to C$ for $C\in\mathcal C,$ for which $\op{id}_C$ are guaranteed because $\mathcal C$ is a category.

• Antisymmetry: if we have $f:C\to C'$ and $g:C'\to C,$ then we note $f\circ g:C'\to C'$ and $g\circ f:C\to C,$ but because there is only one morphism in each of these classes, we must have $f\circ g=\op{id}_{C'}$ and $g\circ f=\op{id}_C.$ In particular, $C$ and $C'$ are isomoprhic. So isomprhisms capture our notion of antisymmetry.

• Transitivity: the ability to inhabit \[\op{Mor}(C,C')\to\op{Mor}(C',C'')\to\op{Mor}(C,C'')\] is exactly what composition of morphisms is for.

So indeed, the definition of a partially ordered category cleanly captures the notion of a partially ordered category.

Maps between partially ordered sets can be annoying, so we move into totally ordered categories.

Totality has been captured by requiring there to be at least one morphism $C\to C'$ or $C'\to C.$ The bound of exactly one is done here to make our notion of antisymmetry stronger than mere isomorphism: now, if we inhabit both $C\to C'$ and $C'\to C,$ then they must be the same class, so $C=C'$ as objects. We do this for purely psychological reasons.

Anyways, the point of moving to category theory is that it lets us more easily talk about maps between partially/totally ordered sets. Intuitively, we would like a map $\varphi$ between partially/totally ordered sets $(X,\le_X)$ and $(Y,\le_Y)$ to be a function $\varphi:X\to Y$ such that\[x_1\le_Xx_1\implies\varphi(x_1)\le_X\varphi(x_2).\]In category theory, we get this for free using functors! Fixing partially/totally ordered categories $\mathcal C$ and $\mathcal D,$ we see that a functor $F:\mathcal C\to\mathcal D$ has\[C_1\stackrel f\to C_2\implies F(C_1)\stackrel{F(f)}\to F(C_2)\]because of how functors behave. Thus, we can talk about maps between our partially/ordered sets more cleanly by calling them functors. In particular, we have more theory to deal with the axioms.

It turns out that functors between totally ordered sets/categories don't look terribly interesting. We have the following.

\begin{proof} This is by induction. Fix the objects of our category $\{x_1,x_2,\ldots,x_n\}$ with a unique arrow $x_a\to x_b$ whenever $a\le b.$ Further, suppose that $F:\mathcal C\to\mathcal C$ is an endofunctor. Because our morphisms are unique, we really only have to worry about where our elements are going. We claim, by (strong) induction that $F(x_k)=x_k$ for $1\le k\le n.$

As our base case, we show $k=1.$ Suppose for the sake of contradiction that $F(x_1)=x_\ell$ for $\ell\ne1.$ Then we may look at the arrow $f:x_{\ell-1}\to x_\ell,$ and because $F$ is a bijective endofunctor, we can look backwards at \[F^{-1}(f):F^{-1}(x_{\ell-1})\to x_1.\] However, there are no arrows into $x_1,$ so we have arrived at a contradiction.

Our inductive step is similar; by inductive hypothesis, we may assert that $F(x_\ell)=x_\ell$ for all $\ell \lt k \lt n$ so that we want to show $F(x_k)=x_k.$ Well, fix $\ell$ so that $F(x_k)=x_\ell$ for some $\ell\ge k.$ (We cannot have $\ell \lt k$ because these elements are already taken.) Then we can again look at $f:x_{\ell-1}\to x_\ell$ and trace back to \[F^{-1}(f):F^{-1}(x_{\ell-1})\to x_k.\] It follows that $F^{-1}(x_{\ell-1})$ maps to some $x_\bullet$ below $x_k.$ However, $F^{-1}(x_{\ell-1})$ cannot go to $x_k$ because identity morphisms map to identity morphisms, and $F^{-1}(f)$ is not the identity, so it follows $F^{-1}(x_{\ell-1})$ is below $x_{k-1}.$ But then we see $\ell\ge k,$ which requires $\ell=k$ for this to be possible, completing the proof.\end{proof}

Each of these hypotheses is necessary. If the endofunctor isn't bijective, then we could, for example, compress all of $\mathcal C$ to one of its elements and make all morphisms go to the identity. More creatively, it is also possible to compress $\mathcal C$ onto, say, two elements in a similar way.

The finite condition on $\mathcal C$ matters because we can, for example, take $\mathcal C=\ZZ$ with $\le$ to induce a totally ordered set, and then something like $n\mapsto n+1$ will provide an endofunctor. Infinite chains can in general be shifted like this.