Archive for December, 2010

Ultrafilters in Ramsey theory

We continue our exploration of ultrafilters. Today we’ll discuss the infinite Ramsey theorem, which is the following classical result:

Theorem: Suppose the complete graph K_{\infty} on countably many vertices has its edges colored in one of k colors. Then there is a monochromatic K_{\infty} (i.e. an infinite subgraph all of whose edges are the same color).

The finite Ramsey theorem implies that there is a monochromatic K_n for every positive integer n, but this is a strictly stronger result; it implies not only the finite Ramsey theorem but the “strengthened” finite Ramsey theorem, and by the Paris-Harrington theorem this is independent of Peano arithmetic (although Peano arithmetic can prove the finite Ramsey theorem). Indeed, while the standard proof of the finite Ramsey theorem uses the finite pigeonhole principle, the standard proof of the infinite Ramsey theorem uses the infinite pigeonhole principle, which is stronger; this is part of the subject of a post by Terence Tao which is quite enlightening.

Given a non-principal ultrafilter F on \mathbb{N}, any partition of \mathbb{N} into finitely many disjoint subsets (that is, any coloring) has the property that exactly one of the subsets is in F (that is, has “full measure”), and this subset must be infinite. This subset can, in turn, be colored (partitioned), and exactly one of the blocks of the partition is in F, and it must again be infinite, and so forth. It follows that a non-principal ultrafilter lets us use the infinite pigeonhole principle repeatedly (in fact this is in some sense what a non-principal ultrafilter is), and since this is exactly what is needed to prove the infinite Ramsey theorem we might expect that we could use a non-principal ultrafilter to prove the infinite Ramsey theorem. Today we’ll describe this proof, and then describe how the infinite Ramsey theorem implies the finite Ramsey theorem, which involves a different use of a non-principal ultrafilter on \mathbb{N}.


Read Full Post »

Ultrafilters in topology

Remark: To forestall empty set difficulties, whenever I talk about arbitrary sets in this post they will be non-empty.

We continue our exploration of ultrafilters from the previous post. Recall that a (proper) filter on a poset P is a non-empty subset F such that

  1. For every x, y \in F, there is some z \in F such that z \le x, z \le y.
  2. For every x \in F, if x \le y then y \in F.
  3. P is not the whole set F.

If P has finite infima (meets), then the first condition, given the second, can be replaced with the condition that if x, y \in F then x \wedge y \in F. (This holds in particular if P is the poset structure on a Boolean ring, in which case x \wedge y = xy.) A filter is an ultrafilter if in addition it is maximal under inclusion among (proper) filters. For Boolean rings, an equivalent condition is that for every x \in B either x \in F or 1 - x \in F, but not both. Recall that this condition tells us that ultrafilters are precisely complements of maximal ideals, and can be identified with morphisms in \text{Hom}_{\text{BRing}}(B, \mathbb{F}_2). If B = \text{Hom}(S, \mathbb{F}_2) for some set S, then we will sometimes call an ultrafilter on B an ultrafilter on S (for example, this is what people usually mean by “an ultrafilter on \mathbb{N}“).

Today we will meander towards an ultrafilter point of view on topology. This point of view provides, among other things, a short, elegant proof of Tychonoff’s theorem.


Read Full Post »

Empty sets

Here’s something I had never really thought about before. Any group G has a unique action on the one-element set 1, since there is a unique morphism 1 \to 1. Abstractly, this is because 1 is a terminal object in the category of sets. Now, any group also has a unique action on the empty set 0, since there is also a unique morphism 0 \to 0 (the “empty function”). Abstractly, this is because 0 is an initial object in the category of sets.

This action is quite strange. There are two definitions (that I’m aware of) of what it means for an action of a group on a set to be transitive, and they disagree for this action:

  1. An action of G on X is transitive if, for every x \in X, y \in Y, there exists g \in G such that gx = y. This is vacuously true when X is empty.
  2. An action of G on X is transitive if it has one orbit. This is false when X is empty; there are zero orbits.

Wikipedia takes the stance that a transitive G-set must be nonempty, which I suppose corresponds to supporting the second definition. There is a great reason for doing this: you want transitive G-sets to correspond to conjugacy classes of subgroups of G, and this only works if you can take stabilizers. And you can only take stabilizers if the G-set is non-empty. Instead of using stabilizers you can use the kernel of the action, but then there are two actions – the unique action on 1, and the unique action on 0 – that both correspond to the entire group G.

Edit: Perhaps an even better reason to declare that the empty G-set is not transitive is that otherwise, the decomposition of a G-set into a coproduct of transitive G-sets is not unique. (As I mention in the comments, the empty G-set itself is the empty coproduct.)

These aren’t entirely idle thoughts; there are some major theorems identifying certain categories with the category of certain types of actions of a group G, and as far as I can tell these theorems are wrong as stated in the literature because they don’t take into account the empty case.

It’s likely I’ve said several things on this blog which are false because I didn’t take into account the empty case. Hopefully I’ll do this less in the future.

Exercise: Define the topology on the empty topological space 0. Is it Hausdorff? Compact? Metrizable? Connected? Path-connected? Simply connected? What is its fundamental group? What does the algebra of continuous functions 0 \to \mathbb{R} look like?

Read Full Post »