Łoś's Theorem

Theorem

Let $\mathcal{L}$ be a language, let $I$ be an infinite set, and let $\mathcal{U}$ be an ultrafilter on $I$.

Let $\phi(v_1,\dots,v_n)$ be an $\mathcal{L}$-formula.

Let $\mathcal{M}$ be the ultraproduct $\displaystyle{\left(\prod_{i\in I}\mathcal{M} i \right) / \mathcal{U}}$, where each $\mathcal{M}_i$ is a $\mathcal{L}$-structures.

Then, for all $m_1 = (m_{1,i})_\mathcal{U},\dots, m_n = (m_{n,i})_\mathcal{U}$ in $\mathcal{M}$, we have that $\mathcal{M}\models\phi(m_1, \dots, m_n)$ if and only if the set $\{i\in I\mid \mathcal{M}_i \models \phi(m_{1,i},\dots,m_{n,i})\}$ is in $\mathcal{U}$.

In particular, for all $\mathcal{L}$ sentences $\phi$, we have that $\mathcal{M}\models\phi$ if and only if $\{i\in I\mid\mathcal{M}_i \models \phi\}$ is in $\mathcal{U}$.

Proof

We prove this by induction on the complexity of formulas. We appeal to the interpretations of language symbols in the ultraproduct when viewed as an $\mathcal{L}$-structure, the properties of ultrafilters, and make use of the Axiom of Choice.

The theorem holds trivially for statements of equality of terms and for relations, by definition of how to interpret language symbols for the ultraproduct.

Suppose the theorem holds for $\psi_0$ and $\psi_1$.

If $\phi$ is $\neg \psi_0$:

We are assuming that $\mathcal{M}\models \psi_0$ iff $\{i\mid \mathcal{M}_i \models \psi_0\}\in\mathcal{U}$.

Thus, $\mathcal{M}\models \phi$ iff $\{i\mid \mathcal{M}_i \models \psi_0\}\notin\mathcal{U}$ follows by negating both sides of this statement.

Since $\mathcal{U}$ is an ultrafilter, a set is absent from $\mathcal{U}$ iff the set's complement is present in $\mathcal{U}$. So, we may again rewrite the above statement equivalently as

$\mathcal{M}\models \phi$ iff $I-\{i\mid \mathcal{M}_i \models \psi_0\}\in\mathcal{U}$

Finally, we can further rewrite this set difference to see that

$\mathcal{M}\models \phi$ iff $\{i\mid \mathcal{M}_i \models \phi\}\in\mathcal{U}$

which is the statement that the theorem holds for $\phi$.

If $\phi$ is $\psi_0 \wedge \psi_1$:

For both $k\in\{0,1\}$, we are assuming that $\mathcal{M}\models \psi_k$ iff $\{i\mid \mathcal{M}_i \models \psi_k\}\in\mathcal{U}$.

By choice of $\phi$, we have $\mathcal{M}\models\phi$ iff $\mathcal{M}\models \psi_0 \wedge \psi_1$.

The right side of this iff statement can be rewritten as $\mathcal{M}\models \psi_0$ and $\mathcal{M}\models \psi_1$. Thus, using the inductive hypothesis stated above for each $\psi_k$, we can write

$\mathcal{M}\models \phi$ iff $\{i\mid \mathcal{M}_i \models \psi_0\}\in\mathcal{U}$ and $\{i\mid \mathcal{M}_i \models \psi_1\}\in\mathcal{U}$.

Since $\mathcal{U}$ is a filter, it is closed under intersections, and hence the right side of this statement can be written as $\{i\mid \mathcal{M}_i \models \psi_0 \text{ and } \mathcal{M}_i \models \psi_1\}\in\mathcal{U}$. Thus, we may write

$\mathcal{M}\models\phi$ iff $\{i\mid \mathcal{M_i}\models \phi\}\in\mathcal{U}$.

which is the statement that the theorem holds for $\phi$.

If $\phi$ is $\exists x \psi_0 (x)$:

If $x$ is not free in $\psi_0$ then earlier cases cover this, so we may assume $x$ is free in $\psi_0$. We are assuming then that for all $m = (m_i)_\mathcal{U}$ in $\mathcal{M}$, we have $\mathcal{M}\models\psi_0 (m)$ iff $\{i\in I\mid \mathcal{M}_i \models \psi_0 (m_i)\}\in \mathcal{U}$.

Thus, we may write

$\mathcal{M}\models\phi$ iff there exists some $m = (m_i)_\mathcal{U}$ in $\mathcal{M}$ for which $\{i\in I\mid \mathcal{M}_i \models \psi_0 (m_i)\}\in \mathcal{U}$.

One direction of the theorem follows easily since this above statement gives us the witnesses $m_i$: if $\mathcal{M}\models\phi$, then $\{i\in I\mid \mathcal{M}_i \models \exists x \psi_0 (x)\}\in \mathcal{U}$.

For the converse, we need to find some appropriate $(m_i)_\mathcal{U}$ in order to apply the above iff statement.

To this end, let $\{i\in I\mid \mathcal{M}_i \models \exists x \psi_0 (x)\}\in \mathcal{U}$, and apply the Axiom of Choice as follows:

Select for each $i\in\{i\in I\mid \mathcal{M}_i \models \exists x \psi_0 (x)\}$ a witness $m_i\in\mathcal{M}_i$ such that $\mathcal{M}_i \models \psi_0 (m_i)$

Select for each $i$ not in this set an arbitrary element $m_i$ of $\mathcal{M}_i$.

Taking $(m_i)_\mathcal{U}$ as our element of $\mathcal{M}$ then allows us to apply the above iff statement and complete the proof.

$\blacksquare$

Source of Name

This entry was named for Jerzy Łoś.