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

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.