# Applications of ultrafilters

I'm looking for some interesting applications of ultrafilters and also everything of interest involving ultrafilters. Do you know some applications or interesting things involving ultrafilters?

I'm at the beginning, so I'd prefer some applications that also a beginner could read.

• You may refer to the hyperreal numbers. See the details at en.wikipedia.org/wiki/…. This special number system enables us to work with genuine infinites and infinitesimals with sound logical background. – Sangchul Lee Apr 27 '11 at 16:30
• Maybe this piece from Tao's blog contains something you find interesting. – t.b. Apr 27 '11 at 16:44

## 7 Answers

Ultrafilters can be also be used to prove Arrow's impossibility theorem. In the proof, you show that a certain set of subsets of S, the set of voters is an ultrafilter.

Now, if the base set is finite, this implies that the ultrafilter is principal, and hence a dictator exists. This gives you Arrow's theorem.

On the other hand, if you weaken the assumptions of Arrow's theorem to one where there are infinitely many voters, then, assuming the existence of a non-principal ultrafilter, there is a theorem that the conclusions of Arrow's theorem do not hold.

The proof of Arrow's theorem is the last problem in the chapter on ultrafilters on $\omega$ in the book Problems and Theorems in Classical Set Theory by Komjáth and Totik. In fact, that chapter has a lot of nice problems on ultrafilters and no extra theory is required to read it. The problems however are at times quite hard!

• In case you do not have access to the book, at lest the following paper migh be interesting: P. Komjáth, V. Totik: Ultrafilters, American Mathematical Monthly, 115(2008), 33–44. bolyai.cs.elte.hu/~kope/ultrafilter.pdf – Martin Sleziak Apr 29 '11 at 6:05

My favorite use of ultrafilters is for defining ultralimits. The wikipedia page explains them pretty well, but basically it lets you extend the notion of convergence (of sequences of real numbers, for example) in such a way that every bounded sequence converges, and these limits still respect sums.

You can use ultralimits to make precise statements like "exactly half of the integers are even, and one-third of them are multiples of three". You can do this by defining a "measure" $\mu$ on the integers with the following properties:

• $\mu$ is a function from sets of integers to [0,1]

• $\mu(\mathbb{Z}) = 1$

• $\mu(A \cup B) = \mu(A) + \mu(B)$ for disjoint sets $A,B \subset \mathbb{Z}$

• $\mu$ is translation invariant, ie $\mu(A) = \mu(n + A)$ for all $n \in \mathbb{Z}$

This measure measures the "proportion" each subset of $\mathbb{Z}$ takes up. To define it, we'd like to do something like taking the proportion of larger and larger intervals that are part of the set:

$\mu(A) = \lim_{n\rightarrow \infty} \frac{\lvert A \cap [-n,n]\rvert}{2n}$

This works fine for having the set of even numbers be $\frac{1}{2}$, but this limit doesn't always exist (for example, if $A$ is the set of numbers whose first digit is 1).

So the solution: Use an ultrafilter! Pick an ultrafilter, and use the corresponding ultralimit in place of the limit in the above definition of $\mu$. Now it converges for all $A$, since every sequence of numbers in [0,1] converges in an ultralimit! The invariance under translation is pretty easy to see, and the finite additivity follows from additivity of ultralimits. So we've defined something very close to a uniform probability distribution on the integers, and all it took was the axiom of choice.

You can actually do this trick to form such a measure on any group that is amenable, but getting into a discussion of such groups would probably be going a little off-topic here.

Some of the nicest applications I know of come from Ramsey theory.

The starting idea is easy to present, and it is possible you have encountered it already: Fix a countable infinite set $A$. The infinitary version of Ramsey's theorem says that any graph $G=(A,E)$ with $A$ as set of vertices either contains a copy of the complete graph in countably many vertices, or else, it contains a copy of the empty graph (i.e., no edges) in countably many vertices. A natural question is which of the two cases actually occurs. One would like to say that if the graph has a "large" number of edges then it contains a copy of the complete graph, and if it lacks a "large" number, then it must contain a copy of the empty graph. This notion of largeness can be made precise by introducing a non-principal ultrafilter ${\mathcal U}$ on $A$. Associated to ${\mathcal U}$ there is an ultrafilter ${\mathcal U}^2$ on the set $[A]^2$ of all possible edges among vertices of $A$. Indeed, one proves that if $E\in{\mathcal U}^2$, then $A$ contains a copy of the complete countable graph, and similarly for the other case. You are probably familiar with the characterization of Ramsey ultrafilters that comes from strengthening this notion of largeness.

This proof of Ramsey's theorem is actually the beginning of a very fruitful interaction between the theory of ultrafilters (through the study of Stone-Cech compactifications) and Ramsey theory. The standard reference is the beautiful book:

N. Hindman and D. Strauss, Algebra in the Stone-Cech compactiﬁcation: theory and applications , de Gruyter, Berlin, 1998.

The book begins at a basic level, and it can be used for self-study. If you want a quick introduction to some of the ideas that are used here, I recommend the article by Andreas Blass, "Ultrafilters: Where Topological Dynamics = Algebra = Combinatorics" (Topology Proc. 18 (1993) 33-56). The paper is available at Andreas's webpage.

A collection of blog posts on the subject:

The application which first got me interested (and which spawned my blog posts above) is that ultrafilters can be used to prove the compactness theorem in first-order logic, as well as Tychonoff's theorem.

There is a nice introduction to ultrafilters in Stevo Todorcevic's Topics in Topology (Springer Lecture Notes in Mathematics 1652). Some applications can be found therein. One nice application is the topological proof of the van der Waerden Theorem found in Section 16 of these notes: For every finite partition of the natural numbers $\bigcup_{i=1}^{\infty} A_{i}$ there is an $i$ such that $A_{i}$ contains an arbitrarily long arithmetic progression.

Perhaps the most well-known application is in various ultraproduct constructions exployed in nonstardard analysis. Below are couple very accessible introductions:

Hatcher: Calculus is Algebra. AMM, 1982.

Sorry, I will advertise here my own research. I developed a theory which I call Algebraic General Topology. It is a theory about some specific relations between filters, used for a generalization of general topology.

My research uses filters. Some things in my research such as monovalued funcoids use properties of ultrafilters. However 90% of my research deals with general filters not just ultrafilters.

http://www.mathematics21.org/algebraic-general-topology.html

It looks like that theory of filters was undervalued in the past, and too much efforts (relatively to research of filters) was put into the special case of ultrafilters. So I developed a theory of filters in some chapters of my book, before going to topology.

So, an answer to your specific question: Ultrafilters are used to describe properties of monovalued funcoids (defined in my book) and some other properties of funcoids (look into my book to find which).