Past exam of the year 1 of the computer science course of the University of Oxford / 2005 / Calculus, linear algebra, discrete mathematics, logic and proof, and models of computation / 6

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:

We prove the result algebraic partially ordered sets are continuous directly from the definitions. First, $a\ll b$ implies $a\le b$, by applying the way-below relation to the singleton directed set $\{b\}$. Also,if $c\le \sup D$, then $b\le \sup D$, so the witness required for $a\ll b$ also works for $a\ll c$.

Fix $x$ and putBy algebraicity, $K_x$ is a directed set with least upper bound $x$. Every $k\in K_x$ satisfies $k\ll k\le x$, hence $k\ll x$. Thus $K_x\subseteq A_x\subseteq \{a:a\le x\}$.

To prove that $A_x$ is a directed set, take $a,b\in A_x$. Applying $a\ll x$ and $b\ll x$ to $x=\sup K_x$ gives $k_a,k_b\in K_x$ such that $a\le k_a$ and $b\le k_b$. Directedness of $K_x$ gives $k\in K_x$ above both. Since $k\in A_x$, it is the required common upper bound inside $A_x$. With the usual nonempty convention, $A_x$ is nonempty since it contains $K_x$.

By directed completeness $A_x$ has a least upper bound. The inclusions above givesoThe same proof handles the paper's literal empty-set convention. If $K_x=\varnothing$, then $x=\sup \varnothing =\perp$, and the defining implication for $a\ll x$, applied to $D=K_x$, shows that $A_x$ must also be empty. Its least upper bound is again $x$. If $K_x$ is nonempty, the argument already given applies without change.