Complete partial order

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 partially ordered set is directed-complete if every directed set in it has a least upper bound. A complete lattice is directed-complete. Conversely, directed completeness together with all finite joins, including the empty join, gives arbitrary joins: take the directed set of joins of finite subsets.

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.

A monotone map preserving suprema of nonempty directed sets. Between pointed domains it need not send bottom to bottom. The pointwise directed supremum of a directed family of such maps is again Scott continuous: interchange the two directed suprema in ${\sup }_f{\sup }_{x\in A}f(x)$.

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.

For Scott continuous maps $e:D\to E$, $p:E\to D$, these two identities say that $D$ is embedded in $E$ and that projection followed by embedding approximates from below. Such pairs lift to endomorphism spaces by $f\mapsto efp$ and $g\mapsto pge$. Their composite on the smaller space is the identity, and the other composite is $g\mapsto (ep)g(ep)\le g$.

For $D_{n+1}=[D_n\to D_n]$ with recursively lifted embedding-projection pairs, form coherent sequences $x_n=p_n{x}_{n+1}$, ordered componentwise. Stage projections $P_n$ and embeddings $E_n$ satisfy $P_n{E}_n=\mathrm{id}$, $E_n{P}_n\uparrow \mathrm{id}$. A coherent family $f_n\in [D_n\to D_n]$ induces $f={\sup }_n{E}_n{f}_n{P}_n$; conversely $f_n=P_{n}f{E}_n$. These constructions are inverse. Removing the initial coordinate of the coherent sequence identifies this function-space limit with the original domain limit.

The Scott continuous maps from $D$ to $E$, ordered pointwise. A nonempty directed family has pointwise supremum, and the constant-bottom function is least. Joint evaluation is Scott continuous: for a directed family of pairs $(f_i,x_i)$, directedness makes diagonal values cofinal among all $f_i(x_j)$. Evaluation and currying make the category of pointed complete partial orders and non-strict Scott continuous maps a Cartesian closed category.

For a directed set of Scott continuous maps $f_i:D\to E$, its least upper bound is $f(x)={\sup }_i{f}_i(x)$. The two directed suprema over $i$ and over inputs commute, proving that $f$ remains Scott continuous. Thus the function space of complete partial orders is a complete partial order.

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