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 / a

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.