Past exam of the mathematics course of the University of Cambridge / 2024 / ii / Paper 1 / 16I (Logic and Set Theory)

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.

For distinct $x,x^{\prime }\in X$ and distinct $y,y^{\prime }\in Y$, take all clausesThe first family says that each $x$ is paired with at most one $y$; the second says that each $y$ is paired with at most one $x$. There is no existence clause, so the domain may be any subset of $X$. Thus the relations $f_v$ are exactly the injective partial functions from $X$ to $Y$.

Start with the two families of uniqueness and injectivity clauses from part (i), and for every $x\in X$ add the finite clauseThis clause is a legitimate proposition because $A_x$ is finite and nonempty. It makes every $x$ have a value in $A_x$, while the earlier clauses make that value unique and make the resulting function injective. Conversely, every injection $g:X\to Y$ with $g(x)\in A_x$ satisfies all these clauses.

No such set of propositions exists. Suppose that $S$ had precisely the total injections as its models, fix $x_0\in X$, and adjointo $S$. Every finite subset of the enlarged theory has a model. Indeed, it excludes only finitely many possible values $F\subset Y$ for $x_0$. Starting with any injection $h:X\to Y$, either $h(x_0)\notin F$, or one may choose $x_1\ne x_0$ with $h(x_1)\notin F$ and swap the values of $x_0$ and $x_1$.

The propositional compactness theorem would therefore give a model of the whole enlarged theory. Its relation $f_v$ is a model of $S$ but has no value at $x_0$, contradicting the assumed description of the models of $S$. This is the compactness obstruction to expressing totality over an infinite codomain.