Math 557 Oct 10

Week 7 - Exercises

Key concepts

(Ultra)filters

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}\).

Reduced products

Given: filter \(\mathcal{F}\) on \(I\) and structures \((\mathcal{M}_i)_{i \in I}\). Let \(M = \prod_{i \in I} M_i\) and 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}\)).

  • 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}}. \]

Łoś’ Theorem

Let \(\mathcal{M}/\mathcal{U} = \prod_{i \in I} \mathcal{M}_i / \mathcal{U}\) be an ultraproduct. 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}. \]

Problems

Exercise 1 (Principal filters) Show that for every \(A \subseteq I\), \[ \{X \subseteq I : A \subseteq X \} \] is a filter on \(I\). Show that it is an ultrafilter if and only if \(|A| = 1\).

Exercise 2 (Finite sets) Show that every ultrafilter on a finite set is principal.

Exercise 3 (Free ultrafilters on infinite sets) Show that a free ultrafilter on an infinite set \(I\) cannot contain any finite subsets of \(I\).

Exercise 4 (Ultrafilter existence) Use Zorn’s Lemma to show that any family \(\mathcal{A} \subseteq \mathcal{P}(I)\) with the FIP can be extended to an ultrafilter \(\mathcal{U}\) on \(I\).

Use this to show that any infinite set has a free ultrafilter.

Exercise 5 (Ultrapoducts with principal ultrafilters) Show that if \(\mathcal{U}\) is a principal ultrafilter on \(I\), then every ultraproduct \[ \mathcal{M}/\mathcal{U} = \prod_{i \in I} \mathcal{M}_i/\mathcal{U} \] is isomorphic to some \(\mathcal{M}_j\), \(j \in I\).

For principal ultrafilters, ultraproducts do not lead to anything new.

Exercise 6 (Ultraproducts of fields) For any prime \(p\) let \(\mathbb{F}_p\) the field with \(p\) elements (of characteristic \(p\)), and let \(\mathcal{U}\) be a free ultrafilter on the set \(P\) of prime numbers.

Show that the ultraproduct

\[\prod_{p\in P} \mathbb{F}_p/\mathcal{U}\]

is a field of characteristic \(0\).

Ultrapowers

If we take an ultraproduct over the same structure \(\mathcal{M}\) along an index set \(I\), we call this an ultrapower, denoted by \[ \mathcal{M}^I/\mathcal{U} \]

Let \(\mathcal{U}\) be a free ultrafilter on an (infinite) set \(I\).

  • Show that the map \(j: b \mapsto (b)_{i \in I}/\mathcal{U}\) defines an elementary embedding of \(\mathcal{M}\) into \(\mathcal{M}^I/\mathcal{U}\) (i.e. it is injective and the image is an elementary substructure).

  • Show that if \(\mathcal{M}\) is infinite, \(j\) is not a surjection.

If we apply this to \(\mathbb{N}\) in the language of arithmetic, this yields another way to obtain non-standard models of arithmetic.

Further explorations

Lindenbaum-Tarski algebra

Given a language \(\mathcal{L}\), define an equivalence relation of the set of all \(\mathcal{L}\)-sentences by \[ \sigma \sim \tau \; \iff \; \vdash \sigma \leftrightarrow \tau \]

The equivalence classes will then form a Boolean algebra, the Lindenbaum-Tarksi algebra \(\mathcal{B}\) with the operations \[ \begin{aligned} [\sigma] \land [\tau] & := [\sigma \land \tau]\\ [\sigma] \lor [\tau] & := [\sigma \lor \tau] \\ \neg[\sigma] & := [\neg \sigma] \end{aligned} \] The bottom element is \(0 :=[\sigma \land \neg \sigma]\), the top element is \(1:= [\sigma \lor \neg \sigma]\).

We can define an order by putting \([\sigma] \leq [\tau] : \iff \vdash \sigma \to \tau\). (This corresponds to the order that is defined on any Boolean algebra via \(a \leq b :\Leftrightarrow a = a \land b\).)

A filter on a Boolean algebra is defined in the same way it is defined on a set \(I\) (in fact, a filter on a set \(I\) is simply a filter on the Boolean algebra induced on its power set by taking intersections, unions, and complements): \(F \subseteq \mathcal{B}\) is a filter if it does not contain the bottom element, is closed under \(\land\) and closed upward under \(\leq\).

  • Show that if \(T\) is a deductively closed, consistent \(\mathcal{L}\)-theory, the set \[ \{ [\sigma] : \sigma \in T \} \] is a filter in \(\mathcal{B}\).

  • Show that if \(T\) is complete, the above filter is an ultrafilter.

Keisler-Shelah Theorem

From Łoś’ Theorem, we know that if two ultrapowers are isomorphic, then the original structures are elementary equivalent. Remarkably, the converse holds, too, and hence gives an algebraic characterization of elementary equivalence.

Theorem 1 (Keisler-Shelah) For any two structures \(\mathcal{M}, \mathcal{N}\), \[ \mathcal{M} \equiv \mathcal{N} \; \iff \; \text{ there exists an index set $I$ and an ultrafilter $\mathcal{U}$ on $I$ such that } \mathcal{M}^I/\mathcal{U} \cong \mathcal{N}^I/\mathcal{U} \]

Other interesting directions