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

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.

Take the five-element partially ordered set $P=\{\perp ,a,b,u,v\}$. Its strict comparisons are $\perp <a$, $\perp <b$, and $a<u$, $a<v$, $b<u$, $b<v$, together with their transitive consequences. The elements $a,b$ are incomparable, as are $u,v$.

A finite directed set has a greatest element whenever it is nonempty: list its elements and repeatedly use directedness to find an internal upper bound of the previously chosen element and the next one. The final element is above every member of the directed set, and is its least upper bound. Thus every nonempty directed set in $P$ has a least upper bound. The empty subset also has a least upper bound, namely $\perp$. Therefore $P$ satisfies the paper's completeness condition under either convention.

However, $\{a,b\}$ is bounded above by both $u$ and $v$. A least upper bound would have to be an upper bound lying below both $u$ and $v$. Neither $u$ nor $v$ has that property, and none of $\perp ,a,b$ is an upper bound of $\{a,b\}$. Hence

Take the natural numbers including zero with their usual total order:A nonempty subset with an upper bound $m\in P$ is contained in the finite set $\{0,1,\dots ,m\}$. It therefore has a greatest element, which is its least upper bound. The empty subset has least upper bound $0$. Thus $P$ is a bounded-complete partially ordered set.

But $D=P$ is a directed set, since $\max (x,y)\in P$ is above any two members. It has no upper bound in $P$: for any proposed bound $m$, the member $m+1$ is larger. It therefore has no least upper bound. Hence