23
$\begingroup$

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.

Improve this question
$\endgroup$
10
  • 6
    $\begingroup$ 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 . $\endgroup$
    – Qiaochu Yuan
    Commented Jul 4, 2011 at 14:04
  • $\begingroup$ @Qiaochu: Since this definition is equivalent to the usual, it is "implicitly" everywhere that ultrafilters are discussed. $\endgroup$
    – Kevin O'Bryant
    Commented Jul 4, 2011 at 14:39
  • 3
    $\begingroup$ 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. $\endgroup$
    – Tom Leinster
    Commented Jul 4, 2011 at 15:36
  • 3
    $\begingroup$ @Tom: great. I never win those contests anyway. :) $\endgroup$
    – Pete L. Clark
    Commented Jul 4, 2011 at 23:01
  • 1
    $\begingroup$ @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}$. $\endgroup$
    – YCor
    Commented May 7, 2013 at 14:20

3 Answers 3

Reset to default
13
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Welcome to MathOverflow! Gerhard "Ask Me About System Design" Paseman, 2013.05.07 $\endgroup$
    – Gerhard Paseman
    Commented May 7, 2013 at 7:27
  • $\begingroup$ 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. $\endgroup$
    – Tom Leinster
    Commented May 7, 2013 at 19:29
  • $\begingroup$ 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.) $\endgroup$
    – Tom Leinster
    Commented May 7, 2013 at 19:32
  • $\begingroup$ 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 $\endgroup$
    – Gerhard Paseman
    Commented May 7, 2013 at 20:57
4
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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.) $\endgroup$
    – Tom Leinster
    Commented Jul 4, 2011 at 14:44
  • $\begingroup$ @Tom Leinster. Ah, yes. I've changed it to the more apparent version. $\endgroup$
    – Greg Graviton
    Commented Jul 4, 2011 at 17:54
-2
$\begingroup$

Google's first page gave me:

Galvin course notes Cor. 2.7...

Qiaochu Yuan blog

Maybe more on the second page?

Improve this answer
$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – Tom Leinster
    Commented Jul 4, 2011 at 17:04
  • $\begingroup$ Lemma 2.10 states it both ways, in a slight disguise. $\endgroup$
    – Emil Jeřábek
    Commented Jul 4, 2011 at 17:59
  • $\begingroup$ 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. $\endgroup$
    – Tom Leinster
    Commented Jul 4, 2011 at 18:11

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .