# How “strong” is the existence of a non trivial ultrafilter on $\omega$?

Obviously the question in the title alone doesn't make sense so I'll develop on the context and then I'll ask my question : Studying $AD$ (axiom of determinacy) I had to prove that $AD$ and $AC$ are incompatible (mod $ZF$). So to prove this I show that under $AC$, there are some undetermined games, and in order to prove this I use the fact that the Fréchet filter can be extended to an ultrafilter (necessarily non principal). As a remark, I thought "This shows that $AD$ is incompatible, not only with $AC$, but also with strictly weaker choice principles, such as the $BPI$ or the statement 'There exists a non-principal ultrafilter over $\omega$' ". Thinking this I wondered how strong that last statement (let $\Omega$ denote said last statement) was, and whether it could imply $BPI$. The answer seems to be "Obviously, no", as $\Omega$ is only about a specific set ($\omega$), whereas the $BPI$ is much more general. But then I wondered whether there was any "general choice principle", strong enough to prove $\Omega$, but not strong enough to prove the $BPI$. I then looked for a way to make "general choice principle" precise in order to look for an answer. So here are my questions :

Is there a satisfactory way to make the notion of "general choice principle" precise, i.e. characterize certain sentences such that $AC$, $BPI$, etc. fall under this scope, but $\Omega$ doesn't ?

If there is, let $\phi$ be such a general choice principle. Can we have $ZF + \phi \vdash \Omega$, but $ZF + \phi$ doesn't prove $BPI$ ?

I first thought of defining it as "$ZF^{-}+ \phi$ ($ZF^{-}$ being $ZF$ minus the axiom of infinity) does not prove the axiom of infinity", but 1.it was only for this particular example, 2. it didn't work, as "$Inf \implies \Omega$" would fall under this notion, but clearly wouldn't be satisfcatory, so a solution would have to be more clever than that.

It seems difficult to make the notion of "general choice principle" precise, but I would guess that the principle "every infinite set admits a nonprincipal ultrafilter" would qualify. If so, then it answers your second question. It obviously implies the existence of a nonprincipal ultrafilter on $\omega$, and, unless I'm making a stupid mistake, it doesn't imply BPI because it follows from the conjunction of "there is a nonprincipal ultrafilter on $\omega$" and countable choice. (The point is that countable choice implies that there are no infinite, Dedekind-finite sets, so every infinite set includes a copy of $\omega$.)

• (You're not making a stupid mistake.) – Asaf Karagila Dec 29 '16 at 15:39
• This is indeed what I would call a "general choice principle" (there is no mention of $\omega$, etc.). So this establishes that (with really big quotation marks) "the existence of a nonprincipal ultrafilter over $\omega$, coming from a general choice principle is stricly weaker than $BPI$". Thanks for your answer ! This was mostly the part I was interested in (the other part was some form of generalization, that could be helpful to solve this) – Maxtimax Dec 29 '16 at 15:48
• @Maxtimax: So countable choice or dependent choice are not considered "general choices principles" since they do mention $\omega$ in their formulation? – Asaf Karagila Dec 31 '16 at 9:49
• Of course what I'm about to answer is not precise at all (that was also one of the goals of the question; as well as the other question you mentionned in your answer), but I would say they are because they allow to "choose" from various sets, sets that themselves need not have any connection with $\omega$. So they do mention $\omega$, but not in the same way as what I called $\Omega$. Although I kind of feel that countable choice wouldn't be a "general choice principle" because it's restricted to countable sequences, whereas dependent choice is about any relation. But it's not precise at all – Maxtimax Dec 31 '16 at 10:54

First of all, not only the existence of a free ultrafilter on $\omega$ is far weaker than $\sf BPI$, even the statement that every filter on $\omega$ can be extended to an ultrafilter on $\omega$ is strictly stronger than "There is a free ultrafilter on $\omega$". This can be an example for a principle that you're looking for: Every filter on $\omega$ can be extended to an ultrafilter. It is weaker than $\sf BPI$, and it proves the existence of a free ultrafilter on $\omega$.

Secondly, there is no "formal definition" of what are choice principles. See What is a Choice Principle, really? for two possible answers, which do not agree at all on the meaning of a choice principle.

Finally, there is a notion of strength when it comes to statement provable from $\sf ZFC$ and not from $\sf ZF$ (or even just "consistent with $\sf ZFC$", like $V=L$ or $\sf GCH$ which imply choice but are not equivalent to it). This is the question whether or not one statement implies the other. So $\sf BPI$ implies $\sf BPI(\omega)$ which implies the existence of a free ultrafilter on $\omega$, and none of these can be reversed. So we have a good notion of being stronger: a stronger principle proves more.

Let me finish by saying that "Every countable family of non-empty sets admits a choice function" cannot prove, nor it is a consequence of $\sf BPI$, so if by a choice principle you mean something like "Every such and such family of sets admits a choice function", then in all likelihood you're expecting a failure; unless you allow something like "There is a choice function from every family which is used in the proof that a filter can be extended to an ultrafilter", or something like that.

• Utlrafilter itself is a choice function of some sort, namely choice of an element within each pair of complementary sets. (And this choice function has to satisfy a couple of extra properties.) – Vladimir Kanovei Mar 19 '17 at 21:41
• Sure, you could say that. But the important part is not the actual choice, but rather the fact that you have coherence between the choices. Saying that an ultrafilter is a choice function is like saying that the Mona Lisa is a drawing, which just happened to have some extra properties. Sure, it's technically correct, but it also sort of misses the point. – Asaf Karagila Mar 19 '17 at 21:43
• You mean that ML has some extra properties and oh by the way it happens to be a drawing somewhere? – Vladimir Kanovei Mar 21 '17 at 21:30
• You apparently don't like your own description of ML as "a drawing, which just happened to have some extra properties" (wording: "some associated artistic and social ideas" would be more adequate as ML is not a scientific term). So I took the liberty to permute the terms, expecting maybe you would like it better. But generally there is an old practice, well-rooted in human culture, to begin a description of something with a generic part and end with a special part (like: homo sapiens, painting known as ML, et cetera). – Vladimir Kanovei Mar 22 '17 at 2:40
• (continuation) Sometimes it takes some effort though to properly figure out the generic affiliation, as I did with the qualiification of ultrafilters as choice functions of certain kind. – Vladimir Kanovei Mar 22 '17 at 2:41