This is the first out of a series of posts on the following theorem.
Theorem (Erdos-Dushnik-Miller, 1941). For every infinite cardinal $\lambda$, we have:
$$\lambda\rightarrow(\lambda,\omega)^2.$$
Namely, for any coloring $c:[\lambda]^2\rightarrow\{0,1\}$ there exists either a subset $A\subseteq \lambda$ of order-type $\lambda$ with $c“[A]^2=\{0\}$, or a subset $B\subseteq \lambda$ of order-type $\omega$ with $c“[A]^2=\{1\}$.
In this post, we shall focus on the case that $\lambda$ is a regular cardinal.
Notice that the case $\lambda=\omega$ is precisely the infinite Ramsey theorem. Also notice that a statement of the form $\lambda\rightarrow(\lambda,\omega+1)^2$ is syntactically stronger than the above statement. To appreciate this difference, let us mention the following four:
Theorem (Laver, 1973). $MA+2^{\aleph_0}=\aleph_2$ entails $\omega_2\not\rightarrow(\omega_2,\omega+2)^2$.
Theorem (Todorcevic, 1983). $PFA$ entails $\omega_1\rightarrow(\omega_1,\alpha)^2$ for every $\alpha<\omega_1$.
Theorem (Todorcevic, 1989). If $\mathfrak b=\omega_1$, then $\omega_1\not\rightarrow(\omega_1,\omega+2)^2$.
Proposition (folklore). $\alpha\not\rightarrow(\omega,\omega+1)^2$ whenever $\omega<\alpha<\omega_1$.
Proof. Fix an injection $\psi:\alpha\rightarrow\omega$. Define $c:[\alpha]^2\rightarrow\{0,1\}$ as follows.
Given $\beta<\delta<\alpha$, let $c(\beta,\delta):=1$ iff $\psi(\beta)<\psi(\delta)$. There are the two possible cases.
Case 1: there exists a subset $A\subseteq\alpha$ of order-type $\omega$ such that $c“[A]=\{0\}$. Let $\{\beta_n\mid n<\omega\}$ denote the increasing enumeration of $A$. By the definition of $c$, and since $\psi$ is injective, we must conclude that $\langle \psi(\beta_n)\mid n<\omega\rangle$ is a strictly decreasing sequence of ordinals. This is a contradiction.
Case 2: there exists a subset $B\subseteq\alpha$ of order-type $\omega+1$ for which $c“[B]=\{1\}$. Let $\{ \beta_n\mid n<\omega+1\}$ denote the increasing enumeration of $B$, then $\{\psi(\beta_n)\mid n<\omega+1\}$ is a subset of $\omega$ of order-type $\omega+1$. This is a contradiction, as well. $\square$
In the case that $\lambda$ is indeed regular, the Erdos-Dushnik-Miller theorem will follow from the following stronger result.
Theorem (Erdos-Rado, 1956). For every regular uncountable cardinal $\lambda$, we have:
$$\lambda\rightarrow(\text{stationary subset of }\lambda,\text{closed copy of }\omega+1)^2.$$
Proof. Suppose that we are given a coloring $c:[\lambda]^2\rightarrow\{0,1\}$. Fix an elementary submodel $M\prec H(\lambda^+)$ such that $c\in M$ and $M\cap\lambda$ is an ordinal of countable cofinality, say $\delta$.
If there exists a cofinal subset $B$ of $\delta$ of order-type $\omega$ for which $c“[B\cup\{\delta\}]^2=\{1\}$, then we are done (as $B\cup\{\delta\}$ would make a closed copy of $\omega+1$). Next, suppose this is not the case.
It follows that there exists a finite set $b\subseteq\delta$ and an ordinal $\beta^*<\delta$ such that the two holds:
- $c“[b\cup\{\delta\}]^2=\{1\}$;
- $c“[b\cup\{\eta\}\cup\{\delta\}]^2\not=\{1\}$ for every $\eta\in(\beta^*,\delta)$.
Fix such $b$ and $\beta^*$. Then $b,\beta^*$ are in $M$, and hence all of the following sets are in $M$ as well:
- $A_1:=\{ \gamma<\lambda\mid c“[b\cup\{\gamma\}]^2=\{1\}, \gamma>\beta^*\}$;
- $A_2:=\{ \gamma\in A_1\mid c“[b\cup\{\eta\}\cup\{\gamma\}]^2\not=\{1\}\text{ for every }\eta\in(\beta^*,\gamma)\}$;
- $A_3:=\{ \gamma\in A_2\mid c[(A_2\cap\gamma)\times\{\gamma\}]=\{0\}\}$.
Evidently, $c“[A_3]=\{0\}$. Thus, we are left with establishing that $A_3$ is a stationary subset of $\lambda$. As $A_3\in M$, the latter task reduces to showing that $M\cap\lambda\in A_3$. Namely, that $\delta\in A_3$. We have already seen that $\delta\in A_2\subseteq A_1$, thus to see that $\delta\in A_3$, we fix an arbitrary $\eta\in A_2\cap \delta$ and verify that $c(\eta,\delta)=0$.
Note that:
I. $\beta^*<\eta<\delta$ (since $\eta\in A_1$)
II. $c“[b\cup\{\eta\}]^2=\{1\}$ (since $\eta\in A_1$)
III. $c“[b\cup\{\delta\}]^2=\{1\}$ (since $\delta\in A_1$)
IV. $c“[b\cup\{\eta\}\cup\{\delta\}]^2\not=\{1\}$ (by item I and since $\delta\in A_2$)
So, alotgether, it must be the case that $c(\eta,\delta)=0$. $\square$
In an unpcoming post, we prove the Erdos-Dushnik-Miller theorem for the case of a singular $\lambda$. We shall also point out that $\lambda\rightarrow(\lambda,\omega+1)^2$ fails for singular cardinals of countable cofinality, but otherwise holds provided that $2^{\text{cf}(\lambda)}<\lambda$.
We conclude this post with one last no-can-do observation:
Proposition (folklore). $\lambda\not\rightarrow (\text{club subset of }\lambda,3)^2$ for every ordinal $\lambda$ of uncountable cofinality.
Proof. Split $\lambda$ into two pairwise disjoint stationary sets, $S_0$ and $S_1$. Define $c:[\lambda]^2\rightarrow\{0,1\}$ by letting $c(\alpha,\beta)=0$ iff $(\alpha,\beta)\in (S_0\times S_0)\cup (S_1\times S_1)$.
Now, in any club $C\subseteq\lambda$, we can find $\beta\in S_1\cap C$ and $\alpha\in S_0\cap C\cap \beta$, and infer that $c(\alpha,\beta)=1$. I.e., $c“[C]^2\not=\{0\}$ for every club $C\subseteq\lambda$.
On the other front, if $B$ is a subset of $\lambda$ of size $3$, then for some $i<2$, we have $[B]^2\cap (S_i\times S_i)\neq\emptyset$ . Consequently, $c“[B]^2\not=\{1\}$. $\square$
Open Problem: Is it consistent that $\mathfrak b\rightarrow(\mathfrak b,\omega+2)^2$?
That was a fast write-up Assaf!
I see that you simplified some of the arguments by writing `let b be a finite subset…’ as opposed to writing out the elements. This is a good habit that I keep trying to develop.
For clarification, did you mean to omit the superscript 2 in some of the arrow notations? (eg. the folklore propositions, the Todorcevic theorems)
Thanks for your feedback, Mike!
Indeed, I started by writing down the individual elements, but then got annoyed by the option that the set which I eventually called $b$ would be empty, so took another approach.
Thanks also for pointing out the superscript omissions. I will fix this.
Here’s a question that’s bothering me. Shelah’s paper that you linked (“The Erdos-Rado Arrow for Singular Cardinals”) gives a positive result for cardinals satisfying the particular relation that you state. But it does not say anything about the case where that relation fails. So for example, if $2^{\aleph_1} > \aleph_{\omega_1}$, we do not know whether or not $\aleph_{\omega_1} \rightarrow (\aleph_{\omega_1}, \omega+1)^2$. I think that means that this problem is still open, right? If so, then why does the MathSciNet review for that paper of Shelah state “The author settles a question of Erdos, Hajnal, Mate and Rado, proving…”, when the question is only partly solved?
My guess is that the reviewer was under the impression that this solves the problem, because Shelah announced in an older paper that $\aleph_{\omega_1}\nrightarrow(\aleph_{\omega_1},\omega+1)$ is consistent.
As far as I know, this theorem was never published, and this must mean that Shelah found a gap in the alleged proof.
Altogether, I would say that this question is still open.
For a regular cardinal $lambda$, the relation $\lambda\rightarrow(\lambda, \omega+1)^2$ can be iterated to give $\lambda\rightarrow(\lambda, (\omega+1)_k)^2$ (for finite k). This works if all you want is the homogeneous set of the required order type. But can we get
$$\lambda\rightarrow(\text{stationary subset of }\lambda, (\text{closed copy of }\omega+1)_k)^2,\quad\text{(for finite k)}?
$$
It seems to me that this doesn’t follow automatically, since the stationary subset of lambda is not necessarily closed, so when you iterate you get only a copy of $\omega+1$ that is relatively closed in the stationary set, not necessarily closed in the original lambda. Is there another way to do the iteration?
The above proof actually gives you what you are looking for. Namely, that whenever $lambda$ is a regular uncountable cardinal, and $S\subseteq{\alpha<\lambda\mid\text{cf}(\alpha)=\omega}$ is stationary, then to any coloring $c:[S]^2\rightarrow{0,1}$, either there exists a stationary subset $A\subseteq S$ with $c“[A]^2={0}$, or $c“[B]^2={1}$ for some closed subset $B\subseteq S$ of order-type $\omega+1$.
Simply take the model $M$ such that $S,c\in M$ and $M\cap\lambda\in S$.
Pingback: Dushnik-Miller for regular cardinals (part 2) | Assaf Rinot
Pingback: Dushnik-Miller for singular cardinals (part 2) | Assaf Rinot
Pingback: Fourteenth Linkfest
Hi Assaf,
I think there’s a minor mistake in your proof of the Theorem, but it can be fixed and actually simplifies the proof a bit. You state $c“[A_3]={0}$ is evidently true, but in fact this is the case iff $A_2 = A_3$. Since it’s clear that $\delta\in A_2\in M$, $A_2$ is stationary, so it actually suffices to show that $c“[A_2]={0}$. This is easy: take $\eta<\gamma\in A_2$. Then $c(\eta,\gamma)=0$ by points II, III, and IV at the end of the proof.
Cheers,
Amit
Thank you, Amit!
The proof indeed (implicitly) shows that $A_2=A_3$. In any case, to make the “evidently” truly evident, I changed the definition of $A_3$ from
$${ \gamma\in A_2\mid c“[A_2\cap\gamma]^2={0}},$$
to
$${ \gamma\in A_2\mid c[(A_2\cap\gamma)\times{\gamma}]={0}}.$$
Thanks, again.
Hi Assaf,
Yes, I think that works. My suggestion was that you don’t even need to mention $A_3$. Clearly $\delta\in A_2\in M$ so $A_2$ is stationary. Then you can show $c“[A_2]={0}$ using the exact same argument (points I-IV) you used to show $\delta\in A_3$, just replace all occurrences of $\delta$ with some $\gamma\in A_2$ with $\eta < \gamma$.
Interestingly, with $A_2$ it's easy to see that it's stationary but it takes an argument to show that its image under $c$ is ${0}$. For $A_3$ it's the opposite: its image is clearly ${0}$ (given your new definition) but it takes an argument to show it's stationary. Even more interestingly, the argument to show the image of $A_2$ is ${0}$ is exactly the same argument used to show $A_3$ is stationary. So $A_3$ doesn't gain you anything.
Cheers,
Amit
I totally agree. Basically, I had to choose between writing “Here’s an homogenous set — let’s see that it is large” to “Here’s a large set, let’s see that it is homogeneous” :).
Pingback: The P-Ideal Dichotomy and the Souslin Hypothesis | Assaf Rinot
The “Open Problem” above is answered (positively), assuming the consistency of a measurable cardinal, in this paper by Raghavan and Todorcevic:
https://doi.org/10.1007/s11856-018-1677-1
thanks!
As to the result of Erdos and Rado assuming CH it holds that: $\omega_2 \rightarrow (\omega_2, \omega_1 + 1)^2$, also the 0-homogeneous set can be made stationary [Handbook of Set Theory, ch. 2., 3.11]. Can it be strengthened to also require the 1-homogeneous set to be closed, i.e. a club subset of some uncountable ordinal $< \omega_2$ ?
Hi David! Let us demonstrate that $\omega_2\nrightarrow(\omega_2,\text{closed}(\omega_1+1))^2$.
For every limit ordinal $\beta<\omega_2$, fix a club $D_\beta$ in $\beta$ of order-type $cf(\beta)$,
and then pick a coloring $c:[\omega_2]^2\rightarrow\{0,1\}$ such that, for every limit ordinal $\beta<\omega_2$, and every $\alpha<\beta$, $c(\alpha,\beta)=0$ iff $\alpha\in D_\beta$.
thanks, that’s a nice counterexample!