22
$\begingroup$

Is there a diagonal argument to show that if $x$ is infinite then ${\cal P}(x)$ (the power set of $x$) is smaller than $\beta x$ (the set of ultrafilters on $x$)?

(Added later. I tried commenting but it wouldn't let me!)

My reason for interest in this was roughly as follows. With AC one can prove that an infinite set $X$ has $2^{2^{|X|}}$ ultrafilters. If choice fails very badly then there might only be $|X|$-many. I was hoping that there might be a diagonal construction lurking in the background which can feed off the choice principles one supplies. As my correspondents know, i spend a lot of time thinking about Quine's NF, and one question there is: how many ultrafilters are there on the universe? If every ultrafilter is principal then very few, yes. But if there are nonprincipal ufs at all, is there some elementary argument available to show that there must be as many of them as there are sets? If there is such a diagonal construction i'd like to know. It could be useful paedogogically, too.

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ Hi Thomas. Since the answers by Joel Hamkins and Asaf Karagila indicate that in the absence of the axiom of choice there need not be such diagonal argument, you can (re)pose your question by asking (1) In the context of ZFC, is there a such a diagonal argument (after all, many diagonal arguments--unlike Cantor's original one--take advantage of well-orderings, e.g., the construction of a Bernstein subset of reals). (2) Can Specker's proof of the failure of AC in NF be finetuned so as to show that in NF the universe does not carry a nonprincpal ultrafilter? $\endgroup$
    – Ali Enayat
    Commented Apr 8, 2018 at 2:08

2 Answers 2

Reset to default
21
$\begingroup$

I think there can be no such argument, for the following reason.

It is consistent with ZF that the statement isn't true, since $x$ might be an amorphous set, a set for which every subset is either finite or co-finite. In this case, every ultrafilter either contains a finite set, in which case it must be the principal ultrafilter concentrating on a point of $x$, or else it is exactly the cofinite filter, which is an ultrafilter when $x$ is amorphous. Thus, the number of ultrafilters on an amorphous set $x$ is precisely $x+1$, which is strictly smaller than $2^x$.

So any proof of the statement would involve a choice principle, and this would seem to indicate that it couldn't be a purely diagonal argument.

Improve this answer
$\endgroup$
9
  • 1
    $\begingroup$ +1. And the "germ" for the obvious diagonal proof, the existence of a size-$\mathcal{P}(x)$ independent family of subsets of $x$, already gives you the result directly. $\endgroup$
    – Noah Schweber
    Commented Apr 6, 2018 at 18:03
  • $\begingroup$ A more direct argument would be "there might not be any free ultrafilters", as I indicate in my answer. But amorphous sets are great examples of this odd behavior of "just add one". $\endgroup$
    – Asaf Karagila ♦
    Commented Apr 6, 2018 at 22:04
  • $\begingroup$ @AsafKaragila Sure, that is of course just as good. Meanwhile, I think amorphous sets may be more widely known to be consistent with ZF. $\endgroup$
    – Joel David Hamkins
    Commented Apr 6, 2018 at 23:41
  • 2
    $\begingroup$ (Just a minor general remark: One might ask why amorphous sets are not still an answer to the question, even when assuming BPI. After all, they have ultrafilters that are constructed pretty much by hand. Well, it turns out that BPI implies that every set can be linearly ordered, but an amorphous set cannot be linearly ordered.) $\endgroup$
    – Asaf Karagila ♦
    Commented Apr 7, 2018 at 9:09
  • 1
    $\begingroup$ Just an interjection that the theorem that there are non-determined games is an example of a diagonalisation argument requiring AC, at least if you allow an argument to be a diagonalisation when you do the diagonalisation by recursion and rely on Choice to well-order the set. $\endgroup$
    – Chris Le Sueur
    Commented Apr 8, 2018 at 1:25
15
$\begingroup$

Even without amorphous sets, this cannot happen.

Suppose there are no free ultrafilters on some infinite set $x$, then $\beta x$ has a natural bijection with $x$. Which is strictly smaller than $\mathcal P(x)$, as you very well know.

And of course, this is consistent for $x=\omega$, and for $x$ being any infinite set.

Improve this answer
$\endgroup$
3
  • $\begingroup$ I've edited the question.... $\endgroup$
    – Thomas Forster
    Commented Apr 7, 2018 at 9:21
  • $\begingroup$ for some reason the system wouldn't allow to post that edit as a comment(!!!) $\endgroup$
    – Thomas Forster
    Commented Apr 7, 2018 at 9:22
  • $\begingroup$ Well, it's a fairly long edit... $\endgroup$
    – Asaf Karagila ♦
    Commented Apr 7, 2018 at 9:59

You must log in to answer this question.

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