# Any ultrafilter over a finite set is principal

Let $I$ be a finite set. Let $\mathcal{U}$ be an ultrafilter over $\mathcal{P}(I)$. I want to prove that $\mathcal{U}$ is principal.

My work: let $\mathcal{U}=\{S_1,\ldots,S_k\}$. Since $\varnothing\notin\mathcal{U}$ and $S_i\cap S_j\in\mathcal{U}$ for every $i,j$, we have that $S_1\cap\ldots\cap S_k\neq\varnothing$. Let $a\in\displaystyle\bigcap_{1}^{k}S_j$. I claim that $\mathcal{U}=\mathcal{U}_a$, the principal ultrafilter generated by $a$, i.e. that $\mathcal{U}=\{S\mid a\in S\}$. Now, $\mathcal{U}\supseteq\{S\mid a\in S\}$ is obvious. By maximality of ultrafilters, i get $\mathcal{U}=\{S\mid a\in S\}$.

Where is the error?

• Why do you think there's an error? (Except the typo of using $\supseteq$ instead of $\subseteq$?) – Henning Makholm Jan 8 '14 at 14:47
• @HenningMakholm Because I always make mistakes in solving exercises and you have just proven it! – Danae Kissinger Jan 8 '14 at 14:51

So, it's been four years, but for the sake of completeness, I'd like to point out that your answer is indeed correct.

Instead of using maximality, you can use the following result, if you'd like:

Given a set $$X$$ and a filter $$\mathcal{U}$$ on it, then $$\mathcal U$$ is an ultrafilter iff for every $$Y\subseteq X$$, either $$Y\in\mathcal U$$ or $$X\setminus Y\in \mathcal U$$.

From that, take $$X$$ a finite set. Then $$\mathcal{P}(X)$$ is also finite and, therefore, any ultrafilter on $$X$$ is also finite.

Let $$\mathcal U$$ be such an ultrafilter. Since it is a finite filter, $$\bigcap \mathcal U\not=\varnothing$$. Let $$x\in\bigcap\mathcal U$$ and $$\mathcal{U}_x$$ be the principal ultrafilter on $$x$$. Then, as you've said, clearly $$\mathcal U\subseteq\mathcal U_x$$.

Conversely, though, notice that every element $$Y$$ of $$\mathcal U_x$$ either belongs to $$\mathcal U$$, or its complement $$X\setminus Y$$ does. But if $$X\setminus Y\in\mathcal U$$, then $$x\in X\setminus Y$$ (since $$x\in\bigcap\mathcal U$$) and, therefore, both $$Y$$ and $$X\setminus Y$$ contain $$x$$ - a contradiction.

It follows that $$X\setminus Y\not\in\mathcal U$$ and, since $$\mathcal U$$ is an ultrafilter, this implies that $$Y\in\mathcal U$$, which shows that $$\mathcal U_x\subseteq \mathcal U$$ and ends the proof.

EDIT:

Based on a comment by Daniel Schepler, I've decided to add more to this answer.

You can actually prove that $$\mathcal U\subseteq \mathcal P(X)$$ is an ultrafilter iff whenever you write $$X$$ as a disjoint union of (at least!) three sets, precisely one of them is in $$\mathcal U$$. From that, if $$X$$ is finite, we have three cases:

If $$X$$ is a singleton, then there's a unique ultrafilter, which must be principal;

If $$X$$ is a two-point set, then we can use $$X=\{x_1\}\sqcup\{x_2\}$$ and my original answer to conclude that any ultrafilter is either principal over $$x_1$$ or $$x_2$$;

Finally, if $$X$$ has at least three elements, then writing $$X=\{x_1\}\sqcup\{x_2\}\sqcup\cdots\sqcup\{x_n\}$$ and using the fact that $$\mathcal U$$ is ultrafilter, we get that there's a unique $$x_i$$ such that $$\{x_i\}\subseteq \mathcal U$$, and we can then prove that $$\mathcal U$$ is indeed principal over such $$x_i$$.

For more on this, I'd recommend reading Tom Leinster's "Codensity and the ultrafilter monad", specifically Proposition 1.5 on page 5.

• Another approach: first prove that for an ultrafilter $\mathcal{U}$, if $\bigcup_{i=1}^n A_i \in \mathcal{U}$ then $A_i \in \mathcal{U}$ for some $i$. Now, for a finite set $X = \{ x_1, x_2, \ldots, x_n \}$, $\bigcup_{i=1}^n \{ x_i \} = X \in \mathcal{U}$, so... – Daniel Schepler Mar 8 at 18:40