Ultraproducts

As I suggested, the set of cofinite subsets of an infinite set \(I\) forms a filter known as the Frechét filter, which we can easily prove. Let \(D = \{X \subseteq I \mid I\setminus X \text{ is finite}\}\). Then we have:

1. \(I \in D\), since \(I\setminus I = \emptyset\) is finite. Likewise \(I \setminus \emptyset = I\) is infinite, so \(\emptyset \notin D\).
2. If \(A \in D\), so \(A\) is cofinite, and \(A \subseteq B\), then \(I\setminus B \subseteq I \setminus A\), so \(B\) is also cofinite.
3. If \(A, B \in D\) are cofinite, then \(I\setminus (A \cap B) = I\setminus A \cup I \setminus B\) is the union of two finite sets, and hence also finite.

One useful tool for creating filters comes from the finite intersection property.

Now we can make them ultra.

This is a weird property. For example, consider the Frechét filter \(D\) on \(\omega\). This is not an ultrafilter as, for instance, neither the set of even nor odd numbers are in \(D\). This makes sense, as it doesn’t make much sense to say that either the even or the odd numbers are “almost all” of the natural numbers. However, we need this property in order to prove Łoś’s theorem later down the line, which is essential for ultraproducts to be useful.

It’s pretty hard to come up with concrete ultrafilters (usually impossible, in fact), but there are some easy ones, known as the principal ultrafilters. Given a set \(I\) and a particular \(x \in I\), define \(D = \{X \subseteq I \mid x \in X\}\). We can easily see that \(D\) is an ultrafilter.

1. \(x \in I\), so \(I \in D\), and \(x \notin \emptyset\), so \(\emptyset \notin I\).
2. If \(A \subseteq B\) and \(x \in A\), then \(x \in B\).
3. If \(x \in A\) and \(x \in B\), then \(x \in A \cap B\).
4. Given \(X \subseteq I\), if \(x \in X\), then \(X \in D\). Otherwise \(x \in I \setminus X\), so \(I \setminus X \in D\).

Remarkably, there are non-principal ultrafilters. Not only that, but the ultrafilter theorem says that we can always extend a filter to an ultrafilter!

What makes this proof remarkable is, since the proof is basically just a single application of Zorn’s lemma, it is extremely non-constructive. Given a filter, we can extend it to an ultrafilter, but this ultrafilter is not even remotely unique, and impossible to describe! Despite this, and the fact that the choice of ultrafilter does impact the resulting ultraproduct, the details of the ultrafilter chosen are completely irrelevant most of the time. Usually it just matters that a non-principal ultrafilter exists. As we will see shortly, every non-principal ultrafilter contains the cofinite sets, which is usually all we need.

There are some facts about non-principal ultrafilters that are very easy to state and prove, but will come in handy.

First, if an ultrafilter contains a singleton set, then it must be principal. Suppose \(\{x\} \in U\). Then certainly every set containing \(x\) is in \(U\). Conversely, let \(X \in U\). If \(x \notin X\), then \(x \in I \setminus X\), so \(X\) and \(I \setminus X\) are in \(U\), hence \(X \cap I \setminus X = \emptyset \in U\), a contradiction.

Furthermore, if an ultrafilter contains a finite set, then it must be principal. Suppose \(U\) contains \(\{x_1, \dots, x_n\}\), and suppose \(n\) is the smallest cardinality of \(U\)’s members. Then consider \(\{x_1\}\). Since \(U\) is an ultrafilter, either \(\{x_1\} \in U\) and hence \(U\) is principal by the previous lemma, or \(I \setminus \{x_1\} \in U\). In the latter case, if \(n > 1\), then \(\{x_2, \dots, x_n\} = I \setminus \{x_1\} \cap \{x_1, \dots, x_n\} \in U\) is a smaller finite set contained in \(U\) contradicting the minimality of \(n\).

As a corollary, we can note that every non-principal ultrafilter \(U\) must contain every cofinite set, as otherwise \(U\) would contain a finite set and hence be principal. Conversely, if an ultrafilter \(U\) contains every cofinite set, it must be non-principal, since, in particular, \(I \setminus \{x\} \in U\) for every \(x \in I\), so \(\{x\} \notin U\) and principal ultrafilters contain a singleton set.

Since the Frechét filter always exists and can be extended to a non-principal ultrafilter, as it contains every cofinite set, and all that matters in an ultraproduct is that the ultrafilter contains all the cofinite sets, we don’t really have to worry about the particular choice of ultrafilter at all, even though the resulting object depends on the choice.

Let \(T\) be a finitely satisfiable theory. Let \(I\) be the set of finite subsets of \(T\). Since \(T\) is finitely satisfiable, for every finite set \(i \in I\), there exists an \(\mathcal{L}\)-structure \(\mathcal{M}_i\) such that \(\mathcal{M}_i \models i\). For each \(\phi \in T\), let \(X_\phi = \{i \in I \mid \phi \in i\}\). The \(X_\phi\) have the finite intersection property (\(\{\phi_1, \dots \phi_n\} \in X_{\phi_1} \cap \dots \cap X_{\phi_n}\)), and thus generate a filter. Extend this filter to an ultrafilter \(U\). Then we have \(\mathcal{M} = \prod_{i\in I} \mathcal{M}_i / U\). I claim \(\mathcal{M} \models T\). Let \(\phi \in T\). Certainly \(\mathcal{M}_i \models \phi\) for every \(i \in X_\phi\), so \(\{i \mid \mathcal{M}_i \models \phi\} \supseteq X_\phi \in U\), so by Łoś’s theorem \(\mathcal{M} \models \phi\).

Isn’t that remarkable? We didn’t have to bother with Henkin constructions or proof systems and Gödel’s completeness theorem. We just glue all the \(\mathcal{L}\)-structures modeling the finite subsets together and average them out and we have a model of \(T\).

Now that we are armed with ultraproducts, let’s look at some really weird constructions. Take \(\mathcal{L}\) to be the language of fields. Then for each prime \(p\), \(\F_p\) is an \(\mathcal{L}\)-structure. Take any ultrafilter \(U\) on the prime numbers. Then we can construct \(K = \prod_p \F_p / U\). This is a very strange \(\mathcal{L}\)-structure. First, since every \(\F_p\) is a field, and that can be expressed in \(\mathcal{L}\), so is \(K\). However, unlike \(\F_p\), \(K\) is characteristic zero. We can see this because for every \(n\), the sentence \(\underbrace{1 + 1 + \dots + 1}_{n \text{ times}} \neq 0\) is true in all but at most one \(\F_p\) and hence true in \(K\) as well. It gets even weirder, however, because \(K\) is uncountable and characteristic zero, but only has a unique extension of every degree, as that is a property expressible in \(\mathcal{L}\) and true of every \(\F_p\).

Things get even weirder too. Pick any elliptic curve with rational coefficients. It is known that the number of solutions in \(\F_p\), \(N_p\), satisfies \(N_p \geq p - 2\sqrt p\), which grows without bound. Hence for any \(n\), all but finitely many fields \(\F_p\) satisfy \(N_p \geq n\). Thus every elliptic curve with rational coefficients has infinitely many solutions in \(K\).

What makes all this so weird is that, purely in terms of first order logic, \(K\) is indistinguishable from a finite field. Everything that is true about all finite fields is true about \(K\). In finite time, you can’t tell that \(K\) isn’t a finite field. For instance, you could keep adding one to try to find its characteristic, but wherever you give up and stop, there are finite fields with larger characteristics. You can check all of its field extensions, and those line up perfectly with what you’d expect from a finite field. You can count solutions to elliptic curves. You could tell that it has a lot of solutions, but you can’t tell in finite time that it has infinitely many, and large finite fields have tons of solutions to elliptic curves as well. But despite this, not only is \(K\) not finite, it’s uncountably infinite and has a lot of bizarre properties that are very different from finite fields, you just can never find out.

This isn’t very important, but it is too absurd and delightful not to share³. There are infinitely many primes \(p\) such that \(\F_p\) has no solution to \(x^2 - 2 = 0\) (follows immediately from quadratic reciprocity and Dirichlet’s theorem). Let \(P\) be the set of these primes. Then if \(U\) is a non-principal ultrafilter containing \(P\), then \(K = \prod_p \F_p / U\) is a pseudofinite field with characteristic zero (hence is an extension of \(\Q\)), where \(x^2 - 2 = 0\) has no root. Thus \(\sqrt 2 \notin K\), and since \(K\) is an extension of \(\Q\), \(\sqrt 2\) must be irrational.

Here’s a weird example. We can glue almost anything with an index together using ultraproducts, so how about \(G = \prod C_n / U\), where \(C_n\) is the cyclic group of order \(n\)? It turns out, the resulting group varies wildly depending on the ultrafilter. No matter what, it will be Abelian, since every cyclic group is Abelian. Furthermore, no matter what it will definitely have elements of infinite order. For every \(k\), all but finitely many of the \(C_n\)’s have an element with order greater than \(k\), so this product will have an element of infinite order (in fact, infinitely many elements of infinite order). The question gets weirder if we ask about torsion elements, since it’s impossible to state that an element has finite order in general in first order logic, but we can ask about specific orders.

So, does \(G\) have an element of order 2? \(G\) having an element of order 2 means \(G \models \exists x\, x\cdot x = e\), which is true if \(\{n \mid C_n \models \exists x\, x \cdot x = e\} \in U\). But \(C_n\) has an element of order 2 if and only if \(n\) is even, so \(G\) has an element of order 2 if and only if the set of even numbers is in \(U\)! The set of even numbers isn’t cofinite, so it depends on the choice of non-principal ultrafilter \(U\). Similar analysis holds for every other order.

We can even choose precisely which finite orders we want. For any natural number \(n\), let \(X_n = n \N\) and \(Y_n = \N \setminus X_n\). The \(X_n\)’s have the finite intersection property, in fact they are closed under finite intersection, so they generate a non-principal ultrafilter \(U_1\). Likewise, the \(Y_n\)’s have the finite intersection property, so they generate a non-principal ultrafilter \(U_2\).

First, let’s look at \(G_1 = \prod C_n / U_1\). The set of even integers is just \(X_2\), so \(G_1\) has an element of order 2, in fact exactly one (since every group with even order has \(\phi(2) = 1\) elements of order 2). Likewise, the set of integers divisible by 3 is \(X_3\), so \(G_1\) also has two elements of order 3. Carrying this logic forward, \(G_1\) has elements of every finite order! More specifically, for every \(n \in \N\), \(G_1\) has \(\phi(n)\) elements of order \(n\). It also has infinitely many elements of infinite order, too! It’s really hard to say much more beyond this about \(G_1\), unfortunately. It is an enormously complicated, uncountably infinite group.

Now let’s consider \(G_2 = \prod C_n / U_2\). This group is much easier to talk about, though it is still quite weird. Unlike \(G_1\) which has elements of every finite order, \(G_2\) only has elements with infinite order, and no elements of any finite order. Things get weirder. Divisibility of groups is not expressible in first order logic, but we can say something about the divisibility of \(G_2\). In order for \(G_2\) to be divisible, we’d want for every \(k\), \[ G_2 \models \forall x\, \exists y\, \underbrace{y \cdot y \cdot \dots \cdot y}_{k\text{ times}} = x. \] Switching gears to \(C_n\), we can say that \(C_n \models \forall x\, \exists y\, y^{k} = x\) if and only if \(k\) and \(n\) are relatively prime. So for a fixed \(k\), we want to see if the set \(Z_k = \{n \mid \gcd(n, k) = 1\} \in U\). Suppose the prime factors of \(k\) are \(p_1\), \(p_2\), \(\dots\), \(p_r\). Then \(Z_k = Y_{p_1} \cap \dots \cap Y_{p_r}\) (\(n\) and \(k\) are relatively prime if and only if \(n\) is not a multiple of any of the prime factors of \(k\)). But then this means that \(C_n\) is a divisible, torsion free, Abelian group! So by the classification of divisible Abelian groups, \(G_2 \cong \Q^{(\mathfrak{c})}\).

A hyperreal number is an equivalence class of sequences of real numbers. The usual real numbers canonically embed in the hyperreals. So, for example, \(d(0) = [(0, 0, 0, 0, \dots)]\). We will abuse notation and often identify real numbers with their image under the canonical embedding, as well as not distinguish, for example, the binary function symbol \(+\), from the function \(+^{\R}\), from the function \(+^{\R^{*}}\), and just use \(+\) for all of them.

By Łoś’s theorem, we immediately get that everything that is true of \(\R\) that is expressible in \(\mathcal{L}\), is also true of \(\R^{*}\). So, for example, the sentence \(\phi = \forall x\, \forall y\, x + y = y + x\) is true in \(\R\), so it is also true in \(\R^{*}\). As such, \(\R^{*}\) is a real ordered field, it has square roots of non-negative elements, every odd degree polynomial has a root, etc.

However, \(\R\) and \(\R^*\) are different. For instance, \(\R\) has the Archimedean Property (for every \(x \in \R\), there exists a natural number \(n\) such that \(n > x\)), while \(\R^{*}\) does not! For instance, consider the hyperreal number \(x = [(0, 1, 2, 3, 4, 5, \dots)]\). Then for any natural number \(n\), all but \(n + 1\) components of \(x\) are greater than \(n\), meaning \(x > n\). In fact, \(x\) is greater than any real number, making it an infinite number.

We already saw that \([(0, 1, 2, 3, 4, 5, \dots)]\) is infinite. Infinitesimals also exist. An example would be \(x = [(1, 1 / 2, 1 / 3, 1 / 4, \dots)]\).

There are some weird hyperreals. Consider \(x = [(1, -1, 1, -1, 1, -1, \dots)]\). Is \(0 < x\)? That depends on the choice of ultrafilter. Fortunately, as we will soon see, every hyperreal is equivalent to a more sane number. It is best not to worry about the sequence representation of hyperreals. There are much more convenient and sensible ways of working with hyperreals purely algebraically.

We will show that \(\approx\) is an equivalence relation, but it will help to have some algebraic tools first.

It turns out that \(\galaxy(0)\) of finite elements is a subring of \(\R^{*}\) with \(\monad(0)\) of infinitesimals being another subring of \(\R^{*}\) and an ideal of \(\galaxy(x)\).

Is it starting to seem nice yet? These infinitesimals play a very similar role to the usual \(\epsilon\)’s and \(\delta\)’s in analysis, but are smaller than every positive real number, so you don’t need to mess around with constantly updating and processing their bounds. In particular, the product of an infinitesimal \(\epsilon\) and a finite number \(a\) is infinitesimal, so if you want \(\epsilon a\) to be small, you don’t need to update your bounds on \(\epsilon\), you just get it to be small for free.

We still have those weird hyperreals that we saw earlier that are hard to characterize. Fortunately, it turns out that every finite hyperreal can be uniquely written as \(r + \epsilon\) for some real number \(r\) and infinitesimal \(\epsilon\).

From here we can really get going. Here’s a list of some easy to prove facts about \(\st\). I encourage the reader to think these through, as they are very easy to prove, and it is very fun to explore these ideas.

Now that we are familiar with the algebra of infinitesimals and the hyperreals, we can use them to develop calculus.

We won’t take this too far, though I strongly encourage you to play around with these ideas if you are interested and translate as much elementary analysis as you can into non-standard analysis, as it is very fun to do.

The fundamental idea of the derivative is considering how a function \(f : \R \to \R\) changes if its input is changed by an infinitesimal amount. We can very easily formulate this idea using infinitesimals.

Note that this requires evaluating a real function on hyperreal inputs. For any function definable in \(\mathcal{L}\), that is to say all the interesting ones, we get its extension into \(\R^{*}\) for free by Łoś’s theorem.

We are very quickly leaving the realm of logic and model theory and entering the domain of nonstandard analysis, so, to quote Michael Penn, this is a good place to stop.