# Universal and left-factoring order-preserving maps

Trying to get a different angle for the question Fixed points and universal maps for posets, I want to compare universal maps to a different kind of functions.

First recall that for posets $P,Q$ an order-preserving map $u:P\to Q$ is universal if for any order-preserving map $f:P\to Q$ there is $x\in P$ such that $f(x) = u(x)$.

Let $\mathcal{C}$ be any category and let $A, B$ be objects. A morphism $l: A\to B$ is said to be left-factoring if for any $Z\in \mathbf{Ob}(\mathcal{C})$ and any morphism $f: Z\to B$ there is $h: Z\to A$ such that $f = l\circ h$. (I didn't find the correct terminology for what I call left-factoring maps; any help is appreciated.)

In the category of posets, it is easy to see that universal maps, as well as left-factoring maps, are surjective. (The converse does not hold for either universal or left-factoring maps.)

Question: Are universal maps left-factoring?

(Note that left-factoring maps need not be universal: the identity on $\omega$ with the usual well-ordering is left-factoring, but not universal, because $\textsf{id}_\omega$ and the successor map $n\mapsto n+1$ do not agree on any point.)

I claim that not every universal map is left-factoring. Let me first give a proposition that allows us to construct many universal maps, and then I will give a counterexample from the proposition. A poset $X$ shall be called a DCPO (directed complete partial order) if every directed subset of $X$ has a least upper bound. It is well known and not to hard to show that a poset is a DCPO if and only if every well ordered chain in $X$ has a least upper bound. Recall that the Knaster-Tarski fixed point theorem states that if $L$ is a complete lattice and $f:L\rightarrow L$, then $f$ has a fixed point. The following proposition is a generalization of the Knaster-Tarski fixed point theorem that allows us to construct universal mappings.

$\mathbf{Proposition}$ Suppose that $f,g:X\rightarrow Y$ are order preserving maps where

1. $f(0)=0$

2. $X$ is a DCPO

3. whenever $L\subseteq X$ is a chain, then $f[L]$ has a least upper bound and $f(\bigvee L)=\bigvee f[L]$.

4. whenever $x\in L$ and $f(x)<r$, there is some $y>x$ with $f(y)\leq r$.

Then there is some $c$ with $f(c)=g(c)$.

$\mathbf{Proof}$ We shall construct a transfinite strictly increasing sequence $(x_{\alpha})_{\alpha}$ in $X$ such that $f(x_{\alpha})\leq g(x_{\alpha})$ until we obtain an $x_{\delta}$ with $f(x_{\delta})=g(x_{\delta})$. Let $x_{0}=0$. If $\gamma$ is a limit ordinal and $x_{\alpha}$ has been obtained for $\alpha<\gamma$, then let $x_{\gamma}=\bigvee_{\alpha<\gamma}x_{\alpha}$. Then since $f(x_{\alpha})\leq g(x_{\alpha})$ for all $\alpha<\gamma$, we have $f(x_{\gamma})=f(\bigvee_{\alpha<\gamma}x_{\alpha})=\bigvee_{\alpha<\gamma}f(x_{\alpha})\leq g(x_{\gamma})$.

Now suppose that $x_{\alpha}$ has been constructed and $f(x_{\alpha})\leq g(x_{\alpha})$. If $f(x_{\alpha})=g(x_{\alpha})$, then we discontinue the transfinite process. If $f(x_{\alpha})<g(x_{\alpha})$, then there is some $x\in X$ with $x>x_{\alpha}$ and $f(x)\leq g(x_{\alpha})$. Therefore select some $x_{\alpha+1}\in X$ such that $x_{\alpha}<x_{\alpha+1}$ and $f(x_{\alpha+1})\leq g(x_{\alpha})$. Then we have $f(x_{\alpha+1})\leq g(x_{\alpha+1})$, and the transfinite process continues. This transfinite process however must terminate at some ordinal $x_{\delta}$, so we have $f(x_{\delta})=g(x_{\delta})$. $\mathbf{QED}$.

Let's now use the above proposition to construct a universal map that is not left-factoring. Suppose that $T$ is a the tree which consists of all strictly increasing functions $f:\alpha\rightarrow[0,1]$ for some ordinal $\alpha$. Let $L:T\rightarrow[0,1]$ be the mapping where $L(f)=\sup\{f(\beta)|\beta\in\textrm{Dom}(f)\}$. Then $L$ is universal. However, the mapping $L$ is not left-factoring. In particular, there is no order preserving map $h:[0,1]\rightarrow T$ with $L\circ h=1_{[0,1]}$ where $1_{[0,1]}$ denotes the identity function on $[0,1]$. If $h$ were such a mapping with $L\circ h=1_{[0,1]}$, then whenever $r<s$, then $r=L(h(r))<L(h(s))=s$, so $h(r)<h(s)$, hence $\textrm{Dom}(h(r))<\textrm{Dom}(h(s))$. However, if $(x_{n})_{n}$ is an infinite descending sequence of real numbers in $[0,1]$, then $(\textrm{Dom}(h(x_{n})))_{n}$ would be an infinite descending sequence of ordinals, a contradiction.

• Very good example + presentation! Maybe this example can be made to work as a counterexample for the claim "The composition of 2 universal maps is universal" Dec 16 '14 at 17:45
• @Dominic van der Zypen. Yes. I was thinking about using the proposition mentioned in this answer to construct a counterexample to the claim that the collection of universal maps is closed under composition. In particular, I was thinking about compositing a map satisfying the assumptions of the proposition with a map satisfying the assumptions of the dual of the proposition. Dec 16 '14 at 18:17