Existence (or non) of "definable" ultrafilters

2012-09-02T23:26:36Z

This is a question which I suspect has an absurdly easy answer, but I'm not seeing it.

Let $\langle\cdot,\cdot\rangle:\omega^2\rightarrow\omega$ be your favorite pairing map (for me, this is the Cantor pairing function $(x, y)\mapsto{(x+y)(x+y+1)\over 2}+y$). Then, for $\mathcal{U}$ any ultrafilter on $\omega$, we can define a map $$m_\mathcal{U}: \mathcal{P}(\omega)\rightarrow\mathcal{P}(\omega): X\mapsto\lbrace j: \lbrace i: \langle i, j\rangle\in X\rbrace\in \mathcal{U}\rbrace.$$ The intuition behind this, for me, is that we take $X$, decompose it into rows, and treat each row as a guess at a mysterious set $\hat{X}$. The actual set $\hat{X}$ is the set of all natural numbers $j$ such that "most" of the rows of $X$ guess that $j$ is in $\hat{X}$. Topologically speaking, these maps are very badly behaved (unless $\mathcal{U}$ is principal of course); I don't know of any good picture of them besides this guessing idea.

This lets $\mathcal{U}$ act on collections of sets of natural numbers: for $\mathcal{C}\subseteq\mathcal{P}(\omega)$, let $$\mathcal{U}(\mathcal{C})=\lbrace m_\mathcal{U}(X): X\in\mathcal{C}\rbrace.$$ Mild closure properties of $\mathcal{C}$ imply that for all ultrafilters $\mathcal{U}$, we have $\mathcal{U}(\mathcal{C})\supseteq\mathcal{C}$; in the other direction, it is easy to construct, for any ultrafilter $\mathcal{U}$ and any $\mathcal{D}\subseteq\mathcal{P}(\omega)$, a $\mathcal{C}\subseteq\mathcal{P}(\omega)$ such that $\mathcal{D}\subseteq\mathcal{C}$ and $\mathcal{U}(\mathcal{C})=\mathcal{C}$.

I'm playing around with these maps for the heck of it; I don't know of any mathematical significance they have (although I'd be very interested if someone could point me towards a source where they're already studied). While fooling around, I ran into the following question:

Let $\mathcal{C}\subseteq\mathcal{P}(\omega)$. Say that an ultrafilter $\mathcal{U}$ on $\omega$ is definable in $\mathcal{C}$ if $\mathcal{U}(\mathcal{C})=\mathcal{C}$ and there is some formula $\phi$ with parameters from $\mathcal{C}\cup\omega$ and two free set variables $\phi(X, Y)$ in the language of second-order arithmetic such that $$\forall A, B\in\mathcal{C}, m_\mathcal{U}(A)=B\iff (\omega,\mathcal{C})\models\phi(A, B).$$ (In this case, say $\mathcal{U}$ is definable in $\mathcal{C}$ via $\phi$) My question is this:

(*) What are the $\mathcal{C}$, $\mathcal{U}$ such that $\mathcal{U}$ is definable in $\mathcal{C}$?

Principal ultrafilters are definable in reasonable $\mathcal{C}$, but I can't "construct" an example of any non-principal ultrafilter being definable in any $\mathcal{C}$ that isn't stupid (say, $\mathcal{C}=\lbrace A\rbrace$, $m_\mathcal{U}(A)=A$, so $\phi(X, Y)\equiv X=Y$); on the other hand, I have no reason to believe that nontrivial examples don't exist.

There is also the stronger notion of extendible definability: An ultrafilter $\mathcal{U}$ is extendibly definable in $\mathcal{C}$ if for some formula $\phi$, $\mathcal{U}$ is definable in $\mathcal{C}$ via $\phi$ and for all $\mathcal{D}\supseteq\mathcal{C}$, there is some $\mathcal{E}\supseteq \mathcal{D}$ such that $\mathcal{U}$ is definable in $\mathcal{E}$ via $\phi$. For instance, every principal ultrafilter is extendibly definable in any sufficiently closed $\mathcal{C}$.

(**) Are there any examples of non-principal ultrafilters being extendibly definable?

A negative answer to this question is plausible to me, I just have no idea how to approach this.

Thanks!

Existence (or non) of "definable" ultrafilters - MathOverflow

Existence (or non) of "definable" ultrafilters