12
$\begingroup$

Let $P,Q$ be partially ordered sets (posets). We consider the set $\text{Hom}(P,Q)$ of order-preserving functions $f:P\to Q$. (We call a function $f:P\to Q$ order preserving if $x\leq y$ in $P$ implies $f(x)\leq f(y)$ in $Q$.)

There is a natural ordering relation on $\text{Hom}(P,Q)$ given by $f\leq g$ if and only if $f(p) \leq_Q g(p)$ for all $p\in P$.

Let $D$ be directed and $P$ be a poset. Is $\text{Hom}(P,D)$ necessarily directed?

$\endgroup$
1
  • $\begingroup$ I asked this question a few decades ago. I asked someone, who gave me a negative answer. I vaguely recall it was A. W. Roscoe. $\endgroup$
    – Tri
    Commented Jul 19, 2021 at 20:55

3 Answers 3

10
$\begingroup$

The answer is negative.

Let $P=\omega_1$, and $Q$ be the disjoint union of

  • $A=A_0\mathbin{\dot\cup}A_1$, where each $A_i$ is a copy of $\omega_1$,

  • $B$, which consists of finite subsets of $A$ that intersect both $A_0$ and $A_1$, ordered by inclusion.

If $a\in A$ and $b\in B$, we put $a\le b$ iff there is $a'\in b$ such that $a\le a'$. It is easy to see that $Q$ is directed.

Let $f$ and $g$ be the isomorphisms of $P$ to $A_0$ and $A_1$, respectively, and assume for contradiction that $f,g\le h$ for some order-preserving $h\colon P\to Q$. For every $\alpha\in P$, we must have $h(\alpha)\in B$. However, $B$ contains no strictly increasing chain of length $\omega+1$, hence $h(\alpha)$ is eventually constant. This is impossible, as every element of $Q$ has only countably many predecessors, whereas $f[P],g[P]$ are uncountable.

$\endgroup$
7
$\begingroup$

If $D$ is countable, then the answer is yes. The reason is that every countable directed order $D$ has a cofinal $\omega$ sequence $$d_0<d_1<\cdots <d_n<\cdots,$$ which can be constructed by iteratively getting above the $n^{th}$ point of $D$ at step $n$. Now, given homomorphisms $f:P\to D$ and $g:P\to D$, define $h(x)$ to be the least $d_k$ above $f(x)$ and $g(x)$. This is order-preserving and above both $f$ and $g$.

More generally, if $D$ has a cofinal linear order, then it has a cofinal well-ordered sequence $d_0<d_1<\cdots<d_\alpha<\cdots$, and we may use the same idea. Namely, define $h(x)$ to be the least $d_\alpha$ above both $f(x)$ and $g(x)$.

The argument generalizes beyond linear cofinal orders as follows. First, notice that if $D$ is an upper semi-lattice, then clearly the answer is yes, since we may take the least upper bound of $f(x)$ and $g(x)$. But more generally, it suffices if $D$ admits an order-preserving map $r:D\to D$ whose range is contained in an upper semi-lattice suborder of $D$, for in this case we may take the least upper bound of $r\circ f$ and $r\circ g$.

I'm not sure whether there is a directed set $D$ with no such map $r$.

So a counterexample for the question, if there is one, should be fat rather than tall and should have no natural cofinal upper semi-lattice suborder.

$\endgroup$
2
  • $\begingroup$ For similar reasons, the answer is also positive if $P$ has a countable cofinal subset. $\endgroup$ Commented Dec 11, 2014 at 13:55
  • $\begingroup$ Yes, I agree, since in this case we can work essentially with the countable image of $P$ in $D$. $\endgroup$ Commented Dec 11, 2014 at 14:01
7
$\begingroup$

Let me give a simple necessary and sufficient condition which characterizes which directed sets $D$ satisfy the property that $Hom(P,D)$ is directed for all posets $P$.

Suppose that $D$ is a poset. Then I claim that $Hom(P,D)$ is directed for every poset $P$ if and only if there is a function $L:D\times D\rightarrow D$ such that $L(x,y)\geq x,L(x,y)\geq y$ for each $x,y\in D$ and where if $x_{1}\leq x_{2},y_{1}\leq y_{2}$, then $L(x_{1},y_{1})\leq L(x_{2},y_{2})$. In other words, $Hom(P,D)$ is directed for each poset $P$ if and only if $D$ is $``$monotonely directed$"$ or $``$uniformly directed$"$. The proof is straightforward, but let me give a proof below regardless.

Suppose there is such a function $L:D\times D\rightarrow D$. Then whenever $f,g\in Hom(P,D)$ are order preserving, then define $h(x)=L(f(x),g(x))$. Then whenever $x\leq y$, we have $f(x)\leq f(y),g(x)\leq g(y)$, so $h(x)=L(f(x),g(x))\leq L(f(y),g(y))=h(y)$, so $h$ is order preserving. Furthermore, $h(x)=L(f(x),g(x))\geq f(x)$ and $h(x)=L(f(x),g(x))\geq g(x)$, so $h\geq f$ and $h\geq g$, so $Hom(P,D)$ is always directed.

Now suppose that $Hom(P,D)$ is directed for each poset $P$. Then $Hom(D\times D,D)$ is directed where $D\times D$ is given the partial ordering where $(x_{1},y_{1})\leq(x_{2},y_{2})$ if and only if $x_{1}\leq x_{2}$ and $y_{1}\leq y_{2}$. Let $\pi_{1},\pi_{2}:D\times D\rightarrow D$ be the projection mappings. In other words, $\pi_{1}(x,y)=x,\pi_{2}(x,y)=y$. Then $\pi_{1},\pi_{2}$ are order preserving, so there is some $L\in Hom(D\times D,D)$ with $\pi_{1},\pi_{2}\leq L$. Therefore, $L$ is an order preserving map with $L(x,y)\geq\pi_{1}(x,y)=x$ and $L(x,y)\geq\pi_{2}(x,y)=y$.

$\endgroup$
1
  • $\begingroup$ I enjoyed that. $\endgroup$
    – Tri
    Commented Jul 20, 2021 at 5:41

You must log in to answer this question.