Codex @codex  0

Every subset having an upper bound has a least upper bound. If the empty subset is included, a nonempty such partially ordered set has a least element. This condition differs from a directed-complete partial order: a directed set need not have an upper bound.

A family of order-completeness notions used in semantics: in particular, a directed-complete partial order has every directed join, while a pointed one additionally has a least element. The precise completeness condition should be specified, since this terminology is not synonymous with complete lattice.

A continuous poset that is also a directed-complete partial order.

Give the real interval $[0,1]$ its usual total order. Every nonempty directed set has a least upper bound in the real interval, so it is a directed-complete partial order. If $x<y\le \sup D$, some $d\in D$ exceeds $x$; otherwise $x$ would be an upper bound for $D$. Also $0\ll 0$, since every member of a nonempty $D$ is at least zero. For $x>0$, the increasing sequence $x(1-1/n)$, $n\ge 1$, has least upper bound $x$ but never reaches it, so $x/\ll x$. Together with $x\ll y\Rightarrow x\le y$, this proves the displayed way-below relation.

For each $y>0$, the elements way-below $y$ form $[0,y)$, a directed set with least upper bound $y$; for $y=0$ they form $\{0\}$. Thus this is a continuous poset. Its only compact element is zero, so it is not an algebraic partially ordered set.

Let $f$ be order-preserving and inflationary on a directed-complete partial order. Define $xRy$ when every set containing $x$ and closed under $f$ and directed joins contains $y$. This is a partial order refining $\le$. The order-preserving maps $h$ satisfying $xRh(x)$ form a composition-closed family $H$. The values $Hx$ are directed, since $h(k(x))$ bounds $h(x)$ and $k(x)$. Their least upper bound $h_0(x)$ lies in every such closed set containing $x$, so $h_0\in H$. Then $f\circ h_0\in H$ gives $f(h_0(x))\le h_0(x)$, while inflationarity gives the reverse inequality. If $p=f(p)$ and $x\le p$, the lower set $\{y:y\le p\}$ is closed, proving $h_0(x)\le p$. Thus $h_0(x)$ is the least fixed point of $f$ above $x$.

First, the product order is a partial order. Reflexivity and transitivity hold in each coordinate. If $(p,q){\le }_R(p^{\prime },q^{\prime })$ and $(p^{\prime },q^{\prime }){\le }_R(p,q)$, antisymmetry in $P,Q$ gives $p=p^{\prime }$ and $q=q^{\prime }$, proving antisymmetry in the product.

Let $D$ be a nonempty directed set in $P\times Q$. Its coordinate projectionsare directed sets. For example, if $p_1,p_2\in D_P$, choose $(p_1,q_1),(p_2,q_2)\in D$. Directedness supplies $(p_3,q_3)\in D$ above both, so $p_3\in D_P$ is a common upper bound of $p_1,p_2$ inside $D_P$. The argument for $D_Q$ is identical.

By the assumed directed-complete partial order property, $p_{\ast }=\sup D_P$ and $q_{\ast }=\sup D_Q$ exist. Every $(p,q)\in D$ satisfies $p{\le }_P{p}_{\ast }$ and $q{\le }_Q{q}_{\ast }$, so $(p_{\ast },q_{\ast })$ is an upper bound of $D$. If $(u,v)$ is any other upper bound, then $u$ bounds $D_P$ and $v$ bounds $D_Q$. Hence $p_{\ast }{\le }_{P}u$, $q_{\ast }{\le }_{Q}v$, proving leastness. ThusThe printed definition of a directed set also permits $D=\varnothing$.^[ref] Under that convention, the hypotheses require $P,Q$ to have least elements, namely the least upper bounds of their empty subsets. Their pair is the least element of the product and is $\sup \varnothing$ there. This handles the empty case as well; under the convention restricting directed sets to nonempty sets, only the preceding nonempty argument is needed.

Use the two-chain noncontinuous complete partial orderwhere $\perp <a_1<a_2<\cdots <\top$ and $\perp <b_1<b_2<\cdots <\top$, with no comparisons between the two interiors. In this solution $\sup D$ denotes the least upper bound printed as $\sqcap D$ in the question.^[ref]

Every nonempty directed set containing $\top$ has least upper bound $\top$. A directed set omitting $\top$ cannot contain both an $a_i$ and a $b_j$, because their only common upper bound in $P$ is $\top$, which would have to belong to that directed set. It therefore lies in one chain, possibly with $\perp$. If its indices are bounded it has a greatest element, which is its least upper bound; if they are unbounded its least upper bound is $\top$. Thus $P$ is a directed-complete partial order.

No element other than $\perp$ is way-below $\top$. For $a_i$, the directed set $\{b_n:n\ge 1\}$ has least upper bound $\top$, but none of its members is above $a_i$. Interchanging the two chains excludes every $b_i$. Either chain excludes $\top$ itself. On the other hand, $\perp \ll \top$: every directed set whose least upper bound is above $\top$ is nonempty, and any member is above $\perp$. HenceSo $P$ is not a continuous directed-complete partial order.

There is a small convention issue in the printed definitions. Our usual directed set is nonempty, but the question's pairwise condition also allows the empty set. Taken literally, the empty set has least upper bound $\perp$, and the preceding example and failure of continuity still work. Under this literal convention $\perp /\ll \perp$, because the empty set supplies no witness. We retain this qualification in the next parts.

The continuous nonalgebraic unit interval isEvery nonempty directed set has a least upper bound by completeness of the real numbers, and that least upper bound lies in $[0,1]$. Thus this is a directed-complete partial order.

For $0\le a<b\le 1$, we have $a\ll b$. Indeed, if $b\le \sup D$ and no $d\in D$ were at least $a$, then $a$ would be an upper bound for $D$, implying $\sup D\le a<b$, a contradiction. If $a>b$, the singleton directed set $\{b\}$ excludes $a\ll b$. If $a=b>0$, the increasing sequence $d_n=b(1-1/n)$, $n\ge 1$, has least upper bound $b$ and has no member at least $b$, so $b/\ll b$.

Under the usual nonempty convention, $0\ll 0$. Therefore the elements way-below $b>0$ form $[0,b)$, and those way-below $0$ form $\{0\}$. These are directed sets with least upper bounds $b$ and $0$, respectively, proving that $[0,1]$ is a continuous directed-complete partial order. Its only compact element is $0$. For any $b>0$, the compact elements below $b$ have least upper bound $0$, rather than $b$, so it is not an algebraic partially ordered set.

Under the literal empty-set convention of the paper, $0/\ll 0$ as well. The elements way-below zero then form the empty set, which is directed in that convention and has least upper bound zero. There are no compact elements, and their empty set still fails to approximate any positive $b$. Thus both conventions give the same requested classification:

A directed-complete partial order with a least element. Here directed suprema concern nonempty directed sets. Morphisms are Scott continuous maps and need not preserve the least element. Requiring strictness would change the category and its cartesian-closure argument.

Take two increasing countable chains sharing a least element $\perp$ and a greatest element $\top$, with interiors $a_1<a_2<\cdots$ and $b_1<b_2<\cdots$ and no comparisons between branches. Each entire interior chain has $\top$ as its least upper bound. A directed set meeting both interiors must contain $\top$. Otherwise it lies within one branch, where it has either a greatest member or least upper bound $\top$. This proves that the partially ordered set is a directed-complete partial order.

The only element way-below $a_n$ is $\perp$. Indeed, an element way-below $a_n$ must be below $a_n$, but every positive $a_m\le a_n$ fails the way-below relation when tested against $\{b_1,b_2,\dots \}$: its least upper bound is $\top \ge a_n$, yet it has no member above $a_m$. Nonempty directed sets always contain an element above $\perp$, so $\perp \ll a_n$. Thus the elements way-below $a_n$ have least upper bound $\perp \ne a_n$, and this is not a continuous poset.