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.)

  • 1
    $\begingroup$ $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. $\endgroup$ – Martin Jun 20 '13 at 10:10
  • $\begingroup$ 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$.) $\endgroup$ – 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.

  • $\begingroup$ 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]$. $\endgroup$ – 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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.