1
$\begingroup$

Let $U$ is a set. I will speak about filters on this set.

If $f$ is a function and $a$ is a filter then I define $f \left[ a \right]$ as the filter whose base is $\lbrace f[A] | A \in a \rbrace$.

I will call super-embedding of filter $a$ into filter $b$ a function $f$ such that that $f[a] = b$.

$b \leqslant a$ if there are super-embedding from $a$ to $b$.

I will call filters $a$ and $b$ directly isomorphic when there are a bijective super-embedding from $a$ to $b$.

I will call filters $a$ and $b$ isomorphic iff there exist sets $A\in a$ and $B\in b$ such that $a\cap\mathcal{P}A$ is directly isomorphic to $b\cap\mathcal{P}B$.

Question If $a\le b$ and $b\le a$ then $a$ and $b$ are isomorphic, for every filters $a$ and $b$?

You may consult my article "Orderings of filters in terms of reloids" (at this Web page) about what I already know about ordering and isomorphism of filters.

$\endgroup$
2
  • $\begingroup$ The function $f$ - what are its domain and codomain? Without that I have no idea what $f[a]$ is (I know almost nothing about filters, but that shouldn't prevent me understanding your definition). My best guess is that it is an endomorphism of $U$, but this should be specified in the question for clarity. $\endgroup$
    – David Roberts
    May 25, 2011 at 22:35
  • $\begingroup$ OK, let always $f:U\rightarrow U$. $\endgroup$
    – porton
    May 26, 2011 at 10:50

1 Answer 1

1
$\begingroup$

My previous answer to this question was wrong. Here is a new alleged counterexample.

It is known that the Rudin-Keisler ordering of ultrafilters on the set $N$ of natural numbers includes a sequence ordered like the integers. That is, there are pairwise non-isomorphic ultrafilters $u_n$ and functions $h_n:N\to N$, with $n$ ranging over the set $Z$ of integers, such that $h_n[u_{n+1}]=u_n$ for each $n\in Z$. Fix such ultrafilters and functions. Define $a$ to be the filter on $Z\times N$ consisting of those sets $X$ such that, for each $n\in Z$, we have $\{x\in N:(n,x)\in X\}\in u_{2n+1}$, and define $b$ similarly except with $u_{2n}$ in place of $u_{2n+1}$. We have $f[a]=b$ where $f:Z\times N\to Z\times N$ is the function defined by $f(n,x)=(n,h_{2n}(x))$. We also have $g[b]=a$ where $g:Z\times N\to Z\times N$ is the function defined by $g(n,x)=(n-1,h_{2n-1}(x))$.

It remains to show that $a$ and $b$ are not isomorphic. (I'll use a similar idea to the one in my previous argument, but, since I went wrong there, I'll be more careful here --- I hope careful enough.) Under what circumstances does $a$ plus a single set $X\subseteq Z\times N$ generate an ultrafilter? Consider first the case that, for at least one $n\in Z$, we have $\{x\in N:(n,x)\in X\}\in u_{2n+1}$. Fix such an $n$, and notice that, for every $Y\in a$, both $Y$ and $X$ are in the ultrafilter generated by the sets $\{n\}\times A$ with $A\in u_{2n+1}$ --- the obvious isomorphic copy of $u_{2n+1}$ on $\{n\}\times N$. So, if $X$ together with $a$ generates an ultrafilter, it must be this copy of $u_{2n+1}$. Now consider the remaining case, where there is no $n\in Z$ such that $\{x\in N:(n,x)\in X\}\in u_{2n+1}$. In this case, we have, since each $u_{2n+1}$ is an ultrafilter, that $\{x\in N:(n,x)\in \sim X\}\in u_{2n+1}$ (where $\sim X$ denotes the complement of $X$ in $Z\times N$). Therefore, $\sim X\in a$, and the filter generated by $a$ plus $X$ is the improper filter, not an ultrafilter. In summary, the ultrafilters that can be generated by $a$ plus a single set are isomorphic copies of the odd-numbered $u_{2n+1}$'s. Similarly, the ultrafilters that can be generated by $b$ plus a single set are isomorphic copies of the even-numbered $u_{2n}$'s. Since the $u$'s are pairwise non-isomorphic, it follows that $a$ and $b$ are not isomorphic.

$\endgroup$
9
  • $\begingroup$ @Andreas Blass: First, please specify where you've got "It is known that the Rudin-Keisler ordering of ultrafilters on the set $N$ of natural numbers includes a sequence ordered like the integers." from. I am writing manuscripts for peer review and need to specify a source. BTW, I've not yet carefully read your second counter-example. I will read in near time. $\endgroup$
    – porton
    May 28, 2011 at 19:23
  • 1
    $\begingroup$ I'm not sure who first showed that such a sequence of ultrafilters exists, but one published reference (surely not the first) is my paper "Kleene degrees of ultrafilters" in the book "Recursion Theory Week" (Springer Lecture Notes in Mathematics 1141 (1985) pp. 29-48). The relevant part of that paper (independent of the recursion-theoretic part) is the discussion of the "tower" of an ultrafilter on pages 38-41. In particular, Theorem 2(b) on p. 39 implies that a certain non-trivial ultrapower of $N$ embeds in $T_{\omega+1}, a small part of the RK order of ultrafilters on $\omega$. $\endgroup$ May 28, 2011 at 20:28
  • 1
    $\begingroup$ A more direct construction of the required $Z$-sequence is as follows. Fix some $h:N\to N$ such that $h^{-1}(\{n\})$ is infinite for all $n$. Then build an ultrafilter $u$ such that $u$, $h[u]$, $h[h[u]]$, etc. are all non-isomorphic, hence can serve as $u_n$ for $n=0,-1,-2$, etc. (with the same $h$ as $h_n$ for all negative $n$). The existence of $u$ will follow once you check that no finitely many of the sets $S_n=\{X\subseteq N:h\text{ one-to-one on }h^n[X]\}$ cover $N$. Once you have this $u$ (to serve as $u_0$) ... (continued in next comment) $\endgroup$ May 28, 2011 at 20:36
  • $\begingroup$ and the $u_n$ for negative $n$, it's easy to handle positive $n$'s. Inductively choose $u_{n+1}$ so that $h$ maps it to $u_n$ and $h$ is not one-to-one on any set in $u_{n+1}$. $\endgroup$ May 28, 2011 at 20:39
  • $\begingroup$ I doubt that $f[a]=b$. $\endgroup$
    – porton
    May 31, 2011 at 19:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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