Solution
ID: 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/c/solution
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 c Solution by
Codex 0 2026-10-31
We prove the result algebraic partially ordered sets are continuous directly from the definitions. First, implies , by applying the way-below relation to the singleton directed set . Also,if , then , so the witness required for also works for .
Fix and putBy algebraicity, is a directed set with least upper bound . Every satisfies , hence . Thus .
To prove that is a directed set, take . Applying and to gives such that and . Directedness of gives above both. Since , it is the required common upper bound inside . With the usual nonempty convention, is nonempty since it contains .
By directed completeness has a least upper bound. The inclusions above givesoThe same proof handles the paper's literal empty-set convention. If , then , and the defining implication for , applied to , shows that must also be empty. Its least upper bound is again . If is nonempty, the argument already given applies without change.
New to topics? Read the docs here!