9
$\begingroup$

For arbitrary (selective) ultrafilter $\mathcal{F}$ does there exist bijection $\phi:[\omega]^2\to\omega$ with the property: $\forall B\in\mathcal{F} : \phi([B]^2)\in\mathcal{F}$ ?

$\endgroup$
12
$\begingroup$

No, this fails not only for selective ultrafilters but for all non-principal ultrafilters $\mathcal F$ on $\omega$.

The main ingredient in the proof is the theorem that, if an ultrafilter $\mathcal U$ on a set $X$ is sent to itself by some map $g:X\to X$ (meaning that $\mathcal U=g(\mathcal U):=\{A\subseteq X:g^{-1}(A)\in\mathcal U\}$), then the set of points in $X$ fixed by $g$ has to be in $\mathcal U$. This easily implies that, if $\phi:X\to Y$ is a bijection and $g:X\to Y$ is an arbitrary map and $\mathcal U$ is an ultrafilter on $X$ with $\phi(\mathcal U)=g(\mathcal U)$, then $\{x\in X:\phi(x)=g(x)\}\in\mathcal U$.

In your situation, suppose toward a contradiction that $\phi$ were a bijection as in the question. Let $\mathcal G$ be the filter on $[\omega]^2$ generated by the sets $[B]^2$ for $B\in\mathcal F$. ($\mathcal G$ may or may not be an ultrafilter, depending on whether or not $\mathcal F$ is selective.) Your requirement on $\phi$ implies that each set in $\mathcal G$ meets each set of the form $\phi^{-1}(A)$ for $A\in\mathcal F$. Since the intersection of two sets of the form $[B]^2$ for $B\in\mathcal F$ is again a set of that form, and since the intersection of two sets of the form $\phi^{-1}(A)$ for $A\in\mathcal F$ is again a set of that form, it follows that the sets of these two forms generate a proper filter. Let $\mathcal U$ be an ultrafilter on $[\omega]^2$ extending that filter. So we have $[B]^2\in\mathcal U$ and $\phi^{-1}(A)\in\mathcal U$ for all $A,B\in\mathcal F$.

It follows that $\phi(\mathcal U)=\mathcal F$. It also follows that $g(\mathcal U)=\mathcal F$, where $g:[\omega]^2\to\omega$ is the function sending each pair $\{x<y\}\in[\omega]^2$ to its smaller member $x$. By the theorem cited above, we have that the set $E=\{\{x<y\}\in[\omega]^2:x=\phi(\{x,y\})\}$ is in $\mathcal U$. Since $\phi$ is one-to-one, $E$ contains, for any $x\in\omega$, at most one pair whose smaller element is $x$. Thus, there is a function $f:\omega\to\omega$ such that $E\subseteq\{\{x,f(x)\}:x\in\omega$. Note that $x$ here is the smaller element (the one given by $g$) in the pair $\{x,f(x)\}$, and so we have $x<f(x)$ for all $x$.

Consider any two sets $B,C\in\mathcal F$. Since $[B\cap C]^2$ and $E$ are both in $\mathcal U$, they have a nonempty intersection. In particular, there is some $x\in C$ with $f(x)\in B$, i.e., with $x\in f^{-1}(B)$. I've just shown that $f^{-1}(B)$ intersects every set $C\in\mathcal F$; since $\mathcal F$ is an ultrafilter, it follows that $f^{-1}(B)\in\mathcal F$. And since this holds for all $B\in\mathcal F$, we have $f(\mathcal F)=\mathcal F$. By the theorem cited at the beginning, $f(x)=x$ for $\mathcal F$-almost all $x$. This contradicts the fact that $x<f(x)$ for all $x$.

$\endgroup$
  • $\begingroup$ Thank you for your answer. Where can I read about the theorem you mention in beginning? $\endgroup$ – ar.grig Feb 27 at 20:24
  • 2
    $\begingroup$ The theorem used in the solution is due to Katetov (1967), you can find the short paper where it appeared through the link: dml.cz/bitstream/handle/10338.dmlcz/105124/…. You can also find Solovay's rendition of Katetov's theorem through the link: math.berkeley.edu/~solovay/Preprints/Rudin_Keisler.pdf $\endgroup$ – Ali Enayat Feb 28 at 0:14
  • $\begingroup$ @AliEnayat: Thank you. I got the links. But what about reference of Solovay's rendition which could be cited in article ? $\endgroup$ – ar.grig Mar 2 at 9:16
  • $\begingroup$ @ar.grig To my knowledge, Solovay's rendition has never appeared in print; his argument is "essentially the same" as Katetov's. As pointed out in the following source, Katetov's theorem can be viewed as a special case of the Bruijn-Erdős theorem: dml.cz/bitstream/handle/10338.dmlcz/126182/… $\endgroup$ – Ali Enayat Mar 3 at 17:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.