Past exam of the mathematics course of the University of Cambridge 2022 iii Paper 120 1 c Solution 2026-09-28
Take a three-world Kripke model for intuitionistic propositional logic with a root and two incomparable terminal successors and . Force only at , force only at , and force neither atom at .
At , the atom holds, so , while . ThereforeLikewise and , soThe Kripke forcing relation for a disjunction requires one disjunct to be forced at the current world. Consequentlywhich is the required Kripke countermodel.
Past exam of the mathematics course of the University of Cambridge 2023 iii Paper 120 1 c Solution 2026-09-28
Take two worlds and let be forced only at . Neither world forces : at this follows from , while at the extension forces . Consequently every extension of that forces also forces vacuously, soBut . The implication clause therefore giveswhich is a finite Kripke countermodel and proves that the formula is not intuitionistically valid.
Past exam of the mathematics course of the University of Cambridge 2023 iii Paper 120 1 e Solution 2026-09-28
Suppose neither nor is provable. By the Kripke completeness theorem for intuitionistic propositional logic, there are rooted Kripke countermodels with roots and . Take their disjoint union and place a fresh world below every world in both components, forcing no propositional variables at beyond those required by persistence.
If , persistence would imply , a contradiction; similarly . Thus . By soundness, is not provable. Taking the contrapositive proves the disjunction property of intuitionistic propositional logic:
Past exam of the mathematics course of the University of Cambridge 2023 iii Paper 120 1 f Solution 2026-09-28
Assume that is not intuitionistically valid. Completeness gives a Kripke countermodel for . Apply filtration of a Kripke model through the finite set of subformulae of : two worlds are identified when they force the same subformulae, and the quotient order is induced by inclusion of those finite theories. The filtration lemma preserves the forcing of every subformula of , so the image of the original counterexample world still fails to force . There are at most quotient worlds when has distinct subformulae. Hence the quotient is a finite countermodel.
This proves the Finite model property of intuitionistic propositional logic. Its contrapositive says that a proposition forced by every finite intuitionistic Kripke model is intuitionistically valid.