1
$\begingroup$

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.)

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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" $\endgroup$ Dec 16 '14 at 17:45
  • $\begingroup$ @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. $\endgroup$ Dec 16 '14 at 18:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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