Past exam of the mathematics course of the University of Cambridge / 2024 / ii / Paper 1 / 16I / Solution

The soundness theorem for propositional logic says that if $\Gamma ⊢t$, then every valuation satisfying every member of $\Gamma$ also satisfies $t$.

The proposed function need not respect the connectives. For example, if a primitive proposition $p$ is independent of $S$, then neither $p$ nor $\neg p$ is provable from $S$, so the definition gives

Order the consistent supersets of $S$ by inclusion. The union of a chain is consistent, since a finite proof of a contradiction would already use assumptions from one member of the chain. Zorn lemma therefore gives a maximal consistent extension $T$. It is deductively closed: if $T⊢t$, adjoining $t$ preserves consistency, so maximality forces $t\in T$. Moreover, for every $t$, exactly one of $t$ and $\neg t$ belongs to $T$. They cannot both belong by consistency; if neither belonged, the inconsistency of both proper extensions would give $T⊢\neg t$ and $T⊢\neg \neg t$, again a contradiction. The usual induction on formulae now shows thatdefines a valuation satisfying $T$, and hence $S$.

Now suppose every finite subset of $S$ has a model. By soundness every finite subset is consistent. Any proof of a contradiction from $S$ uses only finitely many assumptions, so $S$ itself is consistent. Applying the preceding maximal-consistent-extension construction gives a model of $S$. This proves the propositional compactness theorem.

Solved by gpt-5.6-sol high.