Nonstandard Analysis 1: Ultrafilters

Good news, everybody! Isaac Goldbring has brought out a book dedicated to ultrafilters, in nonstandard analysis and many other subjects: Ultrafilters Throughout Mathematics. Go convince someone to buy it for you.

I have decided that the best way for me to regularly contribute to this blog is to send it in a certain direction. Since I love nonstandard analysis and want to get better at it, that will be the general theme. To start with, I thought I would take a look at those weird and wonderful things, ultrafilters. Although the focus will mainly be the use of these in nonstandard analysis (NSA, from now on), we will also look at some other uses.

First, a definition:

Definition 1.1. A set of subsets $\mathcal{U}$ of some set $S$ is a filter on $S$ if

$\emptyset \notin \mathcal{U}, S\in \mathcal{U}$
$A,B \in \mathcal{U}$ implies $A\cap B\in \mathcal{U}$ .
If $A\in \mathcal{U}$ and $A\subset B$ , then $B\in \mathcal{U}$ .

We are going to consider filters mainly when $S = \mathbb{N}$ .

The idea of a filter was first formulated by Cartan, based on Moore’s nets. Let us recap what a net is. Firstly, we recall that a directed set is a set with a reflexive and transitive relation in which every pair of elements has an upper bound.

Definition 1.2. A function $f:X\to Y$ is a net on $Y$ if $X$ is a directed set.

Since a sequence on a space $X$ is a function $f:\mathbb{N}\to X$ , we see that a net is clearly a generalisation of a sequence, and we can use it to capture ideas of convergence, as we will do with filters. A fundamental idea of filters is that each element is “big” in some sense, and that we will consider two things to be equivalent if they agree on an element of the filter. Accordingly, the conditions on a filter reflect this. The empty set is clearly not big, while the whole set must be. The intersections of two big sets must contain some big thing we are interested in, and a set that is bigger than an already big one must itself be considered big.

If we are going to consider two things the same if they agree on an element of the filter (and only then), they can disagree on at most the complement of that set. By implication, the complement of that set can then not also be part of the filter.

Definition 1.3. A filter $\mathcal{F}$ on a set $S$ is an ultrafilter on $S$ if for each $A \subseteq S$ , either $A \in \mathcal{F}$ or $S\setminus A \in \mathcal{F}$ .

The example usually used to illustrate an ultrafilter is the collection of cofinite subsets of $\mathbb{N}$ , that is, subsets of $\mathbb{N}$ with finite complement.

We are not yet done, because there are ultrafilters that can have “small” elements and that will not be suitable for our purposes. Consider the set of subsets of $\mathbb{N}$ that contain the number 3. Since $3\in \mathbb{N}$ , any two sets that contain 3 have an intersection that contains 3, and any set containing a set containing 3 must contain 3, this collection is a filter. Furthermore, if I give you a subset of $\mathbb{N}$ , and its complement, one, and only one of them can contain 3. Therefore, we have an ultrafilter. However, this is not a very useful filter (for our purposes). For instance, if we were using the ultrafilter to compare subsets of $\mathbb{N}$ , they would be deemed equivalent if both contained 3.

Any ultrafilter of this kind is called a principal ultrafilter. More generally, any ultrafilter generated by a finite set in this way will be deemed such. Since they are clearly no good, we will only deal with non-principal ultrafilters, that is, an ultrafilter that cannot be generated by any finite set. You may also hear people use the term free ultrafilter at times. This can be categorised as a filter that does not contain any finite sets, or as one for which the intersection of all elements is empty. These are equivalent to the condition of being non-principal, and we can use the terms “free” and “non-principal” interchangeably.

You might ask me now to provide an example of a free ultrafilter, which I sadly cannot do. There are all sorts of complicated reasons which I might get into in a later post, but suffice it to say that ZF guarantees that such things exist. However, I cannot write one down. Nevertheless, let us now fix a non-principal ultrafilter $\mathcal{U}$ and look at some things we can do with it.

Ultraproducts. This is a fundamental concept in Robinsonian nonstandard analysis, and our constructs will rest on these. (We will be going into Nelson’s nonstandard analysis later, which does not require ultraproducts.) Suppose that we have an index set $S$ (which we take to be the natural numbers) and a structure $M_i$ for each $i\in S$ . These all need to have the same signature, which is something you need not concern yourself overly much with in our constructions. We form the quotient set

$\prod_{i \in S} M_i / \mathcal{U}$ ,

where $\mathcal{U}$ is some fixed free ultrafilter. Let $S = \mathbb{N}$ (so $\mathcal{U}$ is an ultrafilter on $\mathbb{N}$ and $M_i = \mathbb{R}$ for each $i \in \mathbb{N}$ . If we consider two sequences of reals, they will be identified as the same in the ultraproduct if they agree on an element of $\mathcal{U}$ . Although we cannot give specific elements of $\mathcal{U}$ , we can immediately say that two sequences of reals will be equivalent if they differ on only a finite set, since no finite set can be a member of the ultrafilter in question. Also consider the sequence $x = (x_i)$ where $x_i = 1$ if $i$ is even and zero otherwise as well as the sequence $y = (y_i)$ where $y_i = 0$ if $i$ is even and zero otherwise. Are these two sequences equivalent? Of course not – the set of indices on which they agree is empty. Now, can we say if one is equivalent to the sequence consisting of 1’s only, and the other to a constant sequence of zeroes? By the definition of our ultrafilter, either the set of even numbers or the set of odd numbers (but not both!) must be a member. If the set of even numbers is, then $x$ will be equivalent to a sequence of ones, and $y$ will be equivalent to a sequence of zeroes, and vice versa if the set of odd numbers is. However, that is all we can say – in general, we have no idea which of the two sets will be in our ultrafilter.

Now, what about infinitesimals? In our construction, a sequence tending to zero can be considered an equivalence class. Thus, the sequence $x = (2^{-n})_{n=1}^{\infty}$ can be considered as one infinitesimal, and the sequence $y = (1/n)_{n=1}^{\infty}$ as another. They clearly won’t be equivalent, since they agree nowhere. Indeed, we can speculate that the first one represents, in some sense, a smaller quantity than the second, since it tends to zero quicker. In this way, we can define the relation < by saying that $x < y$ (both representing equivalence classes here) if the set $\{n\in \mathbb{N} : x_n < y_n \}$ belongs to $\mathcal{U}$ . Of course, there is still the same ambiguity as we faced with equality. Suppose that $x = (x_n)$ is a sequence with the value 1 on odd values of $n$ , and with value $2^{-n}$ for even values of $n$ , and let $y = (y_n)$ be the sequence with value 1 on odd values of $n$ and with value $1/n$ on even values of $n$ . Now, we cannot definitely say that $x = y$ , nor can we definitely say that $x<y$ , since we do not know whether our ultrafilter contains the even or the odd numbers. However, we can say for certain that $x\leq y$ , at least…