Does there exist an ordering-functor?

Question

This sounds like a very silly question which should have have a negative answer but I don't see an argument. The precise question is this:

Does there exist a covariant functor $ord$ from the category of sets and functions to the category of totally ordered sets and increasing functions such that every set $X$ is the underlying set of $ord(X)$?

---

Of course, I assume the axiom of choice so that every set can be even well-ordered. Since the well-ordering is based on rather arbitrary choices there does not seem to be a reason why it should be in any sense "compatible" with all functions. My guess is that such a functor does not even exist in the subcategory of finite sets.

Answer 1

Conceptual answer.

There can be no such functor. Let $C$ be any concrete category of finite sets and mappings such that the only automorphisms in $C$ are trivial. I claim there is no underlying set preserving functor $F$ from the category $\mathbf{FSet}$ of finite sets to $C$. The category of finite totally ordered sets and order-preserving maps is of this form.

Let us call the rank of a mapping the size of its image.

First note in the category $\mathbf{FSet}$ of finite sets, all idempotents split. That is, if $e\colon X\to X$ is an idempotent then there are morphisms $f\colon X\to Y$ and $g\colon Y\to X$ with $gf=e$ and $fg=1_Y$ for some finite set $Y$. Here you can take $Y$ to be the image of $e$ and take $g$ to be the inclusion and $f$ to be the "corestriction" of $e$. Since $F(f)F(g)=F(fg)=F(1_Y)=1_Y$, we deduce that $F(f)$ is surjective and $F(g)$ is injective and so $F(e)=F(g)F(f)$ has image of size $|Y|$. Thus $F$ preserves the ranks of idempotents, i.e., rank $e$ = rank $F(e)$.

Next note that if $|X|\geq 3$, then there is an idempotent of rank $|X|-2$ which is a product of conjugate rank $|X|-1$ idempotents. To ease notation assume $|X|=n$. For $i\neq j$ let $e_{i,j}$ be the rank $n-1$ idempotent with $e_{i,j}(i)=i=e_{i,j}(j)$ and which fixes all other elements. Let $k\neq i,j$. Then $f=e_{i,j}e_{j, k}$ sends $i,j,k$ to $i$ and fixes all other elements and so is a rank $n-2$ idempotent.

Notice that $e_{i,j}$ and $e_{j,k}$ are conjugate by the permutation $(i,j,k)$: we have $e_{j,k} = (i,j,k)e_{i,j}(k,j,i)$. Since $F((i,j,k))=1_X$, we must have $F(e_{i,j})=F(e_{j,k})$. Since these are idempotents, $F(f)=f(e_{i,j})$, contradicting that $F$ preserves rank of idempotents.

Original answer. I think there is no functor from finite sets to finite totally ordered sets with order preserving maps preserving underlying sets. Here is a proof. Let $F$ be such a functor. It must send every permutation of a finite set $X$ to the identity as there are no non-trivial automorphisms of a finite totally ordered set. Next I claim that every non-invertible endomorphism $f\colon X\to X$ has $F(f)$ a constant mapping. For this, I use the well known fact that the monoid of self-maps of $X$ is generated by the symmetric group $S_X$ and any idempotent $e$ with image of size $|X|-1$. Hence, since $F(S_X)$ is the identity, every non-invertible mapping gets sent to $F(e)$. But if $f\colon X\to X$ is a constant mapping, we have that $f= gh$ with $h\colon X\to \{1\}$ and $g\colon \{1\}\to X$. Thus $F(f)=F(g)F(h)$ has image of size $1$. Thus $F(e)$ above must have image of size $1$ and so every non-invertible mapping of $X$ to $X$ is sent to a constant mapping. This is a problem.

Consider $f\colon \{1,2\}\to \{1,2,3\}$ given by the inclusion and $g\colon \{1,2,3\}\to \{1,2\}$ given by $g(1)=1$, $g(2)=2$ and $g(3)=2$. Then $gf$ is the identity but $fg$ is non-invertible. Thus $F(gf)$ is an identify mapping and $F(fg)$ is a constant mapping, which is impossible as $gf=gfgf$ and so $F(gf)=F(g)F(fg)F(f)$ is both a constant map and an identity for a two element set.