Past exam of the computer science course of the University of Oxford / 2015 / Logic and proof / 1 / f / Solution

Let $S=\{F_i:i\ge 1\}$. Every finite subset of $S$ is satisfiable: if $F_N$ has the largest index occurring, the successive semantic entailments imply $F_N\models F_i$ for every earlier index, so any Boolean valuation satisfying $F_N$ satisfies that finite subset. The propositional compactness theorem therefore also shows that $S$ itself is satisfiable.

Suppose that $G$ had exactly the common models of $S$. Then $S\models G$, and hence $S\cup \{\neg G\}$ is unsatisfiable. By the propositional compactness theorem, finitely many $F_i$ together with $\neg G$ are already unsatisfiable. Enlarge the finite list if necessary so it is nonempty, and let $N$ be its greatest index. We obtainOn the other hand, the asserted equality of model classes gives $G\models F_{N+1}$. Transitivity of semantic entailment would yieldcontradicting the strictness assumption at index $N$. ThusThe obstruction is the finite character of propositional formulas: a single consequence of an infinite set already follows from finitely many premises, whereas this chain continues to impose strictly stronger requirements forever.