Łoś's Theorem

25 Jan 2025

This post continues from the previous post.

5. Nonstandard Characteristics of Hypernatural Numbers

The hypernatural numbers we have examined so far — $[0], [1], [2], \dots$ — correspond to standard natural numbers. We shall now examine some bizarre hypernatural numbers.

Consider the following hypernatural number $\mathfrak{n}$:

\[\mathfrak{n} = [(1, 2, 3, 4, \dots)]\]

Recalling how binary relation is defined for hypernaturals, for any natural number $n$, we have $[n] < \mathfrak{n}$. That is, $\mathfrak{n}$ is a hypernatural number greater than all natural numbers. That is, the following holds for hypernaturals:

\[\phi_1 : \exists x \; ( \lbrace y : y < x \rbrace \text{ is infinite } )\]

This sentence does not hold in the natural numbers.

Now consider the following hypernatural number $\mathfrak{m}$:

\[\mathfrak{m} = [(1, 2!, 3!, 4!, \dots)]\]

For any standard natural number $n$, $\mathfrak{m}$ is divisible by $[n]$. That is, $\mathfrak{m}$ has every natural number as a divisor. Therefore, the following holds for hypernaturals:

\[\phi_2 : \exists x \; (\lbrace y : y \mid x \rbrace \text{ is infinite })\]

Again, this sentence does not hold in the natural numbers.

This may seem to contradict the promise delivered in the previous essay. There, I stated that the natural numbers and hypernatural numbers are logically indistinguishable. Yet $\phi_1$ and $\phi_2$, both of which seem to be a cogent logical formula, are true in $\mathbb{N}^*$ but false in $\mathbb{N}$. Have I been misleading?

Of course not. The key to this apparent paradox lies in the fact that $\phi_1$ and $\phi_2$ cannot be expressed in first-order logic. By the compactness theorem, “… is finite” is inexpressible in first-order logic.

For a more precise statement, let us define the following:

Definition. Two $\mathcal{L}$-models $\mathcal{M}_1$ and $\mathcal{M}_2$ of a language $\mathcal{L}$ are elementarily equivalent if for any $\mathcal{L}$-sentence $\phi$,

\[\mathcal{M_1} \vDash \phi \iff \mathcal{M}_2 \vDash \phi\]

Theorem. $\mathbb{N}$ and $\mathbb{N}^*$ are elementarily equivalent.

This theorem is a special case of Łoś’s theorem. But before we state Łoś’s theorem, let us first rigorously define ultraproducts.

6. Ultraproducts

Let a set $I$ and a free ultrafilter $\mathcal{U}$ on $I$ be given. Furthermore, let models $\lbrace \mathcal{M}_i \rbrace_{i \in I}$ of a language $\mathcal{L}$ be given. We define the ultraproduct $\mathcal{M}^* = \prod \mathcal{M}_i / \mathcal{U}$ as follows:

Elements of the Ultraproduct

The elements of $\mathcal{M}^*$ are equivalence classes of $\lbrace (a_i)_{i\in I} : a_i \in \mathcal{M}_i \rbrace$ under the relation $\sim$, where $\sim$ is defined as:

\[(a_i)_{i\in I} \sim (b_i)_{i \in I} \iff \lbrace i \in I : a_i = b_i \rbrace \in \mathcal{U}\]

Operations on the Ultraproduct

Let $f(x)$ be a function in $\mathcal{L}$. For an element $\mathfrak{a} = [(a_i)_{i\in I}]$ of $\mathcal{M}^*$, we define:

\[f(\mathfrak{a}) = [(f(a_i))_{i \in I}]\]

This definition generalises naturally to $n$-ary functions.

Relations on the Ultraproduct

Let $P(x, y)$ be a relation in $\mathcal{L}$. For two elements $\mathfrak{a} = [(a_i)_{i\in I}]$ and $\mathfrak{b} = [(b_i)_{i\in I}]$ of $\mathcal{M}^*$, we define:

\[\mathcal{M}^* \vDash P(\mathfrak{a}, \mathfrak{b}) \iff \lbrace i \in I : \mathcal{M}_i \vDash P(a_i, b_i) \rbrace \in \mathcal{U}\]

This definition generalises naturally to $n$-ary predicates.

When defining operations and relation on the ultraproduct, one needs to show that the definition is irrelevant to which element is chosen as a representative for each equivalence class. This follows readily from the intersection property of $\mathcal{U}$, so we leave it as an exercise.

We can now redefine the hypernatural numbers as the ultraproduct arising when $I, \mathcal{U}, \mathcal{L}, \mathcal{M}_i$ are respectively:

• $I = \mathbb{N}$
• $\mathcal{U} =$ Fréchet ultrafilter
• $\mathcal{L} = (0, S, <)$
• $\mathcal{M}_i = \mathbb{N}$

Similarly, we can define the hyperreal numbers:

• $I = \mathbb{N}$
• $\mathcal{U} =$ Fréchet ultrafilter
• $\mathcal{L} = (0, 1, +, ⋅, <)$
• $\mathcal{M}_i = \mathbb{R}$

7. Łoś’s Theorem

Łoś’s Theorem. Given an ultraproduct $\mathcal{M}^* = \prod \mathcal{M}_i / \mathcal{U}$, for any $\mathcal{L}$-sentence $\phi$, the following holds:

\[\mathcal{M}^* \vDash \phi \iff \lbrace i \in I : \mathcal{M}_i \vDash \phi \rbrace \in \mathcal{U}\]

Proof. We prove this by structural induction on $\phi$.

1. $\phi$ is an atomic proposition

This follows trivially from the definition of predicates on ultraproducts.

2. $\phi := \psi \land \theta$

\[\begin{aligned} &\mathcal{M}^* ⊨ φ\\ &\iff \mathcal{M}^* ⊨ ψ \land \mathcal{M}^* ⊨ θ\\ &\iff \lbrace i ∈ I \mid \mathcal{M}_i ⊨ ψ \rbrace ∈ \mathcal{U} \land \lbrace i ∈ I \mid \mathcal{M}_i ⊨ θ \rbrace ∈ \mathcal{U} &&(*) \\ &\iff \lbrace i ∈ I \mid \mathcal{M}_i ⊨ ψ \rbrace \cap \lbrace i ∈ I \mid \mathcal{M}_i ⊨ θ \rbrace ∈ \mathcal{U} &&(**) \\ &\iff \lbrace i ∈ I \mid \mathcal{M}_i ⊨ ψ \land \mathcal{M}_i ⊨ θ \rbrace ∈ \mathcal{U}\\ &\iff \lbrace i ∈ I \mid \mathcal{M}_i ⊨ ψ∧θ \rbrace ∈ \mathcal{U}\\ &\iff \lbrace i ∈ I \mid \mathcal{M}_i ⊨ φ \rbrace ∈ \mathcal{U} \end{aligned}\]

$(*)$ holds by the inductive hypothesis, and $(**)$ holds by the intersection closure property of $\mathcal{U}$.

3. $\phi := \lnot \psi$

This can be proved by a similar method to case 2, using the inductive hypothesis and the ultrafilter property of $\mathcal{U}$ ($A \in \mathcal{U} \lor A^c \in \mathcal{U}$).

4. $\phi := \exists x\; \psi$

This can be proved by a similar method to case 2, though the inductive hypothesis alone suffices.

Since every proposition can be constructed from cases 1, 2, 3, and 4, the theorem is proved by induction. ■

Corollary. $\mathbb{N}$ and $\mathbb{N}^*$ are elementarily equivalent.

Proof. By Łoś’s theorem, the necessary and sufficient condition for $\mathbb{N}^* \vDash \phi$ is that $\lbrace i \in \mathbb{N} : \mathbb{N}^\ast_i \vDash \phi \rbrace \in \mathcal{U}$. However, since $\mathbb{N}^*_i = \mathbb{N}$, the necessary and sufficient condition reduces to $\mathbb{N} \vDash \phi$. ■