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

An omega-saturated model realizes every complete one-type over every finite subset of its domain that is consistent with the first-order structure's first-order theory with those named parameters. Equivalently, every partial type in a finite tuple over finitely many parameters that is finitely satisfiable in the first-order structure has a realization there. The equivalence follows by extending a partial type to a complete type; finite tuples can be handled one coordinate at a time.

For an example, take a countably infinite set in the language of equality alone. Over finitely many named elements, a complete one-type either requires equality with one of them or inequality with all of them. Both possibilities are realized. quantifier elimination for an infinite pure set follows by choosing a quantified variable either equal to one of the finitely many named values or distinct from all of them. Indeed every permutation fixing the parameters is a structure automorphism, and all other elements have the same type, so there are no further one-types. This first-order structure is omega-saturated.

For a counterexample, take $(\mathbb{N};0,S)$, where $S(n)=n+1$. The parameter-free partial typeis finitely satisfiable: choose an integer beyond the finitely many excluded numerals. It is not realized in the first-order structure, because every natural number is one of those numerals. Any complete extension of this partial type is therefore omitted as well. Thus the standard successor first-order structure is not omega-saturated.

Here fixed means fixed setwise: $\sigma [D]=D$ for every structure automorphism $\sigma$, not that each point must be fixed individually. A parameter-free definable set has this invariance by automorphism invariance of parameter-free definability.

For the converse, first establish the needed saturation implies homogeneity step. In a countable omega-saturated model, a finite partial elementary map can be extended to include any prescribed additional element in its domain. Transfer the element's complete type over the old finite domain along the map. Each finite part of this transported type has a witness because the old map is elementary; the omega-saturated model realizes the full transported type. The inequalities in the type maintain injectivity. Apply the same construction to the inverse map to enlarge the range. Alternating these steps through an enumeration of the countable domain is the back-and-forth method, giving a structure automorphism. In particular, any two elements with the same complete type over the empty set are related by a structure automorphism.

Assume now that $D$ is finite and invariant, and fix $a\in D$. All realizations in $A$ of $p_a=\mathrm{tp}(a/\varnothing )$ belong to $D$, by the preceding homogeneity and the invariance assumption. Suppose that no parameter-free first-order formula ${\theta }_a\in p_a$ has all its realizations in $D$. Then every finite subset ofis satisfiable in $A$: conjoin the finitely many first-order formulas from $p_a$, and use the assumed absence of a defining neighbourhood inside $D$ to find a witness outside $D$. This is a partial type over the finite parameter set $D$. The omega-saturated model would realize it by an element outside $D$ with the same empty-set type as $a$, a contradiction. Hence such a ${\theta }_a$ does exist.

There are only finitely many $a\in D$, soFor $D=\varnothing$, use $x\ne x$. Thus finite invariant sets in a countable saturated structure are definable. Finiteness is used twice: the extra parameters form a finite set, and the final disjunction is a first-order formula rather than an infinite disjunction.

A filter on a set $I$ means a proper family $\mathcal{F}\subseteq \mathcal{P}(I)$ with $I\in \mathcal{F}$, $\varnothing \notin \mathcal{F}$, closure under finite intersections, and upward closure under inclusion. An ultrafilter is a maximal proper filter; equivalently, for every $X\subseteq I$, exactly one of $X$ and $I\setminus X$ belongs to it. A principal ultrafilter is $\{X\subseteq I:i\in X\}$ for some $i\in I$. A nonprincipal ultrafilter is one not of that form, equivalently one containing no finite set.

To prove the ultrafilter lemma using Zorn's lemma, order all proper filters containing $\mathcal{F}$ by inclusion. The union of any chain is a proper filter: finitely many members lie together in one filter of the chain, and no chain member contains the empty set. Thus every chain has an upper bound, and Zorn's lemma gives a maximal member $\mathcal{U}$.

For completeness, its decision property follows from maximality. If $X\notin \mathcal{U}$, adjoining $X$ cannot generate a proper filter. Hence some $F\in \mathcal{U}$ has $F\cap X=\varnothing$. Upward closure gives $I\setminus X\in \mathcal{U}$. Both complements cannot be members, since their intersection is empty. Therefore $\boxed{\mathcal{F}\subseteq \mathcal{U}\text{ for an ultrafilter }\mathcal{U}}$. Properness is essential; a family containing the empty set cannot extend to an ultrafilter.

Write the ultrafilter as $\mathcal{U}$ to distinguish it from first-order structure domains. On the direct product ${\prod }_{i\in I}{A}_i$, putThe domain of the ultraproduct is the quotient $({\prod }_i{A}_i)/\sim$. Its elements are classes $[\mathbf{a}]$. A constant $c$ is interpreted by $[(c^{{\mathcal{A}}_i}{)}_i]$, and a $k$-ary function symbol byFor a $k$-ary relation symbol,These definitions are independent of representatives: if finitely many input representatives are changed, the coordinates where all old and new inputs agree form a set in the filter. At those coordinates the interpreted outputs and relation truth values agree. Filter closure and upward closure therefore preserve the resulting quotient elements and truth conditions.

The Łoś theorem states that, for every first-order formula $\phi (\mathbf{x})$ and product representatives ${\mathbf{a}}^1,\dots ,{\mathbf{a}}^r$,It extends the defining relation-symbol rule to arbitrary first-order formulas, including quantified ones.

Identify the countable index set with $\mathbb{N}$. A nonprincipal ultrafilter on it contains every cofinite set. Let $p(x)$ be a type over a finite parameter set in the ultraproduct $\mathcal{M}$, finitely satisfiable in $\mathcal{M}$. Because the language and parameter set are countable, enumerate it as ${\phi }_0(x),{\phi }_1(x),\dots$, with chosen product representatives for the parameters. By finite satisfiability and Łoś,Make these large sets decrease while forcing their intersection to be empty:For each index $i$, let $r(i)$ be the largest $n\le i$ with $i\in Y_n$, if one exists. Choose $b_i\in A_i$ satisfying the first $r(i)+1$ first-order formulas; this is possible because $i\in X_{r(i)}$. If no such $n$ exists, choose any $b_i$.

For each fixed $n$, every $i\in Y_n$ has $r(i)\ge n$, so $b_i$ satisfies ${\phi }_n$. Its coordinate truth set contains $Y_n$ and belongs to $\mathcal{U}$. Another use of Łoś gives $\mathcal{M}\models {\phi }_n([\mathbf{b}])$ for every $n$. Thus $[\mathbf{b}]$ realizes the type. This proves the countable saturation of an ultraproduct over omega, and in particular the ultraproduct is omega-saturated. The construction chooses a finite number of requirements at each coordinate; it does not presume the whole infinite type has a witness in any factor.

Let $P_1$ and $P_3$ be the sets of primes congruent to one and three modulo four. Both are infinite. For $P_1$, if a finite list contained them all, put $N=(2p_1\cdots p_r{)}^2+1$. Any prime divisor $q$ of this odd number is new and has minus one as a square modulo $q$, hence belongs to $P_1$ by the given criterion. For $P_3$, use $N=4p_1\cdots p_r-1$. It is three modulo four, so at least one of its odd prime divisors is three modulo four; none of the listed primes divides $N$. These are elementary Euclidean proofs of infinitely many primes in each odd residue class modulo four.

On the set of all primes, the cofinite sets together with $P_1$ have the finite intersection property; so do the cofinite sets together with $P_3$. Extend the generated filters to ultrafilters ${\mathcal{U}}_1$ and ${\mathcal{U}}_3$ using the ultrafilter lemma. They are nonprincipal because they contain every cofinite set, including the complement of any singleton. FormEvery sentence of $\Sigma$ has a cofinite truth set, hence belongs to both ultrafilters. The Łoś theorem shows $F_1,F_2\models \Sigma$. In particular they are fields, since each field axiom holds in every factor.

For each fixed positive integer $n$, the sentence $n\cdot 1\ne 0$ holds in ${\mathbb{F}}_p$ unless $p$ divides $n$. Its truth set is cofinite, so both fields satisfy it. Therefore $\boxed{\mathrm{char}{F}_1=\mathrm{char}{F}_2=0}$.

Finally the sentence $\exists x(x^2+1=0)$ holds at exactly the primes in $P_1\cup \{2\}$. This set belongs to ${\mathcal{U}}_1$, whereas its complement contains $P_3$ and belongs to ${\mathcal{U}}_3$. Łoś therefore givesThus minus one is a square in the first characteristic-zero first-order model of $\Sigma$ and is not a square in the second. The construction also shows why eventual truth over all primes need not decide a sentence whose truth splits along two infinite prime subsequences.