Note: The following attempted summary consists of follow-up questions to this answer by Asaf Karagila to a related question on MathOverflow. These questions are too long for a comment on that answer, and also too basic for MathOverflow. The original answer is copy-pasted at the bottom of this post.
Questions: Is the following a correct summary?
-
In any model of ZF (with neither AC nor V=L) the set of ultrafilters over $\mathbb{N}$, and the set of free ultrafilters over $\mathbb{N}$, are definable (without parameters) sets?
But it's "undecidable" ("independent"?) whether or not they're the empty set? I.e. there are models of ZF where they are the empty set e.g. here, and models where they are not? I.e. whether or not any (free) ultrafilters over $\mathbb{N}$ exist?
-
In any model of ZF + ultrafilter lemma (including any model of ZFC), the set of ultrafilters over $\mathbb{N}$, and the set of free ultrafilters over $\mathbb{N}$, are not only definable (without parameters) sets, but also provably non-empty?
No elements of those sets ((free) ultrafilters over $\mathbb{N}$) are necessarily definable (without parameters) themselves, but as free variables ranging over a definable (without parameters) set, they are "definable with parameters" = "Gödel constructible"?
Or even if not all of them are "Gödel constructible" = "definable with parameters" in general, at least some of them are? -
In any model of ZFC + V=L, not only are the set of ultrafilters over $\mathbb{N}$ and the set of free ultrafilters over $\mathbb{N}$ definable (without parameters) and non-empty sets, but also at least one element of each set (the "least" according to a specific well-ordering of the universe) is also definable (without parameters)? (Even if not all elements are?)
Clearly all elements of the sets (i.e. (free) ultrafilters over $\mathbb{N}$) are at least "Gödel constructible" (even if not necessarily definable without parameters) given the assumption that V=L.
Note 2: I want to confirm or test my understanding of the knowledge expressed in the answer to a related question on MathOverflow copy-pasted below.
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.
Note 3: I would like to avoid facile answers to the question in the title that assert "because the axiom of choice is invoked that means something has to be not definable", because the situation is actually more subtle than that, as explained in this other MathOverflow answer.
Note 4: I am not sure what to tag this question, so please feel free to fix/edit the tags as you see fit.
Best Answer
Your summary is mostly correct but has some wrong details.
If $X$ is a set, then $ZF$ by itself proves that there exists an ultrafilter on $X$: let $a\in X$ then $\mathcal U_a=\{A\subseteq X\mid a\in A\}$ is an ultrafilter.
An ultrafilter is free if and only if it is not of the above form. Indeed it is possible that there are no free ultrafilters on $\mathbb N$ (or on any set at all).
If $X$ is definable from parameters $q$, and $x\in X$ is definable with parameters $p$ then there exists an ultrafilter on $X$ definable with parameters $q\cup p$ (specifically, $\mathcal U_x$).
In the case $p=q=\emptyset$ then that ultrafilter is definable without parameters.
Note that $\mathbb N$ is definable without parameters and any $a\in \mathbb N$ is definable without parameters, so any ultrafilter on $\mathbb N$ that is not free is definable without parameters.