Proof of Los's Theorem

Los's theorem (also called the fundamental theorem of ultraproducts) states that a first-order sentence holds in an ultraproduct if and only if it holds in "most" factors, as measured by the ultrafilter. This result is the backbone of ultraproduct constructions.

Statement

Theorem4.4Los's Theorem

Let $\{\mathcal{M}_i\}_{i \in I}$ be $\mathcal{L}$ -structures and $\mathcal{U}$ an ultrafilter on $I$ . For the ultraproduct $\mathcal{M}^* = \prod_{i \in I} \mathcal{M}_i / \mathcal{U}$ and any $\mathcal{L}$ -formula $\varphi(x_1, \ldots, x_n)$ with elements $[a_1], \ldots, [a_n] \in M^*$ : $\mathcal{M}^* \models \varphi([a_1], \ldots, [a_n]) \iff \{i \in I : \mathcal{M}_i \models \varphi(a_1(i), \ldots, a_n(i))\} \in \mathcal{U}.$

Proof

By induction on the complexity of $\varphi$ .

Atomic formulas: For $\varphi$ being $t_1 = t_2$ , by definition of the ultraproduct, $[t_1] = [t_2]$ in $\mathcal{M}^*$ iff $\{i : t_1^{\mathcal{M}_i} = t_2^{\mathcal{M}_i}\} \in \mathcal{U}$ . For relation symbols $R(t_1, \ldots, t_k)$ , by definition, $R^{\mathcal{M}^*}([t_1], \ldots, [t_k])$ holds iff $\{i : R^{\mathcal{M}_i}(t_1(i), \ldots, t_k(i))\} \in \mathcal{U}$ .

Negation: $\mathcal{M}^* \models \neg\varphi \iff \mathcal{M}^* \not\models \varphi \iff \{i : \mathcal{M}_i \models \varphi\} \notin \mathcal{U} \iff I \setminus \{i : \mathcal{M}_i \models \varphi\} \in \mathcal{U} \iff \{i : \mathcal{M}_i \models \neg\varphi\} \in \mathcal{U}$ , using the ultrafilter property.

Conjunction: $\mathcal{M}^* \models \varphi \land \psi \iff \mathcal{M}^* \models \varphi$ and $\mathcal{M}^* \models \psi \iff \{i : \mathcal{M}_i \models \varphi\} \in \mathcal{U}$ and $\{i : \mathcal{M}_i \models \psi\} \in \mathcal{U} \iff \{i : \mathcal{M}_i \models \varphi \land \psi\} \in \mathcal{U}$ , since $\mathcal{U}$ is closed under finite intersection.

Existential quantifier: $\mathcal{M}^* \models \exists x \, \varphi(x, [\bar{a}]) \iff$ there exists $[b] \in M^*$ with $\mathcal{M}^* \models \varphi([b], [\bar{a}]) \iff$ there exists $[b]$ with $\{i : \mathcal{M}_i \models \varphi(b(i), \bar{a}(i))\} \in \mathcal{U}$ .

We need $\{i : \mathcal{M}_i \models \exists x \, \varphi(x, \bar{a}(i))\} \in \mathcal{U}$ . The forward direction is clear (the witness $b(i)$ works for each $i$ in the set). For the converse: if $J = \{i : \mathcal{M}_i \models \exists x \, \varphi(x, \bar{a}(i))\} \in \mathcal{U}$ , use the axiom of choice to pick $b(i) \in M_i$ with $\mathcal{M}_i \models \varphi(b(i), \bar{a}(i))$ for $i \in J$ (and $b(i)$ arbitrary for $i \notin J$ ). Then $[b]$ witnesses the existential in $\mathcal{M}^*$ . $\square$

■

Consequences

ExampleTransfer Principle

For an ultrapower $\mathcal{M}^* = \mathcal{M}^I / \mathcal{U}$ , Los's theorem gives: $\mathcal{M}^* \models \sigma \iff \mathcal{M} \models \sigma$ for all sentences $\sigma$ . Thus $\mathcal{M}^* \equiv \mathcal{M}$ , and the diagonal embedding $a \mapsto [(a, a, \ldots)]$ is elementary.

RemarkBeyond First Order

Los's theorem fails for second-order logic: an ultrapower of $\mathbb{N}$ is not isomorphic to $\mathbb{N}$ (it has non-standard elements), so the second-order induction axiom fails. This is precisely why ultraproducts are a first-order tool.