Past exam of the mathematics course of the University of Cambridge / 2007 / ii / Paper 2 / 16G / Solution

A deduction from premises $\Gamma$ in propositional logic is a finite sequence of formulas, each an allowed logical axiom instance, a member of $\Gamma$, or obtained from earlier formulas by an inference rule, such as modus ponens. For example a Hilbert system can use the schemas $p\to (q\to p)$, $[p\to (q\to r)]\to [(p\to q)\to (p\to r)]$, and $(\neg q\to \neg p)\to (p\to q)$, with modus ponens as its rule. Its last formula is the conclusion. A finite deduction uses only finitely many premises. The completeness theorem for propositional logic says $\Gamma \models v$ implies $\Gamma ⊢v$; together with soundness, syntactic consistency is equivalent to existence of a satisfying valuation.

For compactness, if $\Gamma$ had no model, completeness would give a deduction of a contradiction. That deduction uses a finite subset of $\Gamma$, which therefore also has no model. Contrapositively, if every finite subset has a model, so does $\Gamma$.

Fix the given valuation on $Q$ and let $L_v$ be its collection of true literals. Suppose $\{s\}\cup L_v$ were inconsistent. A finite subset of its literals, with conjunction $\ell \in L(Q)$, would satisfy $s⊢\neg \ell$ by the deduction theorem and classical logic. But $\neg \ell \in U$ whereas the given valuation makes $\ell$ true, contradicting that it satisfies all of $U$. Hence $\{s\}\cup L_v$ is consistent.

If $U\cup \{\neg t\}$ had a model, restrict that valuation to $Q$ and apply the preceding consistency result. Completeness supplies an extension to $P\cup Q$ making $s$ true and preserving those $Q$ values. Combine its $P$ values with the original model's $Q\cup R$ values. Disjointness of $P,Q,R$ makes this a well-defined valuation satisfying $s$ and $\neg t$, contradicting soundness of $s⊢t$. Thus $U\cup \{\neg t\}$ is inconsistent.

Compactness now supplies $u_1,\dots ,u_k\in U$ with $u_1,\dots ,u_k⊢t$. Put $u={\bigwedge }_j{u}_j$. ThenThis proves propositional interpolation. The empty conjunction is the truth constant; if the language omits truth and falsehood symbols, use an equivalent tautology when $Q$ is nonempty, or adjoin those constants for the empty-common-language case.