Can you get a non-principal ultrafilter on N using Choice but 'avoiding' Zorn's Lemma?

Question

This question is not about the logical relationships between Choice, Zorn's and the Ultrafilter Lemma, but pedagogical. I am teaching a class and want to go as directly as possible from Choice to a non-principal ultrafilter on $\mathbf{N}$.

The Axiom of Choice is much easier to understand than Zorn's Lemma and the definition of a non-principal ultrafilter on the natural numbers is also pretty easy to understand. However, the proof of Zorn's Lemma using the axiom of choice is relatively technical and introducing partially ordered sets and chains just for this purpose feels a little time-consuming.

Question. Is there a sneaky construction of a non-principal ultrafilter on $\mathbf{N}$ that directly uses the axiom of choice but avoids introducing the statement of Zorn's Lemma?

Answer 1

Of course.

• Fix a choice function on $\mathcal{P(P(\Bbb N))}$.
• Start with a non-principal filter, say the co-finite filter.

• By transfinite induction, each time choose a set not in the filter constructed thus far which can be added to the filter; at limit steps take unions. If no such set exists, you have an ultrafilter.

  Namely, if $\cal F_\alpha$ was defined, either $\{A\subseteq\Bbb N\mid A\cup\mathcal F_\alpha\text{ can be extended to a filter}\}$ is empty, in which case we have an ultrafilter on our hands; or we can use our fixed choice function to choose a set from there, and define $\cal F_{\alpha+1}$ to be the filter extending $\cal F_\alpha$ and the chosen set.

• Argue that the construction must stabilize at some point.
• Celebrate by having a beer, or some tea if you prefer.

One key lemma here is that if $\cal F$ is a filter on $X$, and $A\subseteq X$, the $\mathcal F\cup\{A\}$ generates a filter if and only if for all $B\in\cal F$, $A\cap B$ is non-empty.

---

One important remark here is that the axiom of choice "by itself" is nearly useless. It is mostly with transfinite recursion that we can actually use it to construct something.

Answer 2

A free ultrafilter gives a non-measurable subset of the Cantor set in a standard way. There are models of ZF with DC where all subsets of the Cantor set are measurable. In such models no free ultrafilter can exist. So some form of (uncountable) choice is needed to "construct" (via recursion) a free ultrafilter.

Asaf's construction is also how would go about it: enumerate all (infinite) subsets of $\mathbb{N}$ in a well-ordered sequence and check them sequentially.

I don't think it's really more intuitive than Zorn though. If you're teaching a set theory course, Zorn will probably be useful more generally (e.g. to extend bases in linear spaces, construct algebraic completions etc.)

Answer 3

Such a sneaky construction will presumably smuggle in the essence of a proof of either (1) Zermelo's well-ordering theorem or (2) Zorn's Lemma. Let's go with option (1), and let's assume as little prerequisite knowledge as possible.

Given a set of sets $\mathcal{S}$ and $A\in\mathcal{S}$, let $A\downarrow\mathcal{S}$ denote the union of all $B\in\mathcal{S}$ that are proper subsets of $A$.

Given a choice function c on $X=\mathcal{P}(\mathcal{P}(\mathbb{N}))$, call a set $\mathcal{W}$ of filters on $\mathbb{N}$ "well" if every $F\in\mathcal{W}$ has the property that $F$ is the smallest (proper) filter containing $$(F\downarrow\mathcal{W})\cup \{c(X\setminus(F\downarrow\mathcal{W}))\},$$ if such a filter exists. If it does not exist, we instead require $F$ to be the smallest filter containing $$(F\downarrow\mathcal{W})\cup \{\mathbb{N}\setminus c(X\setminus(F\downarrow\mathcal{W}))\}.$$

An example well set of size 3 should clarify to your students the meaning of this definition. Follow up with example well sets of "length" $\omega$ and $\omega+1$.

Now let $\mathbb{W}$ denote the set of all well sets of filters. Assert that $U=\bigcup\bigcup\mathbb{W}$ is an ultrafilter on $\mathbb{N}$. Give the easy proof that $U$ is an ultrafilter if it is a filter. It's not so easy to prove that $U$ is a filter; hand wave and leave the details an as optional or extra-credit project. This will not be completely satisfying, but at least you've given an explicit definition of $U$.