# An ultrafilter is a set of subsets containing exactly one element of each finite partition: reference request

There are probably dozens of ways of defining "ultrafilter". The definition I've seen most often involves first defining "filter", then declaring an ultrafilter to be a maximal filter.

But there's another, shorter way to state the definition:

Let $X$ be a set. An ultrafilter on $X$ is a set $\mathcal{U}$ of subsets such that for all partitions $$X = X_1 \amalg \cdots \amalg X_n$$ of $X$ into a finite number $n \geq 0$ of subsets, there is exactly one $i$ for which $X_i \in \mathcal{U}$.

I'd be amazed if this wasn't in the literature somewhere, but I haven't been able to track it down. Can anyone help?

Actually, there's an even more economical definition: instead of allowing $n$ to be any natural number, you take it to be 3. Thus, the condition is that whenever $X = A \amalg B \amalg C$, exactly one of $A$, $B$ and $C$ is in $\mathcal{U}$. (The same thing works with 4, or 5, etc., though not with 2.) I'm mostly interested in the version with arbitrary $n$, which seems more natural, but if you've seen the $n = 3$ version in the literature then I'd like to hear about that, too.

Edit To be clear, when I use the word "partition" I don't mean to imply that the sets $X_i$ are nonempty. I just mean a family of pairwise disjoint sets $X_i$ whose union is $X$. They can be empty.

• Does my blog count as part of the literature (he said, tongue firmly planted in cheek)? I implicitly give this definition at qchu.wordpress.com/2010/12/09/ultrafilters-in-topology . – Qiaochu Yuan Jul 4 '11 at 14:04
• @Qiaochu: Since this definition is equivalent to the usual, it is "implicitly" everywhere that ultrafilters are discussed. – Kevin O'Bryant Jul 4 '11 at 14:39
• By the way, Qiaochu, I don't think you need to plant your tongue in your cheek. In my opinion, blog posts (and MO answers) should be taken absolutely seriously when it comes to attributing priority. On the other hand, I'd bet a large amount that this characterization of ultrafilters was found well before either of us was born. – Tom Leinster Jul 4 '11 at 15:36
• @Tom: great. I never win those contests anyway. :) – Pete L. Clark Jul 4 '11 at 23:01
• @Pete: write $X=X_1\sqcup X_2\sqcup X_3$ where $X_1=X$ and $X_2=X_3=\emptyset$. For a unique $i$ we have $X_i\in\mathcal{U}$, so necessarily $i=1$ (otherwise uniqueness would fail). So $\emptyset\notin\mathcal{U}$. – YCor May 7 '13 at 14:20

You can find that characterization (even with n = 3), as well as the generalization to $\kappa$-complete ultrafilters, in: Fred Galvin and Alfred Horn, Operations preserving all equivalence relations, Proc. Amer. Math. Soc. 24 (1970), 521-523.

• Welcome to MathOverflow! Gerhard "Ask Me About System Design" Paseman, 2013.05.07 – Gerhard Paseman May 7 '13 at 7:27
• Excellent. Thanks very much. For the sake of precision, let me add that they don't quite do the case $n=3$ in the sense described in my question. They do show that if a set $\mathcal{U}$ of subsets of $X$ satisfies the partition condition for all $n\leq 3$, then $\mathcal{U}$ is an ultrafilter. But they seem not to observe that it suffices to require it for $n=3$ (which implies it for $n=0,1,2$). Quite possibly they knew it but just didn't think it was worth mentioning. – Tom Leinster May 7 '13 at 19:29
• PS to Butch: I'll acknowledge you when I update the paper for which I needed this, arxiv.org/abs/1209.3606. Forgive the impertinence, but is Butch Malahide your real name? Feel free to contact me by email. (I'd contact you myself, but there's no address on your profile.) – Tom Leinster May 7 '13 at 19:32
• Tom, I've seen postings by a Butch Malahide on other fora, which may help you get in touch with him/her/it. In this day and age, referring to MathOverflow users by number should be socially acceptable. Gerhard "User 3528. Aliases 3206, 3371..." Paseman, 2013.05.07 – Gerhard Paseman May 7 '13 at 20:57

The alternate formulation is closely related to the following fundamental definition from Ramsey Theory

Definition: Let $\phi : 2^X \to \lbrace\text{true},\text{false}\rbrace$ be a property pertaining to subsets of the set $X$. The property $\phi$ is called partition regular if, for every partition $$X = X_1 \uplus X_2 \dots \uplus X_n$$ we have $\phi(X_i)$ for at least one $i$.

Clearly, every ultrafilter corresponds to a partition regular property, $\phi(Y) = Y\in\mathcal U$. In the other direction, it is a reasonably easy exercise to show that every partition regular property is given by a collection of ultrafilters $\phi(Y) = \bigvee \lbrace Y \in \mathcal U : \mathcal U\rbrace$. See for example theorem 3.11 in Hindman & Strauss "Algebra in the Stone-Čech compactification".

That said, I've never seen the formulation with fixed $n$, like $n=3$, before.

• Thanks, Greg. To save others wondering: by Bool you mean a two-element set {true, false}, if I'm not mistaken. (My first guess was that you meant the category of Boolean algebras.) – Tom Leinster Jul 4 '11 at 14:44
• @Tom Leinster. Ah, yes. I've changed it to the more apparent version. – Greg Graviton Jul 4 '11 at 17:54

Google's first page gave me:

Galvin course notes Cor. 2.7...

Qiaochu Yuan blog

Maybe more on the second page?

• Gerald, either I'm not seeing what you're seeing or you're misunderstanding my question. Cor 2.7 of Galvin states that if a set of subsets of X is an ultrafilter, then it satisfies the partitioning property that I mentioned. But it doesn't state the converse - which is the less obvious half. Re Qiaochu's post, see the comments below my question. – Tom Leinster Jul 4 '11 at 17:04
• Lemma 2.10 states it both ways, in a slight disguise. – Emil Jeřábek Jul 4 '11 at 17:59
• Thanks, Emil. That's pretty close, though it's not a totally trivial disguise, since in Defn 2.9 he doesn't constrain the union of A_1, ..., A_n to be X. Of course there's nothing difficult about the equivalence between the definition I mentioned and the standard one. It's just a matter of finding a reference where someone has actually said it. – Tom Leinster Jul 4 '11 at 18:11