Past exam of the model theory and Gödel's incompleteness theorems course of the University of Oxford / 2008 / B / 8

The Ryll-Nardzewski theorem says that for a complete theory $T$ in a countable first-order language with infinite first-order models, the following are equivalent: $T$ is ${\aleph }_0$-categorical; for every positive integer $n$, the set $S_n(T)$ of complete parameter-free $n$-types is finite; every such finite-arity complete type is isolated by a logical formula. The countable-language hypothesis and the requirement for every finite arity are important.

The omitting types theorem says that, for a first-order consistent complete theory in a countable first-order language, a countable family of nonprincipal partial types in finite tuples of logical variables can all be omitted in a countable first-order model. Here nonprincipal means that no logical formula first-order consistent with the first-order theory implies every logical formula of the partial type. Omission means that no tuple in the constructed first-order model satisfies all logical formulas of that partial type. The complete one-type version is the special case of one partial type in one logical variable.

Use the complete theory of dense linear orders without endpoints in the first-order language $\{<\}$. It eliminates quantifiers: existential conditions on one new point reduce to finitely many logical equality constraints and interval bounds, and density and absence of endpoints decide whether a suitable point exists. Its countably infinite first-order models are all isomorphic to the rational order by the usual back-and-forth method, extending finite order-preserving maps alternately along enumerations of the two first-order models. Thus it is ${\aleph }_0$-categorical.

To distinguish first-order models of size ${\aleph }_1$, letwith ordered sums. Both are dense without endpoints and have cardinality ${\aleph }_1$. The first has cofinality ${\aleph }_1$: countably many points lie in a bounded set of block indices and cannot be cofinal. The second has cofinality ${\aleph }_0$, supplied by its final rational block. Cofinality of a linear order is preserved by isomorphism, so they are not isomorphic. ThereforeFor Ryll-Nardzewski, its $n$-types are precisely the finitely many equality-and-order patterns on $n$ coordinates. Each is isolated by the conjunction specifying that pattern, agreeing with the theorem's prediction.

Use $AC{F}_0$, the complete theory of algebraically closed fields of characteristic zero. Its quantifier elimination is a standard characterization of this complete theory. Algebraically closed fields of a fixed characteristic are classified up to isomorphism by transcendence degree over their prime field.

For such a field $K$,when the transcendence degree is infinite, while finite transcendence degree also gives a countable field. This follows by counting rational functions in a transcendence basis and then algebraic elements over that field. Thus every first-order model of cardinality ${\aleph }_1$ has transcendence degree ${\aleph }_1$, and the classification gives a unique such first-order model.

On the other hand $\overline{\mathbb{Q}}$ and an algebraic closure of $\mathbb{Q}(t)$ are countably infinite first-order models with transcendence degrees zero and one, so are not isomorphic. HenceThe transcendental complete one-type consists of $f(x)\ne 0$ for every nonzero polynomial over $\mathbb{Q}$. Quantifier elimination makes it complete. It is nonprincipal: any parameter-free one-variable logical formula containing a transcendental element defines a cofinite set, hence contains algebraic elements as well and cannot isolate this partial type. The first-order model $\overline{\mathbb{Q}}$ omits it, concretely illustrating the omitting types theorem. The existence of infinitely many algebraic complete one-types, together with this nonprincipal complete type, also agrees with the failure of the Ryll-Nardzewski finiteness condition.

Take the first-order theory of an infinite set in the first-order language of logical equality alone, with an axiom asserting at least $n$ distinct elements for each positive integer $n$. It is complete and eliminates quantifiers: a new logical variable either equals a specified old logical variable or is required to avoid only finitely many existing values, which an infinite domain permits.

For every infinite cardinal $\kappa$, any two first-order models of size $\kappa$ are isomorphic because every bijection between their underlying sets preserves logical equality, the whole first-order language. ThusIts complete $n$-types record only the partition of coordinate indices according to logical equality. There are finitely many such partitions, and each is isolated by the corresponding logical equalities and inequalities. Ryll-Nardzewski therefore recovers countable categoricity; there are no nonprincipal complete finite-arity partial types to omit in this example.

The same complete theory $T_{\infty }$ of an infinite pure set provides this property directly. For $n$ logical variables, each complete type specifies exactly which logical variables are equal. First-order consistency requires an equivalence relation on the finite index set, and infinitude ensures every such partition is realizable. Hencewhere $B_n$ is the $n$th Bell number, counting partitions of an $n$-element set. For example the first values are $B_1=1$, $B_2=2$ and $B_3=5$. The isolating conjunction lists logical equality within blocks and inequality between blocks. This explicitly verifies the hypothesis which Ryll-Nardzewski identifies with ${\aleph }_0$-categoricity.

Use the first-order theory $T_{\mathbb{Z}}$ of a bijection $f$ with named inverse $g$ and no finite cycles. Its axioms areEvery first-order model is a disjoint union of free two-sided integer orbits. Write $f^k$ for positive powers of $f$ and for powers of $g$ when $k$ is negative.

This first-order theory is complete and eliminates quantifiers. Every first-order term reduces to $f^k(x_i)$, and atomic logical formulas reduce to statements $x_j=f^k(x_i)$. To eliminate an existential logical variable in a conjunction of literals, first remove self-equalities using the no-finite-cycle axioms. If an equation fixes that logical variable as an integer translate of another logical variable, substitute that value. If no such equation remains, only finitely many points are excluded by the remaining inequalities, so some value exists in the infinite domain. Apply this to disjunctive normal form and then induct on logical formulas. The resulting parameter-free first-order sentences are decided, proving completeness.

For each fixed finite $n$, a complete type records a partition of the logical variables into common orbits and finitely many integer offsets within each block. There are countably many possibilities. Countable first-order models with one orbit and with two orbits are not isomorphic, so the first-order theory is not ${\aleph }_0$-categorical.

Thus this example has the source's explicitly defined countable-type property. In fact it also satisfies ordinary omega-stability: over a countable parameter set, an element is either a specified integer translate of a parameter, giving countably many possibilities, or lies in an entirely new orbit, giving one further complete one-type. The same finite-orbit-pattern description handles finite tuples. ThereforeThe source prints the label “$0$-stable”; the construction meets its stated definition as well as the usual stronger omega-stability condition. The difference between countably many and finitely many partial types is exactly why Ryll-Nardzewski does not yield categoricity here.

Reuse the complete free-bijection theory from part (e). Quantifier elimination shows that every one-variable atomic statement is already decided by the no-finite-cycle axioms. Thus there is exactly one complete one-type, isolated by $x=x$.

For two logical variables, each integer $k$ gives a different complete type isolated byThere is also the complete typesaying that the two elements lie in different orbits. These exhaust the possibilities by quantifier elimination. In particularThe last complete type is a nonprincipal complete type. Any logical formula uses only finitely many integer offsets after quantifier elimination; a pair in a single orbit with a sufficiently different offset agrees with a different-orbit pair on those tests. Hence no single logical formula can isolate $p_{\infty }$.

The one-orbit first-order model $(\mathbb{Z},f(n)=n+1,g(n)=n-1)$ omits $p_{\infty }$, while a two-orbit first-order model realizes it. This illustrates the omitting types theorem and shows concretely why finitely many complete one-types alone cannot replace the all-arities condition in Ryll-Nardzewski.