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\rightarrow(\lambda,\omega)^2.$$

Proof. Suppose that $\lambda$ is a singular cardinal, and $c:[\lambda]^2\rightarrow\{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 $\langle (X_n,\alpha_n)\mid n<\omega\rangle$ 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\neq\{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 $\langle \lambda_i \mid i<\text{cf}(\lambda)\rangle$ be a strictly increasing sequence of regular cardinals converging to $\lambda$, with $\lambda_0>\text{cf}(\lambda)$. Let $\langle X_i\mid i<\text{cf}(\lambda)\rangle$ 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\rightarrow\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\left\{ I_\alpha\mid \alpha\in \bigcup_{l<i}Y_{f(l)}\right\}$, 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$. $\square$

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

Proposition (folklore). $\lambda\rightarrow(\lambda,\omega+1)^2$ fails for every uncountable cardinal $\lambda$ of countable cofinality.
Proof. Suppose that $\lambda>\text{cf}(\lambda)=\omega$. Let $\langle \lambda_n\mid n<\omega\rangle$ denote an increasing sequence of ordinals converging to $\lambda$. Define $f:\lambda\rightarrow\omega$ by letting $f(\alpha):=\min\{n<\omega\mid \alpha<\lambda_n\}$. Define $c:[\lambda]^2\rightarrow\{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\restriction 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\neq\{0\}$ for every subset $A\subseteq\lambda$ of order-type $\lambda$. Altogether, $c$ witnesses the failure of $\lambda\rightarrow(\lambda,\omega+1)^2$. $\square$.

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.