Past exam of the logic and set theory course of the University of Oxford / 2007 / A / 4

Soundness states that formal derivability implies semantic entailment:For first-order sentences this means that every first-order structure satisfying all assumptions also satisfies every first-order sentence formally derived from them. In the logical formula version one uses the usual restrictions on generalization from assumptions with free variables.

Strong completeness states the converse:Equivalently, every syntactically consistent set of first-order sentences has a first-order model. Equality is interpreted as actual identity, and its usual logical axioms and substitution rules are part of the standard calculus. Both assertions hold for arbitrary sets of assumptions, rather than only finite sets.

The compactness theorem says that a set $T$ of first-order sentences has a first-order model if and only if every finite subset of $T$ has a first-order model. One direction follows by using the same first-order model for each subset.

For the nontrivial direction suppose every finite subset has a first-order model, but $T$ has none. Semantically $T\models \perp$, so completeness gives a formal logical derivation $T⊢\perp$. A formal logical derivation is finite and uses only finitely many assumptions, say $T_0\subseteq T$. Thus $T_0⊢\perp$. Soundness would make $T_0$ unsatisfiable, contradicting the hypothesis. Here $\perp$ can be any fixed contradictory first-order sentence, such as $\exists x(x\ne x)$, if it is not a primitive logical symbol. Therefore finite satisfiability implies satisfiability.

Take $S_1$ to consist of the three usual first-order sentencesThese assert reflexivity, symmetry and transitivity and therefore define exactly the equivalence relations.

For $S_2$, adjoin to $S_1$ the single first-order sentenceIts witness $y$ gives a second member of each class, while its final universal clause excludes all others. Hence every class has exactly two members, and conversely such a relation satisfies it. This remains a finite set of first-order sentences.

For each positive integer $n$, writeThenEvery class in a first-order model has at least $n$ elements for every $n$, so cannot be finite. Conversely every infinite equivalence class supplies each finite collection of distinct witnesses. The displayed infinite scheme therefore has exactly the requested first-order models.

Suppose such a first-order theory $S$ existed. Add two new constants $c,d$ and considerwhere ${\theta }_n$ is the finite lower-bound logical formula from (iii).

Every finite subset of $T$ has a first-order model. Choose a first-order structure with exactly two equivalence classes: one countably infinite, and one finite of size at least the largest bound appearing in that subset. Interpret $c$ in the infinite class and $d$ in the finite class. The first-order structure satisfies all of $S$, by its assumed characterization, and meets the finite demands on both named classes.

Compactness theorem in the language with the two new constants gives a first-order model of all of $T$. Its classes of $c$ and $d$ are distinct and both infinite. Its reduct still satisfies $S$, which is impossible if $S$ characterizes exactly one infinite class. HenceThe finite approximations work because any finite list of lower bounds permits the second class to remain finite; the entire list prevents that escape.