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.
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 compactification: 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.
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!