This is a nice application of the omitting types theorem that characterises ${\aleph}_{0}$-categorical theories in countable languages $L$.

The main notion is that of a type. If $T$ is a set of $L$-sentences a type over $T$ $p\left(\stackrel{\_}{x}\right)$ is a set of $L$-formulas in some fixed finite tuple of free variables $\stackrel{\_}{x}$ such that $p\left(\stackrel{\_}{x}\right)$ is maximally consistent with $T$, i.e. for each finite subset $\left\{{\varphi}_{1}\left(\stackrel{\_}{x}\right),{\varphi}_{1}\left(\stackrel{\_}{x}\right),\dots ,{\varphi}_{1}\left(\stackrel{\_}{x}\right)\right\}$ of $p\left(\stackrel{\_}{x}\right)$ there is a model of $T\cup \left\{\exists \stackrel{\_}{x}\u200a\left({\varphi}_{1}\left(\stackrel{\_}{x}\right)\wedge {\varphi}_{1}\left(\stackrel{\_}{x}\right)\wedge \dots \wedge {\varphi}_{1}\left(\stackrel{\_}{x}\right)\right)\right\}$, and $p\left(\stackrel{\_}{x}\right)$ is maximal such that this happens.

For the rest of this worksheet, fix a countable first-order language $L$ and a complete $L$-theory $T$ which has infinite models. (Hence $T$ has no finite models - why is this?)

Exercise.

Suppose that $T$ has a type which is not isolated. I.e. suppose $T$ has a type which has no support. Show that $T$ is not ${\aleph}_{0}$-categorical.

Exercise.

Suppose that every type over $T$ is isolated. Let $n\in \mathbb{N}$. Show that there are finitely many types over $T$ in the variables ${x}_{1},\dots ,{x}_{n}$. Hint: Enumerate all formulas in ${x}_{1},\dots ,{x}_{n}$ as ${\sigma}_{0}\left(\stackrel{\_}{x}\right),{\sigma}_{1}\left(\stackrel{\_}{x}\right),\dots $, and for $A\subseteq \mathbb{N}$ consider

$${p}_{A}\left(\stackrel{\_}{x}\right)=\{{\sigma}_{i}\left(\stackrel{\_}{x}\right):i\in A\}\cup \{\neg {\sigma}_{i}\left(\stackrel{\_}{x}\right):i\notin A\}$$as the infinite paths through a certain tree. How many distinct consistent paths are there?

Definition.

A type in $n$ free variables ${x}_{1},\dots ,{x}_{n}$ is called an $n$-type.

Exercise.

Suppose $T$ has finitely many $n$-types for each $n\in \mathbb{N}$. Show that every type is isolated. (Hint: consider the tree in the previous exercise.)

Exercise.

Suppose that every type over $T$ is isolated and given countable models $M,N\models T$ show that $MN$. (Use back-and-forth.)

Hence deduce

Theorem.

For a complete theory $T$ with infinite models in a countable language $L$, the following are equivalent.

- $T$ is ${\aleph}_{0}$-categorical.
- $T$ has finitely many $n$-types for each $n\in \mathbb{N}$.
- every type over $T$ is isolated.

A variation of this result is also useful.

Exercise.

Suppose $T$ is a complete $L$-theory with infinite models and $T$ has countably many $n$-types for each $n\in \mathbb{N}$. Show that there is a countable model $M\models T$ such that

- Every type realised in $M$ is isolated, and
- for any $N\models T$ there is an elementary embedding $M\to N$.

Such a model is called a prime models. There is up to isomorphism at most one countable prim model of any complete theory $T$. However, there is no converse to the result in the last exercise: find such a theory $T$ with a prime model and uncountably many $n$-types for some $n$.