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

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.