Dushnik-Miller for singular cardinals (part 1)

Continuing the previous post, let us now prove the following.

Theorem (Erdos-Dushnik-Miller, 1941). For every singular cardinal λ, we have:
$$\lambda \to (\lambda ,\omega {)}^2.$$

Proof. Suppose that $\lambda$ is a singular cardinal, and $c:[\lambda {]}^2\to \{0,1\}$ is a given coloring. For any ordinal $\alpha <\lambda$, denote $I_{\alpha }:=\{\beta \in (\alpha ,\lambda )\mid c(\alpha ,\beta )=1\}$.

Subclaim. At least one of the following holds:

1. there exists an infinite subset $B\subseteq \lambda$ for which $c“[B{]}^2=\{1\}$;
2. there exists a subset $X\subseteq \lambda$ of size $\lambda$, such that $|X\cap I_{\alpha }|<\lambda$ for all $\alpha \in X$.

Proof. Suppose that (2) fails. Recursively define a seuqence $⟨(X_n,{\alpha }_n)\mid n<\omega ⟩$ as follows:
– $X_0:=\lambda$, and ${\alpha }_0$ is a witness to the fact that $\{\alpha \in X_0\mid |X_0\cap I_{\alpha }|=\lambda \}$ is non-empty;
– $X_{n+1}:=X_n\cap I_{{\alpha }_n}$, and ${\alpha }_{n+1}$ is an element of the non-empty set $\{\alpha \in X_{n+1}\mid |X_{n+1}\cap I_{\alpha }|=\lambda \}$.

Then $n<m<\omega$ implies that ${\alpha }_n<{\alpha }_m\in X_m\subseteq X_{n+1}\subseteq I_{{\alpha }_n}$. In particular, $c({\alpha }_n,{\alpha }_m)=1$. So $B=\{{\alpha }_n\mid n<\omega \}$ witnesses clause (1). End of proof of subclaim.

Next, let us suppose that $c“[B{]}^2\ne \{1\}$ for any infinite $B\subseteq \lambda$, and work towards showing that $c“[A{]}^2=\{0\}$ for some subset $A\subseteq \lambda$ of size $\lambda$. By our hypothesis, we may fix a subset $X$ as in clause (2) of the preceding subclaim. Let $⟨{\lambda }_i\mid i<\text{cf}(\lambda )⟩$ be a strictly increasing sequence of regular cardinals converging to $\lambda$, with ${\lambda }_0>\text{cf}(\lambda )$. Let $⟨X_i\mid i<\text{cf}(\lambda )⟩$ be some partition of a subset of $X$ into pairwise-disjoint sets such that $|X_i|={\lambda }_i$ for all $i<\text{cf}(\lambda )$. For simplicity, we shall further require that $sup(X_i)<min(X_j)$ for all $i<j<\text{cf}(\lambda )$.

Denote $\kappa :=\text{cf}(\lambda )$, and fix $i<\kappa$.
– Since ${\lambda }_i$ is regular, we infer from the previous post, the existence of a subset $Y_i\subseteq X_i$ of size ${\lambda }_i$ such that $c“[Y_i]=\{0\}$.
– Since $Y_i\subseteq X_i\subseteq X$, we get that $$Y_i=\bigcup _{j<\kappa }\{\alpha \in Y_i\mid |X\cap I_{\alpha }|<{\lambda }_j\},$$ and since $|Y_i|=\text{cf}({\lambda }_i)>\kappa$, we infer the existence of some $j_i<\kappa$ for which $$|\{\alpha \in Y_i\mid |X\cap I_{\alpha }|<{\lambda }_{j_i}\}|={\lambda }_i.$$

Recursively define a function $f:\kappa \to \kappa$ so that for all $i<\kappa$, we would have:
$${\lambda }_{f(i)}>\sum _{l<i}({\lambda }_{f(l)}+{\lambda }_{j_{f(l)}}).$$

Then, for all $i<\kappa$, let $Z_i:=Y_{f(i)}\setminus \bigcup \{I_{\alpha }\mid \alpha \in \bigcup _{l<i}{Y}_{f(l)}\}$, and notice that the choice of $f$ insures that $|Z_i|={\lambda }_{f(i)}$ for all $i<\kappa$. So in particular, $A:=\bigcup _{i<\kappa }{Z}_i$ is a subset of size $\lambda$.
Finally, to see that $c“[A{]}^2=\{0\}$, fix ${\alpha }_0<{\alpha }_1$ in $A$. Let $i_0,i_1$ be such that ${\alpha }_n\in Z_{i_n}$ for all $n<2$. There are two cases to consider:

case 1: $i_0=i_1$. Here, $\{{\alpha }_0,{\alpha }_1\}\subseteq Y_{f(i_0)}$. So, by the choice of $Y_{f(i_0)}$, we conclude that $c({\alpha }_0,{\alpha }_1)=0$.

case 2: $i_0<i_1$. Since ${\alpha }_0\in Z_{i_0}\subseteq Y_{f(i_0)}$, we know that $I_{{\alpha }_0}$ is disjoint from $Z_{i_1}$. In particular, ${\alpha }_1$ is not an element of $I_{{\alpha }_0}$, meaning that $c({\alpha }_0,{\alpha }_1)=0$. $\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/15.0.3/svg/25fb.svg">}$

To see that the preceding theorem is somewhat optimal, we point out the following.

Proposition (folklore). $\lambda \to (\lambda ,\omega +1{)}^2$ fails for every uncountable cardinal $\lambda$ of countable cofinality.
Proof. Suppose that $\lambda >\text{cf}(\lambda )=\omega$. Let $⟨{\lambda }_n\mid n<\omega ⟩$ denote an increasing sequence of ordinals converging to $\lambda$. Define $f:\lambda \to \omega$ by letting $f(\alpha ):=min\{n<\omega \mid \alpha <{\lambda }_n\}$. Define $c:[\lambda {]}^2\to \{0,1\}$ by letting $c(\alpha ,\beta ):=0$ iff $f(\alpha )=f(\beta )$.

Evidently, for every $B\subseteq \lambda$ that satisfies $c“[B{]}^2=\{1\}$, we have that $f\upharpoonright B$ is order-preserving. In particular, $\text{otp}(B)\le \omega$ for any such $B$. On the other front, as $|f^{-1}\{n\}|<\lambda$ for all $n<\omega$, we get that $c“[A{]}^2\ne \{0\}$ for every subset $A\subseteq \lambda$ of order-type $\lambda$. Altogether, $c$ witnesses the failure of $\lambda \to (\lambda ,\omega +1{)}^2$. $\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/15.0.3/svg/25fb.svg">}$.

In an upcoming post, we shall provide a proof for Shelah’s recent extension of the Edros-Dushnik-Miller theorem that handles singular cardinals of uncountable cofinality.