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

A prime model of a complete theory $T$ is a model $M\models T$ for which there is an elementary embedding $M\to N$ into every model $N\models T$.

An atomic model of $T$ is a model $M\models T$ such that the complete type $\mathrm{tp}(\bar{a}/\varnothing )$ of every finite tuple $\bar{a}\in M$ is an isolated type.

Enumerate the countable atomic model as $M=\{a_0,a_1,\dots \}$ and fix any $N\models T$. We recursively construct finite partial elementary maps $f_n$ from the first $n$ elements of $M$ into $N$.

Suppose $f_n(\bar{a})=\bar{b}$. Since $M$ is atomic, choose a formula $\theta (\bar{x},y)$ isolating $\mathrm{tp}(\bar{a},a_n)$. Its existential consequence $\exists y\theta (\bar{x},y)$ belongs to $\mathrm{tp}(\bar{a})$, so partial elementarity givesChoose a witness $b_n$. Because $\theta$ isolates the complete joint type, extending $f_n$ by $a_n\mapsto b_n$ remains partial elementary. The union of the recursive maps is an elementary embedding $M\to N$. Thus every countable atomic model is a prime model, proving the countable atomic model is prime result.

The Fundamental theorem of stability says that, for a complete theory with infinite models, the following are equivalent:

Let $\lambda =|T|$ and choose an infinite cardinal $\kappa$ satisfying ${\kappa }^{\lambda }=\kappa$, for example $\kappa =2^{\lambda }$. Take $M\models T$ of cardinality $\kappa$. By assumption, every $p\in S_1(M)$ is definable.

For each parameter-free formula scheme $\phi (x;y)$, the definition $d_p\phi (y)$ is a formula with finitely many parameters from $M$. There are at most $\kappa$ such formulas. A definable type is completely determined by choosing one definition for each of the at most $\lambda$ formula schemes, soThe same count applies to every model of cardinality $\kappa$, and therefore $T$ is $\kappa$-stable. Hence $T$ is a stable theory.

Choose $b\in N^m$ and an $L$-formula $\phi (\bar{x};y)$ such thatLet $p(y)=\mathrm{tp}(b/M)$. Stability and the Fundamental theorem of stability make this a definable type. Apply its definition to the formula $\psi (y;\bar{x})=\phi (\bar{x};y)$. There is an $M$-formula $d_p\psi (\bar{x})$ such that, for every $\bar{a}\in M^n$,Thus $d_p\psi$ defines $X\cap M^n$ in $M$, which is the stable trace of a definable set property.

Every model of $T$ becomes an $L_0$-structure by forgetting the symbols outside $L_0$, so $T_0$ has an infinite model. If $\phi$ is an $L_0$-sentence, completeness of $T$ gives either $T\models \phi$ or $T\models \neg \phi$. Accordingly either $\phi \in T_0$ or $\neg \phi \in T_0$. The two cannot both occur because $T$ is consistent. Therefore $T_0$ is a complete $L_0$-theory with infinite models.

Yes. By the Ryll-Nardzewski theorem, aleph-zero-categoricity of $T$ says that, for every $n$, only finitely many $L$-formulas in $n$ variables exist modulo equivalence over $T$. The $L_0$-formulas form a subcollection. Moreover, two $L_0$-formulas are equivalent modulo $T_0$ exactly when their universal equivalence sentence belongs to $T_0$, equivalently when it follows from $T$. Thus there are only finitely many $L_0$-formulas modulo $T_0$ in each arity. Applying Ryll-Nardzewski again proves that $T_0$ is aleph-zero-categorical. This is the reduct of an aleph-zero-categorical theory property.

No. Let $L$ have unary predicates $P,Q$ and a unary function $f$. Let $T$ say that $P$ and $Q$ partition the universe into two infinite sets and that $f$ is an involution mapping $P$ bijectively onto $Q$. This is a complete theory. In every infinite cardinal $\kappa$, a model of total size $\kappa$ has $|P|=|Q|=\kappa$, and any two such bijections are isomorphic. Hence $T$ is $\kappa$-categorical for every infinite $\kappa$.

Take $L_0=\{P,Q\}$. The reduct theory merely says that $P$ and $Q$ are two infinite parts. At any uncountable $\kappa$, it has one model with $|P|={\aleph }_0$ and $|Q|=\kappa$, and another with $|P|=|Q|=\kappa$. They are not isomorphic. Therefore $T_0$ is not $\kappa$-categorical, giving the reduct need not preserve uncountable categoricity counterexample.

A theory $T$ has quantifier elimination when every first-order formula is equivalent modulo $T$ to a quantifier-free formula with the same free variables.

Use the partial-isomorphism criterion for quantifier elimination: it is enough that every finite partial embedding between sufficiently saturated models have the one-point extension property.

Let $f:A\to B$ be a finite partial order isomorphism between models $M,N$ of the theory of dense linear order without endpoints, and take $c\in M\setminus A$. The finite set $A$ partitions $M$ into the points of $A$, the intervals between consecutive elements, and the two outer rays. The order relations between $c$ and $A$ identify one of those intervals or rays. The image $B$ determines the corresponding interval or ray in $N$. Density supplies a point there when it is bounded, and the absence of endpoints supplies one in either outer ray. Choose such a point $d$; then $f\cup \{(c,d)\}$ remains a partial order isomorphism.

The same argument works in the reverse direction. A back-and-forth method therefore extends finite partial order isomorphisms, making them partial elementary. The criterion proves quantifier elimination for dense linear orders without endpoints.