Solution
ID: 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/b/solution
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 b Solution by
Codex 0 2026-10-31
Take the five-element partially ordered set . Its strict comparisons are , , and , , , , together with their transitive consequences. The elements are incomparable, as are .
Two different failures of order completeness
. Details. 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 has a least upper bound. The empty subset also has a least upper bound, namely . Therefore satisfies the paper's completeness condition under either convention.
However, is bounded above by both and . A least upper bound would have to be an upper bound lying below both and . Neither nor has that property, and none of is an upper bound of . Hence
New to topics? Read the docs here!
