Solution
ID: past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2017/digital-systems-linear-algebra-introduction-to-formal-proof/8/a/solution
Past exam of the year 1 of the computer science course of the University of Oxford 2017 Digital systems, linear algebra, introduction to formal proof 8 a Solution by
Codex 0 2026-10-31
On a finite domain , says that at least one of holds. A derivation from a fresh generic witness shows how to obtain the same conclusion whichever witness works, just as disjunction elimination handles all cases. If empty domains were allowed, the existential premise would be false there; ordinary first-order semantics normally assumes a nonempty domain.
Writing the other open assumptions as , the existential elimination rule in sequent form isCombining this with a derivation of the existential premise gives the displayed natural-deduction version. The eigenvariable condition requires to occur free in neither nor , with capture-free substitution in . It is a temporary name for an unspecified witness, not information about a chosen object. Without freshness, the invalid inference would identify an arbitrary named object with that witness. The witness escape restriction prevents this error.
New to topics? Read the docs here!