Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I was studying in this proof the implication $1\Rightarrow3$. I don't understand why $\{x_n,x_m\}\in[X]^2$ and $x_m>x_n$ implies $x_m\in X_{x_n}$. I believe it is not true, I think, first of all, we have to take $X^\prime_n=\bigcap_{i\leq n,i\in Y}X_i\cap Y$, but I can't fix the rest. Can anyone help me please?

Begin with a definition: $\mathcal{F}$ is called Ramsey if for every descending sequence $\{X_n:n\in\omega\}\subset\mathcal{F}$ there exists $\{x_n:n\in\omega\}\in\mathcal{F}$ such that $x_n\in X_n$ for every $n\in\omega$.

I want to prove that:

If $\mathcal{F}$ is Ramsey then for every set $A\subset[\omega]^2$ (not-ordered pairs of elements in $\omega$) there exists $X\in\mathcal{F}$ such that $[X]^2\subset A$ or $[X]^2\cap A=\emptyset$.

Here is the proof: for $n\in\omega$ define $X_n:=\{k>n:\{n,k\}\in A\}$, there exists $Y\in\mathcal{F}$ such that $X_n\in\mathcal{F}$ $\forall n\in Y$ or $\omega\backslash X_n\in\mathcal{F}$ $\forall n\in Y$. Assume that the first case holds. For $n\in Y$ define $X^\prime_n:=\bigcap_{i\leq n,i\in Y}X_i$. Apply the hypothesis to $\{X^\prime_n:n\in Y\}$ to get a set $X\in\mathcal{F}$. Then if $n,m\in Y$ and $x_n<x_m$ we have $x_m\in X_{x_n}$ and so $\{x_n,x_m\}\in A$.

I don't understand at the end, why $x_m\in X_{x_n}$.

share|cite|improve this question
When I click on the link it takes me to a google book page in Italian. Asking for 4.5.2 says (I guess) that the page is not available, though the snippet of page 236 looks like what you are after. – Ross Millikan Apr 19 '11 at 13:08
It is indeed a hassle, but please copy the theorem and relevant parts of the proof that you are having trouble with. – Asaf Karagila Apr 19 '11 at 13:09
Thank you for adding the content. – Arturo Magidin Apr 19 '11 at 15:26
Sorry Jacob, the answer I initially posted (in which said you might have the wrong definition of Ramsey) is probably incorrect. I still agree there appears to be a flaw in the proof you're scrutinizing, so if I can think up a correct proof I'll post it. – Amit Kumar Gupta Apr 23 '11 at 2:06
@Jaboc: I do not think it was good thing to accept my answer, since the original question is still unanswered. (I am around here not long enough to know the rules too good, I think that if you undo this, it will indicate to other members that there is still some stuff to be clarified here and the probability that someone will look into it will be higher.) – Martin Sleziak Apr 24 '11 at 7:02
up vote 1 down vote accepted

This is not an answer, but it would probably be too long for a comment.

First some definitions and results I copied from Bartoszynski-Judah:

Definition 4.4.1: p-point = ultrafilter with pseudointersection property

Lemma 4.4.3: $\mathcal F$ is a p-point $\Leftrightarrow$ for every partition of $\omega$, $\{Y_n; n\in\omega\}$, either there exists $n\in\omega$ such that $Y_n\in\mathcal F$ or there exists $X\in\mathcal F$ such that $X\cap Y_n$ is finite for $n\in\omega$.

Definition 4.5.1: A filter $\mathcal F$ is called Ramsey if for every descending sequence $\{x_n; n\in\omega\}\subseteq\mathcal{F}$ there exists a sequence $\{x_n; n\in\omega\}\in\mathcal F$ such that $x_n\in X_n$ for $n\in\omega$.

$\mathcal F$ is called a q-point if for every partition of $\omega$ into finite pieces $\{I_n: n\in\omega\}$ there exists $X \in \mathcal F$ such that $|X \cap I_n| \le 1$ for $n\in\omega$.

Theorem 4.5.2

Let $\mathcal F$ be an ultrafilter on $\omega$. The following conditions are equivalent:

  1. $\mathcal F$ is Ramsey,

  2. for every partition of $\omega$, $\{Y_n : n\in\omega\}$, either $Y_n \in \mathcal F$ for some $n\in\omega$ or there exists $X\in \mathcal F$ such that $|X_n\cap Y_n| \le 1$ for $n\in\omega$,

  3. for every set $A\subseteq[\omega]^2$ there exists $X\in\mathcal F$ such that $[X]^2\subseteq A$ or $[X]^2\cap A=\emptyset$,

  4. $\mathcal F$ is a p-point and a q-point.

When I tried to search in various literature (books, papers); I found quite frequently that Ramsey is equivalent to p-point and q-point. Most authors defined Ramsey ultrafilters using 3 (colorings). But I also found 2, sometimes under name selective ultrafilter.

I did not find the condition 1 in literature, the closest what I found was:

Lemma I.1.4. A nonprincipal ultrafilter $\mathcal U$ on $\omega$ is Ramsey iff for every sequence $\{M_i, i\in\omega\}\subseteq \mathcal U$ there exists $M \in \mathcal U$ such that $j \in M_i$ for all $i < j$ in $M$. (In Spiros A. Argyros, Stevo Todorcevic: Ramsey Methods in Analysis).

Several authors define selective ideals using diagonalization, which is very similar to condition from Lemma I.1.4.

Jech (Set Theory, Millenium Edition) in proof of Lemma 9.2 show as an auxiliary result that a decreasing system $X_n$ of sets from a Ramsey ultrafilter $D$ there exists $\{a_0<a_1<\dots\}\in D$ such that $a_0\in X_0$ and $a_{n+1}\in X_{a_n}$.

I believe that after replacing their definition of Ramsey ultrafilter by some of the above conditions, the proof from Bartoszynski-Judah might work; but I am still not convinced that their definition is incorrect.

share|cite|improve this answer
Lemma I.1.4 that you mention is equivalent to the auxiliary result in Jech. To prove I.1.4 from Jech's result, let $X_0 = M_0$, $X_{n+1} = X_n \cap M_{n+1}$ (and remove the minimum element from $X_{n+1}$ if necessary to make the $X_n$ strictly decreasing). The set we get from Jech's result gives us the desired $M$. Conversely, given $X_n$, let $M_n = X_n$ and apply the Lemma to get a set $M$. This set will almost satisfy Jech's result, we just need to remove its minimum element so that now, the "new" minimum element is sure to be in $X_0$. – Amit Kumar Gupta Apr 23 '11 at 5:17
By the way, sorry about the redundancy of my (current) answer in light of yours. I only read your answer after totally overhauling my original one. So it seems we're both a bit unsure of the definition in Bartoszynski and Judah, and we've found 6 other definitions/characterizations of "Ramsey" which are equivalent to one another but none of them obviously implied by the definition in Bartoszynski and Judah. That said, I suspect their definition is probably right and there's some argument we're just not seeing. – Amit Kumar Gupta Apr 23 '11 at 5:20
I do not think that your answer is redundant. You summarized it very nicely and explained some points I have missed. – Martin Sleziak Apr 24 '11 at 6:58

This isn't an answer, but it's too long for a comment.

Let's say that a non-principal ultrafilter $\mathcal{F}$ on $\omega$ is:

  • Ramsey(BJ) iff for every decreasing sequence $X_n$ of sets in $\mathcal{F}$, there exists a set $\{ x_n | n \in \omega \} \in \mathcal{F}$ such that for each $n$, $x_n \in X_n$;
  • Ramsey(BJ)${}^+$ iff for such a decreasing sequence $X_n$, the set of $x_n$ that we get satisfy the stronger condition that $x_0 \in X_0$ and $x_{n+1} \in X_{x_n}$;
  • Ramsey(J) iff for every partition $\omega = \bigsqcup _n Z_n$ into "small" sets (i.e. each $Z_n \not\in \mathcal{F}$), there exists $X \in \mathcal{F}$ such that for each $n$, $|X \cap Z_n| \leq 1$;
  • Ramsey(R) iff for every colouring $c : [\omega]^2 \to 2$ there exists $X \in \mathcal{F}$ such that $|c''[X]^2| = 1$; and
  • Ramsey(R)${}^+$ iff for every colouring $c : [\omega]^n \to k$ (for any finite $n, k$) there exists $X \in \mathcal{F}$ such that $|c''[X]^n| = 1$.

The "BJ" is supposed to make you think of Bartoszynski and Judah, the "J" for Jech, and the "R" for Ramsey, since the Ramsey(R) definitions look most evidently like generalizations of Ramsey's theorem.

Now, Bartoszynski and Judah define a Ramsey ultrafilter to be a Ramsey(BJ) ultrafilter. And Theorem 4.5.2 in that text is essentially proving that Ramsey(BJ), Ramsey(J), and Ramsey(R) are equivalent (ignoring clause 4 of that theorem). The proof they give of "Ramsey(BJ) implies Ramsey(R)" seems to use Ramsey(BJ)${}^+$, however. So at first glance, there appears to be a problem.

On the other hand, Jech, as you might guess, defines a Ramsey ultrafilter to be a Ramsey(J) ultrafilter. Then in Lemma 9.2 he proves that an ultrafilter is Ramsey(J) iff it's Ramsey(R)${}^+$. He proves the forward (harder) direction in two steps, first he proves that Ramsey(J) implies Ramsey(BJ)${}^+$, and then that Ramsey(BJ)${}^+$ implies Ramsey(R)${}^+$.

So (assuming Jech's proof is correct, as is the rest of the proof in Bartoszynski and Judah), we know that the last four definitions above are all equivalent, and the first is weaker, but perhaps not strictly weaker. I doubt the definition given in Bartoszynski and Judah is a mistake (although I suppose it's possible), so how can we see that Ramsey(BJ) implies one of the other four characterizations?

share|cite|improve this answer
Did you want to write "at most one point" instead of "exactly one point" in the definition of p-point? This is what I found in most sources e.g here… and here -- I can see how you want to get the definition from Bartozsynski-Judah if you're working with "exactly one"; I do not see the proof right away for "at most one". (Using some kind of correspondence between decreasing systems and partitions.) – Martin Sleziak Apr 22 '11 at 22:44
@Martin: I believe you're referring to my definition of Ramsey ultrafilter, not p-point. Replacing exactly one point with at least one point in my definition changes nothing, since if there's a measure 1 set meeting each piece of a partition in at most 1 point, then there's one meeting each piece of the partition in exactly one point - this is because the pieces of a partition are disjoint, and because ultrafilters are closed upwards under inclusion. – Amit Kumar Gupta Apr 23 '11 at 0:19

Your Answer


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.