Past exam of the mathematics course of the University of Cambridge / 2020 / ii / Paper 2 / 16H / b

The Godel completeness theorem says that for every first-order theory $\Gamma$ and sentence $\phi$,Together with soundness, this is equivalence; it is also equivalent to saying that every syntactically consistent first-order theory has a model.

The compactness theorem states that a set $\Gamma$ of first-order sentences has a model if and only if every finite subset ${\Gamma }_0\subseteq \Gamma$ has a model. To deduce it, suppose every finite subset is satisfiable but $\Gamma$ is not. Then $\Gamma \models \perp$, so completeness gives a formal proof $\Gamma ⊢\perp$. A proof uses only finitely many assumptions, yielding some finite ${\Gamma }_0⊢\perp$, contrary to that subset's satisfiability.

Introduce a propositional variable $P_{x,i}$ for every $x\in X$ and $i\in \{1,\dots ,100\}$. Form a theory containing, for every $x$, clauses saying that exactly one ofis true, and, for every $y\in L_x$ and every $i$, the clauseEvery finite subset of these clauses mentions only finitely many elements, forming a finite set $Y\subset X$. The assumed coloring $f_Y$ gives that finite subset a model. The propositional compactness theorem, equivalently the propositional consequence of first-order compactness, therefore gives a model of all the clauses.

For each $x$, let $F(x)$ be the unique $i$ for which $P_{x,i}$ is true. The edge clauses ensure that $F(x)\ne F(y)$ whenever $y\in L_x$. Hencehas the required property.