Disjunction and existence properties 2026-10-14
A theory has the disjunction property when provability of a closed disjunction implies provability of one disjunct. It has the existence property when a provable existential sentence has a witness whose substitution is provably valid. These are distinct constructive properties; disjunction property of intuitionistic propositional logic is one instance of the former.
Past exam of the mathematics course of the University of Cambridge 2023 iii Paper 120 1 e Solution Created 2026-09-28 Updated 2026-10-03
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: