Math 557 Oct 8

Ultraproducts

Direct Products

Let \((\mathcal{M}_i)_{i \in I}\) be a family of \(L\)-structures.

We define the direct product \[ \mathcal{M} = \prod_{i \in I} \mathcal{M}_i \] as follows:

1. The universe is the Cartesian product \(M = \prod_{i \in I} M_i\). If \(a\) is an element of \(M\), we denote its \(i\)-th component (an element of \(M_i\)) by \(a_i\) and extend this notation to vectors: if \(\vec a\) is a finite tuple in \(M^n\), \(\vec a_i\) denotes the \(n\)-tuple in \(M_i\) consisting of the \(M_i\)-entries of \(\vec a\).
2. For each relation symbol \(R \in \mathcal{L}\), \[ R^{\mathcal{M}}(\vec a) :\iff \forall i \in I,\, \vec a_i \in R^{\mathcal{M}_i} \]
3. For each function symbol \(f \in \mathcal{L}\), \[ f^{\mathcal{M}}(\vec a) := (f^{\mathcal{M}_i}(\vec a_i))_{i\in I}. \]
4. For each constant \(c \in \mathcal{L}\), \[ c^{\mathcal{M}} = (c^{\mathcal{M}_i})_{i\in I}. \]

Examples and Observations

• The direct product of groups is again a group (componentwise operation).
• The direct product of fields is not a field: \[ (1,0)\cdot(0,1) = (0,0). \]
• The direct product of linear orders is only a partial order.

We often want to preserve properties that hold in “most” component structures.
To formalize “most,” we use filters on \(I\).

Filters and Ultrafilters

A filter \(\mathcal{F}\) on a set \(I\) is a nonempty collection of subsets of \(I\) satisfying:

1. \(\emptyset \notin \mathcal{F}\)
   
2. If \(A,B \in \mathcal{F}\), then \(A \cap B \in \mathcal{F}\)
   
3. If \(A \in \mathcal{F}\) and \(A \subseteq B \subseteq I\), then \(B \in \mathcal{F}\)

An ultrafilter \(\mathcal{U}\) is a maximal filter, equivalently:

For all \(A \subseteq I\), either \(A \in \mathcal{U}\) or \(I \setminus A \in \mathcal{U}\).

Ultrafilters interact nicely with logical operators:

• \(A \not \in \mathcal{U} \iff I \backslash A \in \mathcal{U}\),
• \(A \in \mathcal{U} \wedge B \in \mathcal{U} \iff A \cap B \in \mathcal{U}\),
• \(A \in \mathcal{U} \vee B \in \mathcal{U} \iff A \cup B \in \mathcal{U}\).

Examples

• A principal filter is of the form
  \[ \mathcal{F}_A = \{ X \subseteq I : A \subseteq X \} \] for some nonempty \(A \subseteq I\).
  If \(A = \{a\}\), then \(\mathcal{F}_A\) is a principal ultrafilter.

• A free (non-principal) ultrafilter exists on every infinite set \(I\)
  (via Zorn’s Lemma / Boolean prime ideal theorem).

Existence of Ultrafilters

A family of sets has the finite intersection property (FIP) if every finite subfamily has nonempty intersection.

Theorem 1
If a family \(\mathcal{A} \subseteq \mathcal{P}(I)\) has the FIP,
then there exists an ultrafilter \(\mathcal{U}\) on \(I\) with \(\mathcal{A} \subseteq \mathcal{U}\).

Reduced Products

Given a filter \(\mathcal{F}\) on \(I\) and structures \((\mathcal{M}_i)_{i \in I}\), define the reduced product \[ \mathcal{M} / \mathcal{F} \] as follows.

Let \(M = \prod_{i \in I} M_i\). For \(a,b \in M\), define \[ a \sim_{\mathcal{F}} b \iff \{\, i \in I : a_i = b_i \,\} \in \mathcal{F}. \]

The universe of \(\mathcal{M}/\mathcal{F}\) is the quotient \(M / {\sim_{\mathcal{F}}}\), with elements denoted \(a_{\mathcal{F}}\) (alternatively, \(a/\mathcal{F}\)).

For symbols of \(\mathcal{L}\):

• Relations:
  \[ R^{\mathcal{M}/\mathcal{F}}(\vec a_{\mathcal{F}}) : \iff \{\, i : \mathcal{M}_i \models R(\vec a_i) \,\} \in \mathcal{F}. \]

• Functions:
  \[ f^{\mathcal{M}/\mathcal{F}}(\vec a_{\mathcal{F}}) = [\, (f^{\mathcal{M}_i}(\vec a_i))_{i \in I} \,]_{\mathcal{F}}. \]

• Constants:
  \[ c^{\mathcal{M}/\mathcal{F}} = ((c^{\mathcal{M}_i})_{i\in I})_{\mathcal{F}}. \]

Exercise 1 Check that the above definition does not depend on the choice of representative for each equivalence class

Ultraproducts

If \(\mathcal{U}\) is an ultrafilter on \(I\), the reduced product \[ \prod_{i \in I} \mathcal{M}_i / \mathcal{U} \] is called the ultraproduct of \((\mathcal{M}_i)_{i \in I}\) modulo \(\mathcal{U}\).

When all \(\mathcal{M}_i\) are the same structure \(\mathcal{M}\), we get an ultrapower \[ \mathcal{M}^I / \mathcal{U}. \]

Łoś’ Theorem

Let \(\mathcal{M}/\mathcal{U} = \prod_{i \in I} \mathcal{M}_i / \mathcal{U}\) be an ultraproduct.

Theorem 2
For every \(\mathcal{L}\)-formula \(\varphi(x_1,\dots,x_n)\) and tuples
\(\vec a \in \prod_{i \in I} M_i\), \[ \mathcal{M}/\mathcal{U} \models \varphi[\vec a_{\mathcal{U}}] \iff \{\, i \in I : \mathcal{M}_i \models \varphi[\vec a_i]\,\} \in \mathcal{U}. \]

For any \(\mathcal{L}\)-formula \(\varphi(v_0,\ldots,v_{n-1})\) a a tuple \(\vec{a} \in \prod M_i\) we define the Boolean extension as \[ \|\varphi(\vec{a}) \| := \{i \in I| \mathcal{M}_i \models \varphi[\vec{a}_i]\} \]

Lemma 1  

1. \(\| \neg \varphi(\vec{a}) \| = I \backslash \|\varphi(\vec{a}) \|\),
2. \(\| (\varphi \wedge \psi)(\vec{a}) \| =\| \varphi(\vec{a}) \| \cap \| \psi(\vec{a}) \|\),
3. \(\| (\varphi \vee \psi)(\vec{a}) \| =\| \varphi(\vec{a}) \| \cup \| \psi(\vec{a}) \|\),
4. For all tuples \(\vec{a}\) and elements \(b\) in \(A\): \[ \|\varphi(\vec{a},b) \| \subseteq \| (\exists v_n \varphi)(\vec{a}) \|, \] and there exists \(b \in M\) such that \[ \|\varphi(\vec{a},b) \| = \| (\exists v_n \varphi)(\vec{a}) \|. \]

Proof. (1)-(3) and the first part of (4) follow directly from the definition of ultrafilters (and the definition of \(\models\)).

For the second part of (4), we observe that for every \[ i \in \| (\exists v_n \varphi)(\vec{a}) \| \] there exists \(b_i \in A_i\) with \(\mathcal{M}_i \models \varphi[\vec{a}_i,b_i]\). For all other \(j \in I \setminus \| (\exists v_n \varphi)(\vec{a}) \|\) we choose an aribitrary \(b_j \in A_j\). This yields a sequence \(b = (b_i)_{i\in I}\) with \(b \in M\), for which \[ \| (\exists v_n \varphi)(\vec{a}) \| \subseteq \|\varphi(\vec{a},b) \|. \] Together with the first part we obtain \(=\).

Proof of Łoś’s Theorem

We proceed by induction over the formula height. A straightforward argument shows that the interpretation of functions and symbols in \(\mathcal{M}\) extends to terms in the following way: \[ t^{\mathcal{M}/\mathcal{U}}(\vec{a}/U) = (t^{\mathcal{M}_i}(\vec{a}_i))_{i \in I}/\mathcal{U} = t^{\mathcal{M}}(\vec{a})/\mathcal{U} \] This easily implies the statement for atomic formulas.

For \(\varphi \equiv \neg \psi\), we have \[ \begin{aligned} \mathcal{M}/\mathcal{U} \models \neg \psi[\vec{a}_{\mathcal{U}}] &\iff \mathcal{M}/\mathcal{U} \not\models \psi[\vec{a}_{\mathcal{U}}] \\[6pt] &\iff \{\, i : \mathcal{M}_i \models \psi[\vec{a}_i] \,\} \notin \mathcal{U} && \text{(I.H.)} \\[6pt] &\iff \| \psi(\vec{a}) \| \notin \mathcal{U} \\[6pt] &\iff \neg \| \psi(\vec{a}) \| \in \mathcal{U} && (\mathcal{U}\ \text{is an ultrafilter}) \\[6pt] &\iff \| \neg \psi(\vec{a}) \| \in \mathcal{U} && \text{(Lemma (i))} \\[6pt] &\iff \{\, i : \mathcal{M}_i \models \neg \psi[\vec{a}_i] \,\} \in \mathcal{U}. \end{aligned} \]

The case \(\varphi \equiv (\psi \land \theta)\) is similar.

Finally, assume \(\varphi \equiv \exists y \psi\). Then \[ \begin{aligned} \mathcal{M}/\mathcal{U} \models \exists y\, \psi[\vec{a}_{\mathcal{U}}] &\iff \exists b_{\mathcal{U}} \in \mathcal{M}/\mathcal{U} \text{ such that } \mathcal{M}/\mathcal{U} \models \psi[\vec{a}_{\mathcal{U}}, b_{\mathcal{U}}] \\[6pt] &\iff \exists b \in M \text{ such that } \{\, i : \mathcal{M}_i \models \psi[\vec{a}_i, b_i] \,\} \in \mathcal{U} && \text{(I.H.)} \\[6pt] &\iff \exists b \in M \text{ such that } \|\psi(\vec{a}, b)\| \in \mathcal{U} \\[6pt] &\iff \|\exists y\, \psi(\vec{a})\| \in \mathcal{U} && (\mathcal{U}\ \text{ultrafilter, Lemma (4)}) \\[6pt] &\iff \{\, i : \mathcal{M}_i \models \exists y\, \psi[\vec{a}_i] \,\} \in \mathcal{U}. \end{aligned} \]

This completes the proof.

Applications

• Preservation of theories:
  If each \(\mathcal{M}_i \models T\), then \(\prod_i \mathcal{M}_i / \mathcal{U} \models T\).

• Ultrapowers:
  \(\mathcal{M} \equiv \mathcal{M}^I / \mathcal{U}\), i.e., a structure is elementarily equivalent to any of its ultrapowers.

• Nonstandard models:
  For example, the ultrapower \(\mathbb{N}^{\mathbb{N}}/\mathcal{U}\) (with \(\mathcal{U}\) non-principal) yields a countably saturated nonstandard model of arithmetic.

A new proof of the compactness theorem

Suppose \(T\) is an \(\mathcal{L}\)-theory for which every finite subset \(\Delta\) has a model \(\mathcal{M}_\Delta\).

Let \(I = \{\Delta : \Delta \subseteq T \text{ finite}\}\).

For \(\sigma \in T\), let \[ \begin{aligned} \hat{\sigma} & = \{\Delta \in I : \sigma \in \Delta\} \subseteq I \\ E & = \{\hat{\sigma} : \sigma \in T\} \subseteq \mathcal{P}(I) \\ \end{aligned} \]

\(E\) has FIP (finite intersection property), since for \(\hat{S}_1, \ldots, \hat{S}_n \in E\), \[ \{\hat{\sigma}_1, \ldots, \hat{\sigma}_n\} \in \hat{\sigma}_1 \cap \cdots \cap \hat{\sigma}_n. \]

By Theorem 1, \(E\) can be extended to an ultrafilter \(\mathcal{U}\) on \(I\).

Claim: \(\mathcal{M}/\mathcal{U} = \prod_{\Delta \in I} \mathcal{M}_\Delta / \mathcal{U} \models T\).

Let \(\sigma \in T\). Then for \(\Delta \in I\), \[ \Delta \in \hat{\sigma} \; \Rightarrow \; \sigma \in \Delta \; \Rightarrow \; \mathcal{M}_\Delta \models \sigma \]

Hence \[ \hat{\sigma} \subseteq \{\Delta \in I : \mathcal{M}_\Delta \models \sigma\} \]

Since \(\hat{\sigma} \in E\) and \(E \subseteq \mathcal{U}\), we have \(\hat{\sigma} \in \mathcal{U}\), which implies \[ \{\Delta \in I : \mathcal{M}_\Delta \models \sigma\} \in \mathcal{U} \]

By Łoś’ Theorem, \(\mathcal{M} \models \sigma\).