# Given a finite collection of disjoint subsets of $I$ must every ultrafilter on $I$ contain exactly one?

The title pretty much contains the question, but here's some elaboration:

The following is one of the first results one encounters while learning about Ultrafilters.

Fact: If $\mathfrak{U}$ is an ultrafilter on an index set $I$, and $X\subset I$, then exactly one of $X$ and $I\backslash X$ is in $\mathfrak{U}$.

Question: Can this be generalized to a collection $X_{1}, ... X_{n}$ of disjoint subsets of $I$ for any $n\geq 1$? That is, if $\mathfrak{U}$ is an ultrafilter on $I$, then there is exactly one value of $j\in\{1,...,n\}$ such that $X_{j}\in \mathfrak{U}$?

I haven't been able to find it in the literature anywhere or prove it myself (though I thought I did briefly) so I'm beginning to suspect it's false in general.

Second Question: If the answer to the first question is false, is it true if $\mathfrak{U}$ is an ultrafilter on $\mathbb{N}$ containing the order filter?

• Yes, and in fact one can define ultrafilters this way. See, for example, Proposition 1.5 in arxiv.org/abs/1209.3606. May 25 '15 at 23:09
• @QiaochuYuan: You need the $X_i$ to be a partition. This is not what the OP asked (but it may be what they meant). May 25 '15 at 23:16
• A partition is what I intended to start with, but forgot to mention. Thanks to all for the great answers.
– roo
May 25 '15 at 23:59
• I was not sure whether to tag this (elementary-set-theory) or (set-theory). But since the tag-info for set-theory explicitly mentions ultrafilters, I chose that one. Jul 11 '16 at 8:02
• Jul 15 '16 at 16:01

If $X_1, \dots, X_n$ is a collection of disjoint sets with $\bigcup_{i=1}^nX_i = I$, then $X_k \in \mathfrak{U}$ for precisely one $k$.

Note that for each $k$, either $X_k \in \mathfrak{U}$ or $\bigcup_{i \neq k}X_i \in \mathfrak{U}$. If $X_k \not\in \mathfrak{U}$ for all $k$, then $\bigcup_{i\neq k}X_i \in \mathfrak{U}$ for every $k$, and so the intersection of such sets would also belong to $\mathfrak{U}$. This is a contradiction as the intersection is empty, i.e. $\bigcap_{k=1}^n\bigcup_{i\neq k}X_i = \emptyset$. Therefore, there exists $k \in \{1, \dots, n\}$ such that $X_k \in \mathfrak{U}$. If there were $l \in \{1, \dots, n\}$, $l \neq k$, with $X_l \in \mathfrak{U}$, then $X_l\cap X_k \in \mathfrak{U}$, but this intersection is empty, so no such $l$ exits. Therefore, $k$ is unique.

Note, you need the sets $X_i$ to cover $I$. If they don't cover $I$, choose $m \in I\setminus\bigcup_{i=1}^nX_i$ and consider the principal ultrafilter $\mathfrak{U}_m$. As $m \not\in X_i$ for all $i$, $X_i \not\in \mathfrak{U}_m$ for all $i$.

Let $X_1,X_2,\dots, X_n$ be a finite collection of sets (not necessarily pairwise disjoint) such that the union $X_1\cup X_2\cup \cdots\cup X_n$ is in the ultrafilter. Then at least one of the $X_i$ is in the ultrafilter. If the $X_i$ are pairwise disjoint, then exactly one of the $X_i$ is in the ultrafilter. The proof is straightforward, by induction.

Added: From comments, it became clear that the OP knew the standard proof that if $D$ is an ultrafilter on the index set $I$, then $X$ or $X^c$ is in $D$. The fact that if the union $X_1\cup X_2$ is in $D$, then $X_1$ or $X_2$ is in $D$ follows. For let $O$ be the "rest" of $I$. If $X_1$ is not in $D$, then its complement $X_2\cup O$ is in $D$. Also, we know that $X_1\cup X_2$ is in $D$. Now note that $X_2=(X_2\cup O)\cap(X_1\cup X_2)$, so $X_2\in D$.

Remark: I think it helps the intuition to think of an ultrafilter as defining a two-valued "measure" $\mu$ on the collection of subsets of $I$, where $\mu(X)=1$ if $X$ is in the ultrafilter, and $\mu(X)=0$ otherwise. The "measure" is almost always not a real measure, since it is ordinarily not countably additive. But it is finitely additive. The finite additivity makes the answer to your question clear. If the $X_i$ all had measure $0$, their union would have measure $0$.

• It is the intuition you describe that led me to guess that the result might be true. I could not come up with a proof, however. Thanks for your additional information!
– roo
May 26 '15 at 1:12
• To see how easy the induction is, let's do it for $3$ sets. Let $X_1\cup X_2\cup X_3$ be in the ultrafilter $D$. Then $(X_1\cup (X_2\cup X_3))\in D$. By the $n=2$ case, either $X_1\in D$, and we are finished, or $(X_2\cup X_3)\in D$, in which case again by the $n=2$ case we are finished. May 26 '15 at 1:41
• I agree that the induction part of the proof is indeed easy. But you are using the following lemma, which I think is the tricky part: If $X_{1}\cup X_{2}\in \mathfrak{U}$, with $X_{1}\cap X_{2} = \phi$, then exactly one of $X_{1}$ or $X_{2}$ is in $\mathfrak{U}$. This is slightly stronger than the fact I mentioned, and cannot be proved in quite the same way (using a brief maximality argument). The lemma clearly follows immediately from Michael Albanese's argument above, but I do not see an easy way to get it directly.
– roo
May 26 '15 at 1:55
• That it cannot be both is obvious, for part of the usual definition of a filter $D$ is that $\emptyset\not\in D$. For the proof that at least one is, it depends on the definition of ultrafilter. If we define it as a maximal filter, one shows that if neither $A$ nor $A^c$ is in $D$, then $A$ can be added to $D$, along with all intersections of elements of $D$ with $A$, and their supersets, to form a larger filter $D'$. May 26 '15 at 2:06
• Is it the part $O$ "outside" $X_1\cup X_2$ that bothers you? If $X_1$ is not in $D$, then its complement $X_2\cup O$ is in $D$, and by assumption $X_1\cup X_2$ is in $D$, so the intersection of $X_2\cup O$ and $X_1\cup X_2$ is in $D$, that is, $X_2$ is in $D$. May 26 '15 at 3:54

It is true, granted the sets form a partition of $I$. Otherwise it is easy to come by counterexamples, simple consider a few singletons and a free ultrafilter.

The proof is simple by induction.