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.
Past exam of the mathematics course of the University of Cambridge 2026 iii Paper 120 1 e Solution Created 2026-09-24 Updated 2026-10-03
Assume . By Kripke completeness there is a rooted countermodel. Unravel it into a tree and retain only the subformulas of . Whenever a retained node fails an implication , retain one successor witnessing and the failure of . Along a branch, passing to a genuinely new witness strictly enlarges the finite theory of subformulas, so at most witness levels are needed. Identifying repeated equal theories and retaining at most one witness for each failed implication leaves at most representatives for each of the at most theories. The resulting pruned filtration has at most worlds and still refutes by the truth lemma.
Thus every underivable formula with subformulas has a countermodel of size at most . The contrapositive proves the claim and is the quantitative Finite model property of intuitionistic propositional logic.