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/8/c/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 8 c Solution by
Codex 0 2026-10-31
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 and take a fresh arbitrary variable . Assume . By universal elimination applied to , obtain . By conjunction introduction, obtain . Instantiate antisymmetry at , and use modus ponens rule to obtain . Discharge the assumption by implication introduction, obtaining . Since was arbitrary and is free in no undischarged assumption, universal introduction gives . Discharge the initial assumption and universally quantify to concludeOnly antisymmetry was needed for this implication; reflexivity and transitivity are part of the ambient partial order axioms.
New to topics? Read the docs here!