Past exam of the model theory course of the University of Oxford / 2011 / 1

Here parameter-free definability is intended: parameters are not silently added to the first-order language. A subset $D\subseteq A^n$ is a definable set when some $L$-first-order formula $\phi (x_1,\dots ,x_n)$ satisfiesA definable function is one whose graph is a definable set. Thus $f:A^n\to A$ is definable when an $L$-formula $\theta (\mathbf{x},y)$ satisfiesIn particular $\mathcal{A}\models \forall \mathbf{x}\exists !y\theta (\mathbf{x},y)$. Definability over a parameter set $B$ permits parameters from $B$ in these first-order formulas, equivalently new constants naming those parameters. That is a different requirement: allowing a parameter naming an element would immediately define its singleton.

Yes. In the additive first-order structure, the quantifier-free formulaholds exactly at zero, because cancellation in the additive group gives $x=0$. This first-order formula uses only the permitted function symbol and equality; it does not require a constant symbol for zero.

No. The map $s(x)=-x$ is an automorphism of a first-order structure for the additive integers, but it sends one to minus one. By automorphism invariance of parameter-free definability, every parameter-free definable singleton is fixed by every structure automorphism. The singleton containing one is not fixed, so it is not definable.

No. Definability of a function means definability of its graph. The same additive structure automorphism $s(x)=-x$ would have to preserve the graph of multiplication. It sends the graph point $(1,1,1)$ to $(-1,-1,-1)$, which is not a multiplication-graph point because $(-1)(-1)=1\ne -1$. This contradicts automorphism invariance of parameter-free definability.

No. Interpreting the printed ${\mathbb{Z}}^{⩾}$ as the nonnegative integers, negation is an additive structure automorphism carrying the positive integer one outside that set. The set is therefore not invariant under structure automorphisms and cannot have parameter-free definability. The same argument would apply if the notation were taken to mean the strictly positive integers.

Yes. Zero is the unique absorbing element of the multiplicative first-order structure. It is defined byZero satisfies this universal formula. Conversely, substituting the actual integer zero for $y$ in the semantic verification forces $x=0$. This use of zero in the verification does not insert a constant symbol into the first-order formula.

Yes. One is the unique identity element of multiplication, defined byThe integer one satisfies the first-order formula, and testing at the actual integer one forces any satisfying $x$ to equal one. Thus this is a parameter-free universal formula even though the language has no named identity.

No. Use the prime-sign automorphism of the multiplicative integerswhere $v_2(n)$ is the exponent of two in $|n|$, a P-adic valuation. For nonzero integers, $v_2(mn)=v_2(m)+v_2(n)$, so $s(mn)=s(m)s(n)$; the identity also holds when a factor is zero. The exponent of two is unchanged by changing the sign, hence $s(s(n))=n$. Thus $s$ is a multiplicative structure automorphism.

It fixes one and sends two to minus two. The addition-graph point $(1,1,2)$ is sent to $(1,1,-2)$, outside the graph of addition. By automorphism invariance of parameter-free definability, addition is not definable in the multiplicative reduct.

No. The prime-sign automorphism of the multiplicative integers from the preceding part sends the positive integer two to minus two. It therefore does not preserve the nonnegative integers, contradicting the necessary automorphism invariance of parameter-free definability. This also excludes definability of the strictly positive integers if that convention for the printed notation is used.

For the additive zero singleton, $x+x=x$ is already a quantifier-free formula, so it is also an existential formula and a universal formula with an empty quantifier block. If a nonempty block is required, add a dummy $\exists y$ or $\forall y$; first-order domains are nonempty.

For the two definable multiplicative singletons, existential formulas areIn the integers, the equation $x^2=x$ restricts $x$ to zero or one. In the first line, one never satisfies the inequality, whereas zero does with $y=1$. In the second, zero never satisfies it, whereas one does with $y=0$. The respective universal formulas are $\forall y(xy=x)$ and $\forall y(xy=y)$, as already verified.

Neither multiplicative singleton has a quantifier-free formula. In this constant-free, multiplication-only language, every term in the sole free variable $x$ is $x^k$ for a positive integer $k$. Every atomic formula $x^r=x^s$ is true at both zero and one. Every Boolean combination consequently has the same truth value at those two points, and cannot separate their singletons. This is the fact that zero and one have the same quantifier-free type in the multiplicative integers.

Thus additive zero admits all three forms; multiplicative zero and one admit existential and universal forms, but no quantifier-free form. All remaining cases were excluded from definability itself by structure automorphisms.

An aleph-zero-categorical theory has, up to isomorphism, exactly one first-order model of cardinality ${\aleph }_0$.

The Ryll-Nardzewski theorem says that, for a complete theory $T$ in a countable first-order language, with infinite first-order models, the following conditions are equivalent: $T$ is aleph-zero-categorical; for every positive integer $n$, its type space $S_n(T)$ of complete types over the empty set is finite; and, for every $n$, there are only finitely many $L$-formulas in $n$ free variables modulo equivalence over $T$. Here $\phi$ and $\psi$ are equivalent over $T$ when $T\models \forall \mathbf{x}(\phi \leftrightarrow \psi )$.

A partial type $p(\mathbf{x})$ is a set of $L$-first-order formulas in a fixed tuple $\mathbf{x}=(x_1,\dots ,x_n)$ jointly consistent with $T$. A complete type, the usual meaning of an $n$-type here, is maximal among such consistent sets: for each first-order formula $\phi (\mathbf{x})$ it contains exactly one of $\phi ,\neg \phi$.

Add new constants $\mathbf{c}$ and considerEvery finite subset is satisfiable by consistency of the type. The compactness theorem gives a first-order model of the full set. Its $L$-reduct is a first-order model of $T$, and the interpretations of $\mathbf{c}$ realize $p$. This proof applies to partial as well as complete types.

For a complete theory in a countable language, the types realized in every first-order model are exactly the isolated types. An isolated type has a consistent first-order formula $\theta \in p$ such that $T\models \forall \mathbf{x}(\theta \to \phi )$ for every $\phi \in p$. Completeness forces $T\models \exists \mathbf{x}\theta$, so every first-order model realizes $p$; the converse is the omitting types theorem. Countability is a hypothesis of that converse, not of the preceding compactness realization argument. For a partial type the corresponding criterion is an isolating consistent first-order formula, together with its existence in every first-order model; it need not itself belong to the partial type.

If $T$ is not complete, no one complete $n$-type can be realized in every first-order model of $T$: a complete type decides sentences, and two completions of $T$ disagree on some sentence. Thus the completeness and countability hypotheses must be retained when using the isolated-type characterization.

For the additive first-order structure, letIt defines $n\mathbb{Z}$. These sets are pairwise distinct: if $m>n>0$, the integer $n$ belongs to $n\mathbb{Z}$ but not to $m\mathbb{Z}$. Thus there are infinitely many inequivalent one-variable first-order formulas modulo the complete theory of the additive integers. The Ryll-Nardzewski theorem implies that first-order theory is not aleph-zero-categorical.

For the multiplicative first-order structure define divisibility by $d(y,x):=\exists z(yz=x)$. For $k\ge 1$, the first-order formulaasserts the existence of at least $2k$ distinct integer divisors. The integer $2^{k-1}$ has exactly $2k$ such divisors, namely $\pm 2^j$ for $0\le j\le k-1$, so it satisfies ${\psi }_k$ but not any ${\psi }_{\ell }$ with $\ell >k$. Again there are infinitely many inequivalent one-variable first-order formulas. The Ryll-Nardzewski theorem therefore implies the first-order theory of the multiplicative integers is not aleph-zero-categorical.