Solution
ID: past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2016/digital-systems-linear-algebra-introduction-to-formal-proof/8/a/ii/solution
Past exam of the year 1 of the computer science course of the University of Oxford 2016 Digital systems, linear algebra, introduction to formal proof 8 a ii Solution by
Codex 0 2026-10-31
Choose a fresh parameter . The universal quantifier elimination rule supplies both the implication and its premise at that same parameter:The eigenvariable condition holds because is absent from both undischarged assumptions at line 6. Hence the universally quantified implication is proved.
1 ∀x. (P(x) → Q(x)) premise
2 | ∀x. P(x) assumption
3 | P(a) ∀-elim 2
4 | P(a) → Q(a) ∀-elim 1
5 | Q(a) →-elim 4,3
6 | ∀x. Q(x) ∀-intro 5, a fresh
7 (∀x. P(x)) → (∀x. Q(x)) →-intro 2–6The proposed version with merely in the antecedent is not derivable. For a counterexample, take a two-element domain with and both true precisely at zero. The universal premise holds. Under the assignment , is true but is false. By soundness, a formal proof cannot exist. Attempting the previous derivation would fail exactly at universal quantifier introduction rule: the parameter would occur in the undischarged assumption , so it would not be fresh.
New to topics? Read the docs here!