22

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.

Tom Leinster
  • 27,167
  • 5
    Does my blog count as part of the literature (he said, tongue firmly planted in cheek)? I implicitly give this definition at http://qchu.wordpress.com/2010/12/09/ultrafilters-in-topology/ . – Qiaochu Yuan Jul 04 '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 04 '11 at 14:39
  • I like your post, Qiaochu. Thanks for pointing it out. Let me probe a bit, though: where would you say that you implicitly give this definition? I'm guessing that you're thinking of the last two paras before the heading "Non-principal ultrafilters". I understood that passage as saying that any ultrafilter satisfies the property in the definition I mentioned, but is it also asserting the converse? I didn't get that impression, though maybe it could be read in different ways. – Tom Leinster Jul 04 '11 at 15:34
  • 3
    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 04 '11 at 15:36
  • @Tom: yes, that passage, although you're right that I don't assert the converse. – Qiaochu Yuan Jul 04 '11 at 16:51
  • I don't see how the proposed definition rules out the possibility that $\mathcal{U}$ contains the empty set. Or are you allowing the empty set as a member of your partition? (This is not standard, I believe.) Anyway, is there any advantage to this definition? (You claim it's shorter. I guess it is if you you don't also want to define filters, but that is usually not the case.) – Pete L. Clark Jul 04 '11 at 19:25
  • (I hope Tom doesn't mind if I answer; the two of us have been talking about this a bit recently.) The empty set is being allowed as a member of the "partition"; more properly, we are really considering properties of functions $X \to [n]$ where $[n]$ is an $n$-element set. – Todd Trimble Jul 04 '11 at 20:14
  • Hi Pete. Yup, it's just as Todd said. Sorry, I didn't know there was a usage of the word "partition" that forbade the empty set; I'll clarify that in the question. And yes, when I said it was short I had in mind that you get to skip the definition of filter. (But I'm not really bothered about what's shorter than what; this isn't supposed to be a who's-got-the-shortest-one contest.) – Tom Leinster Jul 04 '11 at 22:05
  • 3
    @Tom: great. I never win those contests anyway. :) – Pete L. Clark Jul 04 '11 at 23:01
  • 1
    @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 07 '13 at 14:20

3 Answers3

12

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 07 '13 at 07: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 07 '13 at 19:29
  • PS to Butch: I'll acknowledge you when I update the paper for which I needed this, http://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 07 '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 07 '13 at 20:57
4

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.

Greg Graviton
  • 1,347
  • 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 04 '11 at 14:44
  • @Tom Leinster. Ah, yes. I've changed it to the more apparent version. – Greg Graviton Jul 04 '11 at 17:54
-2

Google's first page gave me:

Galvin course notes Cor. 2.7...

Qiaochu Yuan blog

Maybe more on the second page?

Gerald Edgar
  • 40,238
  • 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 04 '11 at 17:04
  • Lemma 2.10 states it both ways, in a slight disguise. – Emil Jeřábek Jul 04 '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 04 '11 at 18:11