Existence (or non) of "definable" ultrafilters - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-24T04:48:32Z http://mathoverflow.net/feeds/question/106205 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/106205/existence-or-non-of-definable-ultrafilters Existence (or non) of "definable" ultrafilters Noah S 2012-09-02T23:26:36Z 2012-09-05T11:21:08Z <p>This is a question which I suspect has an absurdly easy answer, but I'm not seeing it.</p> <p>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.</p> <p>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}$. </p> <p>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:</p> <p>Let $\mathcal{C}\subseteq\mathcal{P}(\omega)$. Say that an ultrafilter $\mathcal{U}$ on $\omega$ is <em>definable in $\mathcal{C}$</em> 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:</p> <p>(*) What are the $\mathcal{C}$, $\mathcal{U}$ such that $\mathcal{U}$ is definable in $\mathcal{C}$?</p> <p>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.</p> <p>There is also the stronger notion of <em>extendible definability</em>: An ultrafilter $\mathcal{U}$ is <em>extendibly definable in $\mathcal{C}$</em> 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}$.</p> <p>(**) Are there any examples of non-principal ultrafilters being extendibly definable?</p> <p>A negative answer to this question is plausible to me, I just have no idea how to approach this.</p> <p>Thanks!</p>