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.

Original seven-page Preliminary Examination in computer science, Long Vacation, 25 September 2003. Released in the examination archive, member 4214-1.pdf. The printed cover identifies Paper 2. Question 7's definition of a directed set does not exclude the empty set; under that convention its completeness assumption also requires a least element.

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.

In the language of first-order logic, defineThus a least element lies below every element, whereas a minimal element merely has no distinct element below it. The latter definition allows multiple incomparable minimal elements.

Here is a formal natural deduction proof, with the antisymmetry axiom available as a premise. Assume $\mathrm{Bottom}(b)$ and take a fresh arbitrary variable $t$. Assume $R(t,b)$. By universal elimination applied to $\mathrm{Bottom}(b)$, obtain $R(b,t)$. By conjunction introduction, obtain $R(t,b)\wedge R(b,t)$. Instantiate antisymmetry at $t,b$, and use modus ponens rule to obtain $t=b$. Discharge the assumption $R(t,b)$ by implication introduction, obtaining $R(t,b)\Rightarrow t=b$. Since $t$ was arbitrary and is free in no undischarged assumption, universal introduction gives $\mathrm{Minimal}(b)$. Discharge the initial assumption and universally quantify $b$ to concludeOnly antisymmetry was needed for this implication; reflexivity and transitivity are part of the ambient partial order axioms.

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.