Łoś's Theorem

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $\mathcal L$ be a language.

Let $I$ be an infinite set.

Let $\mathcal U$ be an ultrafilter on $I$.

Let $\map \phi {v_1, \ldots, v_n}$ be an $\mathcal L$-formula.

Let $\mathcal M$ be the ultraproduct:

$\displaystyle \paren {\prod_{i \mathop \in I}\mathcal M i} / \mathcal U$

where each $\mathcal M_i$ is a $\mathcal L$-structures.


Then, for all $m_1 = \paren {m_{1, i} }_\mathcal U, \dots, m_n = \paren {m_{n, i} }_\mathcal U$ in $\mathcal M$:

$\mathcal M \models \map \phi {m_1, \ldots, m_n}$

if and only if:

the set $\set {i \in I: \mathcal M_i \models \map \phi {m_{1, i}, \ldots, 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 $\set {i \in I: \mathcal M_i \models \phi}$ is in $\mathcal U$.


Proof

We prove the $\mathcal L$-sentences case by induction on the complexity of formulas. The general case trivially follows this proof.

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$ if and only if:

$\set {i: \mathcal M_i \models \psi_0} \in \mathcal U$.

Thus:

$\mathcal M \models \phi$ if and only if $\set {i: \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$ if and only if 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 \setminus \set {i: \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 \set {i: \mathcal M_i \models \phi} \in \mathcal U$

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


Let $\phi$ be $\psi_0 \wedge \psi_1$:

For both $k \in \left\{{0, 1}\right\}$, we are assuming that:

$\mathcal M \models \psi_k \iff \set {i: \mathcal M_i \models \psi_k} \in \mathcal U$

By choice of $\phi$, we have $\mathcal M \models \phi$ if and only if $\mathcal M \models \psi_0 \wedge \psi_1$.

The right side of this if and only if 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$:

$\mathcal M \models \phi \iff \set {i: \mathcal M_i \models \psi_0} \in \mathcal U$ and $\set {i: \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:

$\set {i: \mathcal M_i \models \psi_0 \text{ and } \mathcal M_i \models \psi_1} \in \mathcal U$

Thus:

$\mathcal M \models \phi \iff \set {i: \mathcal M_i \models \phi} \in \mathcal U$

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


Let $\phi$ be $\exists x \psi_0 \left({x}\right)$:

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 = \left\langle{m_i}\right\rangle_\mathcal U$ in $\mathcal M$:

$\mathcal M \models \psi_0 \left({m}\right) \iff \left\{{i \in I: \mathcal M_i \models \psi_0 \left({m_i}\right)}\right\}\in \mathcal U$

Thus:

$\mathcal M \models \phi \iff \exists m = \left\langle{m_i}\right\rangle_\mathcal U \in \mathcal M$

for which:

$\left\{{i \in I: \mathcal M_i \models \psi_0 \left({m_i}\right)}\right\}\in \mathcal U$

One direction of the theorem follows easily, since this above statement gives us the witnesses $m_i$:

$\mathcal M \models \phi \implies \left\{{i \in I: \mathcal M_i \models \psi_0 \left({m_i}\right)}\right\} \in \mathcal U$

And this above set is included in the set we're looking for, so that is an element of the ultrafilter as well:

$\left\{{i \in I: \mathcal M_i \models \psi_0 \left({m_i}\right)}\right\} \subseteq \left\{{i \in I: \mathcal M_i \models \exists x \psi_0 \left({x}\right)}\right\}\in \mathcal U$

For the converse, we need to find some appropriate $\left\langle{m_i}\right\rangle_\mathcal U$ in order to apply the above biconditional statement.

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

Select for each $i \in \left\{{i \in I: \mathcal M_i \models \exists x \psi_0 \left({x}\right)}\right\}$ a witness $m_i \in \mathcal M_i$ such that $\mathcal M_i \models \psi_0 \left({m_i}\right)$

Select for each $i$ not in this set an arbitrary element $m_i$ of $\mathcal M_i$.

Taking $\left\langle{m_i}\right\rangle_\mathcal U$ as our element of $\mathcal M$ then allows us to apply the above biconditional statement and complete the proof.

$\blacksquare$


Source of Name

This entry was named for Jerzy Maria Michał Łoś.