3
$\begingroup$

In this question I had asked about proof of the property of selective ultrafilter. As was answered, the proof is trivial if we know that ultrafilter is selective iff it is Ramsey ultrafilter. The proof of latter fact can be found in book "Theory of ultrafilters" by Comfort and Negrepontis. Non-trivial part of this proof is the implication "selective $\implies$ quasi-normal". While it is easy to see that the proof of latter implication is correct, I was unable to understand intuitive idea of this proof. So, I tried to find more easy and intuitively clear proof. So, the question :

Proof that for any selective ultrafilter $\mathcal{F}$ and for arbitrary family of big sets $\{A_i\}_{i\in\omega}$ there exists a big set $A$ with the property: $\forall i,j \in A : i<j \implies j\in A_i$

I will give my proof in answers below.

$\endgroup$
5
$\begingroup$

I don't have my copy of Comfort & Negrepontis handy, so the following might be essentially the same as their proof, but I think it's clear enough.

The very rough idea is that, because $\mathcal F$ is a Q-point, the proof would be easy if each $A_i$ were a final segment of $\omega$ (Steps 3 and 4 below), and, because $\mathcal F$ is a P-point, we can reduce to this final-segment case by restricting to a suitable set in $\mathcal F$ (Steps 1 and 2 below).

Step 1. Get a big set $B$ that is almost included (i.e., included except for a finite set) in each $A_i$. This is essentially the fact that a selective ultrafilter is a P-point, plus the equivalence of a couple of definitions of P-point. In detail: Without loss of generality (because $\mathcal F$ is non-principal) $A_i$ has no elements $\leq i$, and so, for every natural number $x$, we can define $f(x)$ to be the smallest $i$ such that $x\notin A_i$. This $f$ cannot be constant on any set in $\mathcal F$, because the set on which it has value $i$ is disjoint from $A_i\in\mathcal F$. So $f$ is one-to-one on some $B\in\mathcal F$. On $B-A_i$, this one-to-one $f$ takes only values $\leq i$, so $|B-A_i|\leq i+1$. That completes step 1.

Step 2. Partition $\omega$ into a sequence of finite intervals $I_0,I_1,\dots$, where $I_n=[e_n,e_{n+1})$ (with $e_0=0$ and $e_{n+1}>e_n$), choosing the sequence $(e_n)$ growing so rapidly that, for all $i\leq e_n$, all elements of the finite set $B-A_i$ are $<e_{n+1}$. It is trivial to choose such $e_n$'s by induction on $n$. This choice ensures that, if $i\leq e_n$ and $j\geq e_{n+1}$ (thus, if $i<j$ are in $B$ and lie in $I$-intervals with at least one other $I$-interval between them) then $j\in A_i$.

Step 3. Apply selectivity to the function $g$ that is constant with value $n$ on exactly the interval $I_n$, to get a set $C\in\mathcal F$ that has at most one element in any $I_n$. So,if $i<j$ are in $B\cap C$ and are not consecutive in $C$, then $j\in A_i$.

Step 4. Finally, let $D$ consist of every second element of $C$, and let $E=C-D$. Because $\mathcal F$ is an ultrafilter, it contains exactly one of $D$ and $E$, so it contains one of $B\cap D$ and $B\cap E$. Within either of these sets, $i<j$ implies $j\in A_i$, so the proof is complete.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you very much for your answer and for clearly explained main idea of your proof. Can you also review the one of mine? $\endgroup$ – ar.grig May 26 '18 at 17:34
  • 1
    $\begingroup$ The general idea of your proof seems to be the same as mine, but I don't (yet) understand your definition of $m_k$. Should it perhaps have been the smallest number of the form $f(b)$ with $b\in B$ and $b$ larger than all elements of previous $P_n$'s (rather than $s=f(b)$ larger than all those elements)? Also, your second paragraph, where you replace $A_k$ with $A_k'$, should come earlier, because without it the function $f$ in your first paragraph might not be defined everywhere (some $i$ might be in all of the given sets $A_j$). $\endgroup$ – Andreas Blass May 27 '18 at 0:08
  • $\begingroup$ 1. Yes, $m_k$ is smallest number from $f(B)$, which is larger than all previous $P_n$'s. 2. Yes, of course, I should assume that $\cap_i A_i=\emptyset$. Corrected. $\endgroup$ – ar.grig May 27 '18 at 10:08
  • $\begingroup$ @ar.grig Your answer "yes" to part 1 suggests that you agree with my proposed change, but then you repeat that part of your answer, not changed. So I'm confused: In the notation of my previous comment, do you want $b$ or $f(b)$ to be larger than all previous $P_n$'s? $\endgroup$ – Andreas Blass May 27 '18 at 12:16
  • $\begingroup$ Sorry for misunderstanding. I need $m_k=f(b)$ for some $b\in B$ and be larger than all elements of previous $P_n$'s ( the corresponding $b$ will be larger too, because $m_k=f(b)\leq b$ ). I need this condition, because it implies $P_k\neq\emptyset$. $\endgroup$ – ar.grig May 27 '18 at 14:54
0
$\begingroup$

First of all we can assume with no loss of generality that $\forall i\in A_k~:~ i>k$, because we can replace $A_k$ with $A_k'=\{i\in A_k | i>k\}$. Let $f:\omega\to\omega, f(i)=min\{j\in\omega | i\notin A_j\}$. Thus $f(i)\leq i$. Obviously, $f^{-1}(j)\cap A_j = \emptyset$ and, so, there exists big set $B$ such that $f$ is injective on $B.$

My main idea is creating of big set $A$ with property: $\forall i,j\in A : i<j \implies i<f(j) \leq j$. Such a set satisfies the conditions of the statement.

Now let construct finite subsets $P_k$ of $B$ as follows: $m_0=f(b_0)=min f(B), P_0=\{b_0\}$, $ m_k=min\{s\in f(B) ~|~ s>max \cup_{n=0}^{k-1}P_n\}$, $P_k=\{b\in B ~|~ m_{k-1}< f(b) \leq m_k\}$.

We have $\coprod_k P_k = B$. One of $\coprod_k P_{2k}$ and $\coprod_k P_{2k+1} $ is big and partitioned with $P_n$ where n is odd or even. Applying selectivity we get big set which can be taken as $A$.

| cite | improve this answer | |
$\endgroup$

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.