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

A complete theory is $\kappa$-categorical when it has a model with underlying cardinality $\kappa$ and any two of its models of that cardinality are isomorphic structures. Thus categoricity means uniqueness up to isomorphism at the specified cardinal, not a unique underlying set or a unique isomorphism.

For the infinite cardinals relevant here, the existence clause is automatic from the stated infinite model and the Löwenheim-Skolem theorem. One may equivalently require exactly one isomorphism class of models of size $\kappa$.

An $n$-type over the empty set is a set $p(x_1,\dots ,x_n)$ of formulas of the language, with no additional parameters, jointly consistent with $T$. Equivalently every finite set is simultaneously satisfiable with $T$. A complete type decides every formula in these variables: for each $\phi$, exactly one of $\phi$ and $\neg \phi$ belongs to $p$.

A principal type has an isolating formula $\theta (x)$ consistent with $T$, such that $T\models \forall x(\theta (x)\to \phi (x))$ for every $\phi \in p$. For a complete type this is an isolated type; its isolator determines the entire type. A principal partial type may be weaker than a complete type, so its isolator need not decide all formulas.

A tuple $a\in A^n$ realizes $p$ if $\mathcal{A}\models \phi (a)$ for every formula in $p$. The model omits $p$ if it contains no such tuple. Thus omission is a simultaneous failure of realizing the whole type, even though each finite fragment can be realized.

Let $\theta (x)$ isolate the principal type. Consistency with $T$ means $T\cup \{\exists x\theta (x)\}$ is satisfiable. Because $T$ is a complete theory, it must imply $\exists x\theta (x)$; the alternative would make that extension inconsistent.

Therefore every model of $T$ has a tuple $a$ satisfying $\theta$. Each implication $T\models \theta \to \phi$ then makes $a$ satisfy every member of the type. HenceCompleteness is what turns possible realization of the isolating formula into realization in every model.

Add constants $c_1,\dots ,c_n$ and form $T\cup \{\phi (c):\phi \in p\}$. Every finite set has a model by consistency of the type. The compactness theorem gives a model $\mathcal{M}$ realizing the whole expanded theory, so $c^{\mathcal{M}}$ realizes $p$.

Apply the downward Löwenheim-Skolem theorem to the countable expanded language, retaining these finitely many named elements. The resulting countable elementary substructure still satisfies every formula of $p$ at the same tuple. Its reduct to the original language is a countable model of $T$ realizing $p$. Since $T$ has no finite models, this model is countably infinite.

The countable omitting types theorem says that for a consistent theory in a countable language and countably many nonprincipal types of finite arities, there is a countable model omitting all those types. In particular a nonisolated complete type of $T$ can be omitted in a countable model.

Interpret “definable” here as without parameters. If parameters were allowed freely, every infinite structure would have infinitely many definable singleton sets, and the claimed implication would be false even for a dense linear order without endpoints.

Infinitely many distinct parameter-free definable subsets of $A^n$ imply infinitely many complete $n$-types: if there were only $r$ such types, each formula would select a subset of those $r$ types, giving at most $2^r$ distinct definable subsets. There must also be a nonisolated complete type. To see this, suppose each complete type $p$ had an isolator ${\theta }_p$. The family of their basic open sets covers the type space. Its compactness theorem gives a finite subcover, which would account for only finitely many complete types, a contradiction. Equivalently apply logical compactness theorem to $T\cup \{\neg {\theta }_p(c):p\text{ complete}\}$.

Choose a nonisolated type $p$. The omitting types theorem gives a countable model omitting it, while part (d) gives a countable model realizing it. An isomorphism of structures preserves realization of parameter-free types, so these models are not isomorphic. Thus $\boxed{T\text{ is not }{\aleph }_0\text{-categorical}}$.

No. In the standard successor structure, every element other than the named zero has a predecessor:The proposed structure fails this first-order sentence at the integer $-1$. Its nonnegative elements map to positive elements, while every negative element maps to an integer at most $-2$; hence no element maps to $-1$. This gives a direct first-order distinction, without treating the negative branch as a two-sided successor chain.

Take the standard successor structure and its disjoint union with one two-sided integer successor chain:Both interpret the named zero in the natural-number component. The classification of models of the successor theory describes every model as this distinguished one-sided chain together with an arbitrary collection of two-sided chains. Its axioms are injectivity of $s$, zero outside its range, a predecessor for every nonzero element, and absence of finite cycles. These axioms are complete; equivalently the theory has the successor quantifier-elimination property explained in the concept proposal.

Consequently both displayed structures are models of the standard complete theory. They are not isomorphic: any isomorphism must fix zero and hence every element $s^n(0)$. The first structure has no other elements; the second has the entire extra integer chain. Being in that additional component is an isomorphism invariant even though being outside all standard iterates of zero is not expressible by one first-order formula.

For each natural number $n$, the formula $x=s^n(0)$ defines the singleton $\{n\}$ in the standard successor structure. These are pairwise distinct parameter-free definable subsets. ThereforeIn particular the criterion in part (e) applies already at arity one.

Consider the partial typeEach finite fragment is realized by a sufficiently large standard natural number, so it is consistent. It is omitted in the standard successor structure, since each of its elements equals one of the named iterates.

There is exactly one complete type extending this partial type. By classification of models of the successor theory and its quantifier-elimination property, a parameter-free one-variable formula is equivalent to a Boolean combination of finitely many equalities $x=s^n(0)$ and sentences whose truth is fixed by the theory. For a point on an extra integer chain every displayed equality is false, so all such points have the same complete type. Thusis the required omitted complete type. More formally take all formulas true at such a point; $p_{\infty }$ axiomatizes that type modulo the theory, and its deductive closure is complete.

The distinguished chain generated by zero is countable, and every other component in the classification of models of the successor theory is a countable copy of the integer successor chain. A model of cardinality ${\aleph }_1$ therefore has exactly ${\aleph }_1$ additional components: a finite or countable collection would be countable, while the union of $\kappa$ countable components has size $\max (\kappa ,{\aleph }_0)$.

Given two such models, match their zero chains in the forced way and choose a bijection between their additional components. On each component choose an origin and match corresponding integer iterates; this commutes with successor. The union of these maps is an isomorphism of structures. Existence is given by a disjoint union with ${\aleph }_1$ integer chains. HenceThe same argument works at every uncountable cardinal. Countable models can still differ by the number of extra components, as part (ii) shows.