Past exam of the mathematics course of the University of Cambridge / 2015 / iii / Paper 23 / 1

Let $R={\prod }_i{\mathcal{M}}_i/F$ be the reduced product by a proper filter on a set. Its underlying equivalence relation is $f\sim g$ when $\{i:f(i)=g(i)\}\in F$. Operations are interpreted coordinatewise, and a relation holds of the classes exactly when its coordinate truth set belongs to $F$.

Evaluation of a first-order term commutes with passage to the quotient, by mathematical induction on terms. Consequently the desired equivalence holds for every atomic formula, including logical equality. For a formula $\theta$ and representatives $\bar{f}$, write $S_{\theta }=\{i:{\mathcal{M}}_i\models \theta (\bar{f}(i))\}$.

For logical conjunction, $S_{\theta \wedge \psi }=S_{\theta }\cap S_{\psi }$. The filter on a set axioms giveThus the induction hypothesis transfers a conjunction in both directions.

For existential quantification, first suppose $R\models \exists y\theta (y,[\bar{f}])$. Choose a representative $g$ of a witness. Induction gives $S_{\theta (g,\bar{f})}\in F$, and this set is contained in $S_{\exists y\theta }$. Upward closure therefore gives $S_{\exists y\theta }\in F$.

Conversely, suppose $A=S_{\exists y\theta }\in F$. For each $i\in A$, choose a coordinate witness $g(i)$, and choose an arbitrary element of $M_i$ outside $A$. These simultaneous choices use the axiom of choice, as does the usual product construction. Then $A\subseteq S_{\theta (g,\bar{f})}$, so that truth set belongs to $F$. Induction gives $R\models \theta ([g],[\bar{f}])$, providing the required witness. Thereforefor every primitive positive formula. The exam's tame formulas are exactly this fragment, built using logical conjunction and existential quantification. No ultrafilter dichotomy was used.

Take $I=\{0,1\}$ and the proper filter on a set $F=\{I\}$. In the first-order language with unary predicates $P,Q$, let both factors be one-element first-order structures. Set $P$ true and $Q$ false in the first factor, and reverse these truth values in the second.

The reduced product also has one element $a$. Neither $P(a)$ nor $Q(a)$ holds there: their truth sets are $\{0\}$ and $\{1\}$, neither belonging to $F$. ThusLogical disjunction can therefore break the equivalence. A union can belong to a filter on a set without either summand belonging to it; the corresponding union property does hold for an ultrafilter.

Use the same two-index filter on a set $F=\{\{0,1\}\}$, with a unary predicate $P$ true only in the first one-element factor. In the reduced product, $P(a)$ is false, so $\neg P(a)$ is true. ButLogical negation also breaks the equivalence. For a general proper filter on a set, a set and its complement can both be absent. In an ultrafilter, exactly one belongs, which is the step used to transfer logical negation in the Łoś theorem.

An ultrafilter $U$ on $X$ is kappa-complete if, for every index set $J$ with $|J|<\kappa$ and every family $(A_j{)}_{j\in J}$ of members of $U$,The bound is strictly fewer than $\kappa$ sets. In particular every ultrafilter is ${\aleph }_0$-complete, since this requires only finite intersections; countably complete ultrafilters require intersections of countably many members, equivalently ${\aleph }_1$-completeness.

First use the fact that a small set is absent from a complete nonprincipal ultrafilter. Indeed, if $A\subseteq \kappa$ and $|A|<\kappa$, then every $\kappa \setminus \{\alpha \}$, $\alpha \in A$, belongs to $U$ by nonprincipality. Kappa-completeness gives $\kappa \setminus A\in U$, so $A\notin U$. In particular every final segment $\{i:i>\alpha \}$ belongs to $U$.

Suppose for contradiction that the ultrapower has at most $\kappa$ elements. List representatives $f_{\alpha }:\kappa \to M$ for all its classes, indexed by $\alpha <\kappa$; repetitions are allowed. At coordinate $i<\kappa$, fewer than $\kappa$ values occur among $f_{\alpha }(i)$ with $\alpha <i$. Since $|M|\ge \kappa$, chooseThis diagonal argument for ultrapower cardinality uses the axiom of choice. For each fixed $\alpha$, the functions $g$ and $f_{\alpha }$ disagree throughout the final segment $i>\alpha$, which belongs to $U$. Their equality set therefore cannot belong to $U$, and $[g]\ne [f_{\alpha }]$.

This contradicts the assumed enumeration of the ultrapower. HenceThe proof uses only that each ordinal $i<\kappa$ has cardinality below $\kappa$; it does not require a separate assumption of regularity.