# Cardinality of an ultrafilter

If $\mathscr F$ is an ultrafilter on an infinite set $M$, then it can be shown that $|\mathscr F|=2^{|M|}$.

We know that for each subset $A\subseteq M$ we have $A\in\mathscr F$ or $M\setminus A \in \mathscr F$. In this way we can divide the power set $\mathscr P(M)$ into two disjoint parts $\{A\subseteq M; A\in\mathscr F\}$ and $\{A\subseteq M; M\setminus A\in\mathscr F\}$, both of them have cardinality $|\mathscr F|$.

Thus we have $$|\mathscr F|=|\mathscr F|+|\mathscr F|=|\mathscr P(M)|=2^{|M|}.$$

Here we have used that $a+a=a$ for infinite cardinals; which uses axiom of choice. (At least the proof of this fact based on $a\le a+a \le a\cdot a=a$ uses AC.)

Is there an argument showing $|\mathscr F|=2^{|M|}$ without using AC?

(I am aware that already the existence of free ultrafilters can be considered a weaker form of AC, but I am not sure whether it is sufficiently strong to imply $a+a=a$. Additionally, the above argument makes sense for principal ultrafilters, too.)

• $a + a = a$ is Form 3 and the Boolean Prime Ideal theorem is Form 14 in Howard-Rubin. There are models in which Form 14 holds but Form 3 is false and vice versa. – Martin Jun 20 '13 at 10:10
• And BPI is equivalent to UFT; so it implies existence of a free ultrafilter. So this shows that the same argument cannot be repeated in ZF. (Knowing that an ultrafilter exists is not enough to prove $a+a=a$.) – Martin Sleziak Jun 20 '13 at 10:13

The amount of choice used can be reduced to the statement "Dedekind-infinite is equivalent to infinite" (where a set $A$ is Dedekind-infinite if there is an injection $A \to A$ that is not surjective). I don't know if it can be reduced further than this.

NB. ${\sf AC}_\omega$, the Axiom of Countable Choice, is strictly stronger than the statement above, so it's already a very "weak" assumption.

Manifestly $|\mathscr F| \le 2^{|M|}$; we just use the inclusion.

Now, fix a non-surjective injection $f: M \to M$; then for $A, B \subseteq M, f[A] = f[B]$ implies $A = B$. Pick $m \in M \setminus f[M]$.

Now we define $g: 2^M \to \mathscr F$ by:

$$g(A) = \begin{cases} f[A] & \text{if } f[A] \in \mathscr F \\ f[A]^c & \text{if } f[A] \notin \mathscr F \end{cases}$$

Because $m \notin f[M]$, we have that $m \in g(A) \iff f[A] \notin \mathscr F$. This means that we cannot have $f[A] = f[B]^c$ for $A, B \subseteq M$, whereas $f[A] = f[B]$ and $f[A]^c = f[B]^c$ are prohibited by the injectivity of $f$.

Thus $g$ is injective, and we conclude that $\mathscr F$ and $2^M$ are equinumerous by Cantor-Schröder-Bernstein.

• You don’t really need the observation that $m\in g(A)$ iff $f[A]\notin\mathscr{F}$. You just need the fact that $m\notin f[A]$ for any $A\subseteq M$: $m\notin f[B]$, so $m\in M\setminus f[B]$, which therefore can’t be $f[A]$. – Brian M. Scott Jun 20 '13 at 10:53

You can't prove that an ultrafilter has cardinality $2^M$ without the axiom of choice, and here is a lovely counterexample:

Let $A$ be an amorphous set, then co-finite filter $\cal F$ is an ultrafilter (because every set is finite or co-finite). However $\mathcal P(A)$ is a Dedekind-finite, and clearly $\mathcal F\subsetneq\mathcal P(A)$ and therefore has a smaller cardinality.

• Together, our answers place "$|\mathscr F| = 2^{|M|}$ for all ultrafilters" nicely between "there exists an amorphous set" and "infinite implies Dedekind-infinite". Nice. :) – Lord_Farin Jun 20 '13 at 11:22
• @Lord_Farin: One can easily see that this is really a closer bound to "The power set of an infinite set is Dedekind-infinite". – Asaf Karagila Jun 20 '13 at 11:29