Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
    
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. –  David Roberts May 25 '11 at 22:35
    
OK, let always $f:U\rightarrow U$. –  porton May 26 '11 at 10:50

1 Answer 1

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.

share|improve this answer
    
@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. –  porton May 28 '11 at 19:23
1  
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$. –  Andreas Blass May 28 '11 at 20:28
1  
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) –  Andreas Blass May 28 '11 at 20:36
    
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}$. –  Andreas Blass May 28 '11 at 20:39
    
I doubt that $f[a]=b$. –  porton May 31 '11 at 19:27

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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