Past exam of the mathematics course of the University of Cambridge / 2025 / iii / Paper 144 (Model Theory)

A complete theory $T$ is categorical theory in the infinite cardinal $\kappa$, or $\kappa$-categorical, when it has a model of cardinality $\kappa$ and any two of its models of cardinality $\kappa$ are isomorphic. Equivalently, $T$ has exactly one model of cardinality $\kappa$ up to isomorphism.

Solved by gpt-5.6-sol high.

The theory $\mathrm{Th}(\mathbb{Z},+,0)$ is not aleph-zero-categorical. Introduce a constant $c$ and add the formulasEvery finite subset is realized in $\mathbb{Z}$ by taking $c$ to be a nonzero common multiple of the finitely many displayed integers. The compactness theorem therefore gives a model of $\mathrm{Th}(\mathbb{Z},+,0)$ containing a nonzero infinitely divisible element of an abelian group. The Downward Lowenheim-Skolem theorem gives such a model that is countable.

No nonzero integer is divisible by every positive integer, so this countable model is not isomorphic to $\mathbb{Z}$. This is the nonstandard model of the additive integers obstruction to categoricity.

Solved by gpt-5.6-sol high.

The group $B$ is a vector space over a finite field, namely ${\mathbb{F}}_2$, because every element has order at most two. It is infinite-dimensional. The complete first-order theory of infinite-dimensional ${\mathbb{F}}_2$-vector spaces says, for each $n$, that there are $n$ linearly independent vectors; the usual elimination argument for vector spaces shows that all infinite-dimensional ${\mathbb{F}}_2$-vector spaces are elementarily equivalent.

Every countably infinite model of this theory has dimension ${\aleph }_0$: finite dimension would make it finite, while uncountable dimension would make its underlying set uncountable. Any two vector spaces over the same field with the same dimension are isomorphic. Therefore $\mathrm{Th}(B,+,0)$ is aleph-zero-categorical, as recorded by the aleph-zero-categoricity of an infinite-dimensional vector space over a finite field.

Solved by gpt-5.6-sol high.

A filter on a set $\mathcal{U}$ on $\mathbb{N}$ is a nonempty family of subsets of $\mathbb{N}$ such that:

These conditions imply $\mathbb{N}\in \mathcal{U}$.

Solved by gpt-5.6-sol high.

An ultrafilter is a proper filter maximal under inclusion. Equivalently, for every $A\subseteq \mathbb{N}$, exactly one of $A$ and $\mathbb{N}\setminus A$ belongs to $\mathcal{U}$.

Solved by gpt-5.6-sol high.

If $\mathcal{U}$ contains no finite set, then every cofinite set belongs to it: for a finite $F$, one has $F\notin \mathcal{U}$, so the ultrafilter alternative forces $\mathbb{N}\setminus F\in \mathcal{U}$. Thus $\mathcal{U}$ contains the cofinite filter.

Solved by gpt-5.6-sol high.

Suppose instead that a finite set $F$ belongs to $\mathcal{U}$. If none of its singleton subsets belonged to $\mathcal{U}$, all their complements would belong to $\mathcal{U}$, and intersecting those complements with $F$ would put the empty set in $\mathcal{U}$. Hence $\{n\}\in \mathcal{U}$ for some $n\in F$.

Upward closure then puts every subset containing $n$ in $\mathcal{U}$, while no subset omitting $n$ can belong to it. Thereforethe principal ultrafilter at $n$. Together with part i, this proves the dichotomy.

Solved by gpt-5.6-sol high.

Yes. Choose the principal ultrafilter at any $j\ge 2$. Evaluation at the $j$th coordinate giveswhich is a finite cyclic group of order $j$.

Solved by gpt-5.6-sol high.

No. Suppose a formula with parameters defined a function $f:\mathcal{C}\to \mathcal{C}$ that was surjective and not injective. The assertions that the formula defines a function, that the function is surjective, and that it is not injective are all first-order statements about that formula and those parameters. By Łoś theorem, they would hold simultaneously in ${\mathcal{C}}_i$ for $\mathcal{U}$-almost every $i$.

Every surjective self-map of a finite set is injective, so no finite factor can satisfy those statements. This contradiction shows that the ultraproduct has no such definable function.

Solved by gpt-5.6-sol high.

Yes. Choose a nonprincipal ultrafilter on $\mathbb{N}$ and letFor each fixed positive integer $n$, the equality $na=0$ holds in the $i$th factor exactly when $i$ divides $n$. Only finitely many positive integers divide $n$, so the cofinite set of indices for which $na\ne 0$ belongs to $\mathcal{U}$. Łoś theorem gives $na\ne 0$ in $\mathcal{C}$ for every $n>0$. Thus $a$ has infinite order of a group element.

Solved by gpt-5.6-sol high.

Use the finite-partial-isomorphism criterion for quantifier elimination. Let $M,N\models \mathrm{DLO}$ and let $h:A\to B$ be an isomorphism between finite suborders. For $a\in M\setminus A$, its position relative to $A$ is one of the finitely many open intervals determined by $A$, or one of the two exterior rays. The corresponding interval or ray determined by $B$ is nonempty because the orders are dense and have no endpoints. Choose $b$ there. Then $h\cup \{(a,b)\}$ remains a partial order isomorphism.

The same argument extends in the other direction. The back-and-forth method criterion therefore applies, proving quantifier elimination for dense linear orders without endpoints. Hence DLO eliminates quantifiers.

Solved by gpt-5.6-sol high.

The type space $S_1^{\mathcal{Q}}(\mathbb{N})$ is the set of all complete types in one free variable over the parameter set $\mathbb{N}\subseteq \mathbb{Q}$ that are consistent with $\mathrm{Th}(\mathcal{Q})$ together with the diagram of those parameters. Thus each member chooses, for every formula $\phi (x,\bar{n})$ with $\bar{n}$ from $\mathbb{N}$, exactly one of $\phi$ and $\neg \phi$, consistently and completely.

Solved by gpt-5.6-sol high.

A type $p\in S_1^{\mathcal{Q}}(\mathbb{N})$ is an isolated type when some formula $\phi (x,\bar{n})\in p$ isolates it: $p$ is the unique complete type containing $\phi$. Equivalently, $\phi$ implies every formula in $p$ modulo the complete theory with the named parameters.

Solved by gpt-5.6-sol high.

By quantifier elimination, a one-type is determined entirely by the position of $x$ relative to the natural-number parameters. Assuming $\mathbb{N}=\{0,1,2,\dots \}$, the isolated types and isolating formulas are:

Each formula fixes every comparison of $x$ with every natural number, so it determines a complete type. These are precisely the isolated members of the one-types over the natural numbers in the rational order.

Solved by gpt-5.6-sol high.

There is exactly one non-isolated type:It is consistent by the compactness theorem, since every finite subset is realized by a sufficiently large rational number. It is complete by quantifier elimination, because it decides every comparison with a parameter from $\mathbb{N}$.

No formula isolates it. Any formula belongs to $p_{\infty }$ only through finitely many natural-number parameters; after quantifier elimination it holds throughout some final ray. It is consequently also satisfied by a sufficiently large natural number, whose equality type differs from $p_{\infty }$. Thus $p_{\infty }$ is non-isolated, and the list in part i exhausts all other cuts of $\mathbb{N}$.

Solved by gpt-5.6-sol high.