# In $L$, does there exist a definable non-principal ultrafilter on $\mathbb{N}$

The axiom of constructibility $V=L$ leads to some very interesting consequences, one of which is that it becomes possible to give explicit constructions of some of the "weird" results of AC. For instance, in $L$, there is a definable well-ordering of the real numbers (since there is a definable well-ordering of the universe).

Since AC holds true in $L$, the ultrafilter lemma must be true. Does this mean that a definable non-principal ultrafilter on $\mathbb{N}$ exists in $L$, given by an explicit formula?

If so, what is the formula?

-
How about "the $<_L$-least non-principal ultrafilter on $\mathbb{N}$"? – Amit Kumar Gupta Jan 21 '14 at 7:14
Drat, Amit, you beat me! – Noah Schweber Jan 21 '14 at 7:19

Yes, but it's not particularly nice: since $L$ has a definable well-ordering of the sets of reals (in fact, of all of $L$) coming from the $L$-hierarchy itself, there is a formula defining the "least" (in that well-ordering) ultrafilter, $U$.

(This $U$ isn't the only naturally definable ultrafilter in $L$; we could also consider the ultrafilter gotten by going through the infinite sets of natural numbers, in the $L$-order, and throwing in each set that we can - a sort of "greedy algorithm" for building an ultrafilter. This ultrafilter $U'$ would also be definable, and there's no reason for $U'$ to equal $U$. Other tricks exist.)

Note that, while of course there are only countably many definable ultrafilters, we can use the $L$-ordering to produce a definable ultrafilter with any given definable property ("the least ultrafilter with property X") - so there's basically nothing that can be said about the definable ultrafilters.

-
Countably many definable where, and how? Recall the result about pointwise definable models (Hamkins, Linetsky, Reitz). In these models every element is definable. Including all $2^{2^{\aleph_0}}$ ultrafilters. – Asaf Karagila Jan 21 '14 at 16:01
Argh, quite right - that's one of those things that sounds totally innocuous to say, but then someone points out that you need to think about it . . . :) Thanks for reminding me (that's one of my favorite results)! – Noah Schweber Jan 21 '14 at 19:39

Let me emphasize what Noah de-emphasized (by putting it in parentheses) in his answer: Instead of the "really cheap" idea of the first free ultrafilter in $L$-order, one can use the $L$-order of subsets of $\mathbb N$ to greedily construct an ultrafilter. The $L$-ordering of the subsets of $\mathbb N$ is a $\Delta^1_2$ relation with some additional properties (I believe Moschovakis uses the terminology $\Delta^1_2$-good well-ordering). One can then deduce that the greedily constructed ultrafilter is a $\Delta^1_2$ set of subsets of $\mathbb N$.

Since free ultrafilters on $\mathbb N$ never have the Baire property and are never Lebesgue measurable, this shows that the classical results, that analytic and coanalytic sets have the Baire property and are measurable, cannot be extended higher in the projective hierarchy in ZFC (without additional hypotheses like large cardinals or determinacy).

Similar greedy constructions based on the $L$-ordering of the reals produce $\Delta^1_2$ examples of lots of other sets of reals that, in the absence of $V=L$, would be obtained by applying the axiom of choice and thus might not be definable at all. Examples include Hamel bases over $\mathbb Q$, Vitali sets, and Bernstein sets.

-
Regarding the Hamel basis over $\mathbb{Q}$ - very interesting! One thing I've been very curious about is what a basis for the vector space of functions from $\mathbb{R} \to \mathbb{R}$ might look like. Is this constructible in $L$ as well? I can't begin to imagine what these functions would look like. – Mike Battaglia Jan 23 '14 at 7:43
@MikeBattaglia If $V=L$, you can build a basis for the functions $\mathbb R\to\mathbb R$ by similar methods to those in the answers here, but you'd have to use $L$'s well-ordering not of the reals but of the subsets of the reals, so the complexity goes way up. I agree with you that most of the functions in such a Hamel basis would be unimaginable. Note, for example, that the basis would have cardinality $2^{2^{\aleph_0}}$, whereas the number of continuous or even Borel functions is only $2^{\aleph_0}$. – Andreas Blass Jan 23 '14 at 16:54

Generally formulas in set theory are not "very nice". There is very little structure to work with.

We can define when $U$ is a filter over $X$, simply by saying that every element of $U$ is a subset of $X$, and $U$ is closed under superset (below $X$), and under finite intersections (recall that in set theory we can say that within a first-order formula, simply by stating that the intersection over a finite subset of $U$ is in $U$).

Then we can define $U$ as an ultrafilter as a filter which is maximal with respect to inclusion. And $U$ is free if it doesn't contain finite sets, or a singleton, or its entire intersection is empty. Pick your pick.

Finally, from the axiom of choice we can prove that the set of ultrafilters over $\Bbb N$ is non-empty. Therefore using the canonical well-ordering of $L$ we can fully state "the least free ultrafilter over $\Bbb N$". It's just an insanely long formula (especially if you unwind all the recursive definitions everywhere and the abbreviations for subsets, finite, etc.) which is not very pretty.

-