Dushnik-Miller for regular cardinals (part 1)

This is the first out of a series of posts on the following theorem.

Theorem (Erdos-Dushnik-Miller, 1941). For every infinite cardinal $λ$ , we have:

$λ \to (λ, ω)^{2} .$

Namely, for any coloring $c : [λ]^{2} \to {0, 1}$ there exists either a subset $A \subseteq λ$ of order-type $λ$ with $c “ [A]^{2} = {0}$ , or a subset $B \subseteq λ$ of order-type $ω$ with $c “ [A]^{2} = {1}$ .

In this post, we shall focus on the case that $λ$ is a regular cardinal.

Notice that the case $λ = ω$ is precisely the infinite Ramsey theorem. Also notice that a statement of the form $λ \to (λ, ω + 1)^{2}$ is syntactically stronger than the above statement. To appreciate this difference, let us mention the following four:

Theorem (Laver, 1973). $M A + 2^{ℵ_{0}} = ℵ_{2}$ entails $ω_{2} ↛ (ω_{2}, ω + 2)^{2}$ .

Theorem (Todorcevic, 1983). $P F A$ entails $ω_{1} \to (ω_{1}, α)^{2}$ for every $α < ω_{1}$ .

Theorem (Todorcevic, 1989). If $b = ω_{1}$ , then $ω_{1} ↛ (ω_{1}, ω + 2)^{2}$ .

Proposition (folklore). $α ↛ (ω, ω + 1)^{2}$ whenever $ω < α < ω_{1}$ .
Proof. Fix an injection $ψ : α \to ω$ . Define $c : [α]^{2} \to {0, 1}$ as follows.
Given $β < δ < α$ , let $c (β, δ) := 1$ iff $ψ (β) < ψ (δ)$ . There are the two possible cases.

Case 1: there exists a subset $A \subseteq α$ of order-type $ω$ such that $c “ [A] = {0}$ . Let ${β_{n} ∣ n < ω}$ denote the increasing enumeration of $A$ . By the definition of $c$ , and since $ψ$ is injective, we must conclude that $⟨ ψ (β_{n}) ∣ n < ω ⟩$ is a strictly decreasing sequence of ordinals. This is a contradiction.

Case 2: there exists a subset $B \subseteq α$ of order-type $ω + 1$ for which $c “ [B] = {1}$ . Let ${β_{n} ∣ n < ω + 1}$ denote the increasing enumeration of $B$ , then ${ψ (β_{n}) ∣ n < ω + 1}$ is a subset of $ω$ of order-type $ω + 1$ . This is a contradiction, as well.

In the case that $λ$ is indeed regular, the Erdos-Dushnik-Miller theorem will follow from the following stronger result.

Theorem (Erdos-Rado, 1956). For every regular uncountable cardinal $λ$ , we have:

$λ \to (stationary subset of λ, closed copy of ω + 1)^{2} .$

Proof. Suppose that we are given a coloring $c : [λ]^{2} \to {0, 1}$ . Fix an elementary submodel $M ≺ H (λ^{+})$ such that $c \in M$ and $M \cap λ$ is an ordinal of countable cofinality, say $δ$ .

If there exists a cofinal subset $B$ of $δ$ of order-type $ω$ for which $c “ [B \cup {δ}]^{2} = {1}$ , then we are done (as $B \cup {δ}$ would make a closed copy of $ω + 1$ ). Next, suppose this is not the case.

It follows that there exists a finite set $b \subseteq δ$ and an ordinal $β^{*} < δ$ such that the two holds:

$c “ [b \cup {δ}]^{2} = {1}$ ;
$c “ [b \cup {η} \cup {δ}]^{2} \neq {1}$ for every $η \in (β^{*}, δ)$ .

Fix such $b$ and $β^{*}$ . Then $b, β^{*}$ are in $M$ , and hence all of the following sets are in $M$ as well:

$A_{1} := {γ < λ ∣ c “ [b \cup {γ}]^{2} = {1}, γ > β^{*}}$ ;
$A_{2} := {γ \in A_{1} ∣ c “ [b \cup {η} \cup {γ}]^{2} \neq {1} for every η \in (β^{*}, γ)}$ ;
$A_{3} := {γ \in A_{2} ∣ c [(A_{2} \cap γ) \times {γ}] = {0}}$ .

Evidently, $c “ [A_{3}] = {0}$ . Thus, we are left with establishing that $A_{3}$ is a stationary subset of $λ$ . As $A_{3} \in M$ , the latter task reduces to showing that $M \cap λ \in A_{3}$ . Namely, that $δ \in A_{3}$ . We have already seen that $δ \in A_{2} \subseteq A_{1}$ , thus to see that $δ \in A_{3}$ , we fix an arbitrary $η \in A_{2} \cap δ$ and verify that $c (η, δ) = 0$ .

Note that:

I. $β^{*} < η < δ$ (since $η \in A_{1}$ )
II. $c “ [b \cup {η}]^{2} = {1}$ (since $η \in A_{1}$ )
III. $c “ [b \cup {δ}]^{2} = {1}$ (since $δ \in A_{1}$ )
IV. $c “ [b \cup {η} \cup {δ}]^{2} \neq {1}$ (by item I and since $δ \in A_{2}$ )

So, alotgether, it must be the case that $c (η, δ) = 0$ .

In an unpcoming post, we prove the Erdos-Dushnik-Miller theorem for the case of a singular $λ$ . We shall also point out that $λ \to (λ, ω + 1)^{2}$ fails for singular cardinals of countable cofinality, but otherwise holds provided that $2^{cf (λ)} < λ$ .

We conclude this post with one last no-can-do observation:

Proposition (folklore). $λ ↛ (club subset of λ, 3)^{2}$ for every ordinal $λ$ of uncountable cofinality.
Proof. Split $λ$ into two pairwise disjoint stationary sets, $S_{0}$ and $S_{1}$ . Define $c : [λ]^{2} \to {0, 1}$ by letting $c (α, β) = 0$ iff $(α, β) \in (S_{0} \times S_{0}) \cup (S_{1} \times S_{1})$ .

Now, in any club $C \subseteq λ$ , we can find $β \in S_{1} \cap C$ and $α \in S_{0} \cap C \cap β$ , and infer that $c (α, β) = 1$ . I.e., $c “ [C]^{2} \neq {0}$ for every club $C \subseteq λ$ .
On the other front, if $B$ is a subset of $λ$ of size $3$ , then for some $i < 2$ , we have $[B]^{2} \cap (S_{i} \times S_{i}) \neq \emptyset$ . Consequently, $c “ [B]^{2} \neq {1}$ .

Open Problem: Is it consistent that $b \to (b, ω + 2)^{2}$ ?

19 Responses to Dushnik-Miller for regular cardinals (part 1)

Micheal Pawliuk says:

January 21, 2012 at 2:06 am

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)

- saf says:
  
  January 21, 2012 at 2:53 am
  
  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.
  
Ari B. says:

January 25, 2012 at 4:29 am

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^{ℵ_{1}} > ℵ_{ω_{1}}$ , we do not know whether or not $ℵ_{ω_{1}} \to (ℵ_{ω_{1}}, ω + 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?

- saf says:
  
  January 25, 2012 at 9:25 am
  
  My guess is that the reviewer was under the impression that this solves the problem, because Shelah announced in an older paper that $ℵ_{ω_{1}} ↛ (ℵ_{ω_{1}}, ω + 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.
  
Ari B. says:

January 25, 2012 at 4:42 am

For a regular cardinal $l a m b d a$ , the relation $λ \to (λ, ω + 1)^{2}$ can be iterated to give $λ \to (λ, (ω + 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
$λ \to (stationary subset of λ, (closed copy of ω + 1)_{k})^{2}, (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 $ω + 1$ that is relatively closed in the stationary set, not necessarily closed in the original lambda. Is there another way to do the iteration?

- saf says:
  
  January 25, 2012 at 9:17 am
  
  The above proof actually gives you what you are looking for. Namely, that whenever $l a m b d a$ is a regular uncountable cardinal, and $S \subseteq α < λ ∣ cf (α) = ω$ is stationary, then to any coloring $c : [S]^{2} \to 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 $ω + 1$ .
  
  Simply take the model $M$ such that $S, c \in M$ and $M \cap λ \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
Amit Kumar Gupta says:

February 11, 2012 at 5:01 pm

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 $δ \in A_{2} \in M$ , $A_{2}$ is stationary, so it actually suffices to show that $c “ [A_{2}] = 0$ . This is easy: take $η < γ \in A_{2}$ . Then $c (η, γ) = 0$ by points II, III, and IV at the end of the proof.

Cheers,
Amit

- saf says:
  
  February 11, 2012 at 9:34 pm
  
  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
  $γ \in A_{2} ∣ c “ [A_{2} \cap γ]^{2} = 0,$
  to
  $γ \in A_{2} ∣ c [(A_{2} \cap γ) \times γ] = 0 .$
  
  Thanks, again.
  
  - Amit Kumar Gupta says:
    
    February 12, 2012 at 4:45 pm
    
    Hi Assaf,
    
    Yes, I think that works. My suggestion was that you don’t even need to mention $A_{3}$ . Clearly $δ \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 $δ \in A_{3}$ , just replace all occurrences of $δ$ with some $γ \in A_{2}$ with $η < γ$ .
    
    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
    
    - saf says:
      
      February 12, 2012 at 9:02 pm
      
      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
Ari B. says:

April 24, 2019 at 5:43 am

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

- saf says:
  
  April 24, 2019 at 6:04 am
  
  thanks!
  
David says:

July 27, 2020 at 1:09 pm

As to the result of Erdos and Rado assuming CH it holds that: $ω_{2} \to (ω_{2}, ω_{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 $< ω_{2}$ ?

- saf says:
  
  September 4, 2020 at 2:10 pm
  
  Hi David! Let us demonstrate that $ω_{2} ↛ (ω_{2}, closed (ω_{1} + 1))^{2}$ .
  For every limit ordinal $β < ω_{2}$ , fix a club $D_{β}$ in $β$ of order-type $c f (β)$ ,
  and then pick a coloring $c : [ω_{2}]^{2} \to {0, 1}$ such that, for every limit ordinal $β < ω_{2}$ , and every $α < β$ , $c (α, β) = 0$ iff $α \in D_{β}$ .
- $▸$ For every cofinal subset $S$ of $ω_{2}$ , we may find some $β \in S$ such that $S \cap β$ has order-type $> ω_{1}$ , and hence, there is $α \in S ∖ D_{β}$ , so that $c (α, β) = 1$ .
- $▸$ For every club $C$ in an ordinal $β$ of uncountable cofinality, we may find $α \in C \cap D_{β}$ , so that $c (α, β) = 0$ .

Dushnik-Miller for regular cardinals (part 1)

19 Responses to Dushnik-Miller for regular cardinals (part 1)

Leave a Reply Cancel reply

Archives

Keywords

Set Theory Colloquium

Friends’ Blogs

Recent Comments