Dushnik-Miller for regular cardinals (part 2)

In this post, we shall provide a proof of Todorcevic’s theorem, that $\mathfrak b=\omega_1$ implies $\omega_1\not\rightarrow(\omega_1,\omega+2)^2$. This will show that the Erdos-Rado theorem that we discussed in an earlier post, is consistently optimal. Our exposition of Todorcevic’s theorem would be slightly more general, with the benefit of yielding another famous theorem of Todorcevic: $\omega_1\not\rightarrow[\omega_1]^2_{\omega_1}$.

We commence by fixing two sequences (whose existence are basic ZFC facts):

• Let $\langle e_\alpha:\alpha\rightarrow\omega\mid \alpha<\omega_1\rangle$ be a sequence of injections such that $\{ e_\alpha\restriction\delta\mid \alpha<\omega_1\}$ is countable for every $\delta<\omega_1$;
• Let $\langle f_\alpha:\omega\rightarrow\omega\mid \alpha<\omega_1\rangle$ be a sequence of strictly increasing functions, such that $\alpha<\beta$ implies that $\{n<\omega\mid f_\alpha(n)\ge f_\beta(n)\}$ is finite.

Denote $\Delta(\alpha,\beta):=\min\{n<\omega\mid f_\alpha(n)\neq f_\beta(n)\}$.

This post will center around the analysis of the following object: let $H:[\omega_1]^2\rightarrow\mathcal P(\omega_1)$ be the function satisfying for all $\alpha<\beta<\omega_1$: $$H(\alpha,\beta):=\{\delta\in[\alpha,\beta)\mid f_\beta(\Delta(\alpha,\beta))\ge e_\beta(\delta)\}.$$

Define $c:[\omega_1]^2\rightarrow 2$ and $d:[\omega_1]^2\rightarrow\omega_1$ by letting for all $\alpha<\beta<\omega_1$:

• $c(\alpha,\beta):=1$ iff $\alpha= d(\alpha,\beta)$, where:
• $d(\alpha,\beta):=\min(H(\alpha,\beta)\cup\{\beta\})$.

Proposition 1. For every subset $B\subseteq\omega_1$ of order-type $\omega+2$, we have $c“[B]^2\neq\{1\}$.
Proof. Towards a contradiction, suppose that $B\subseteq\omega_1$ is of order-type $\omega+2$ and $c“[B]^2=\{1\}$. Let $\beta:=\max(B)$,  $\alpha:=\max(B\cap\beta)$, and $L:=B\cap\alpha$.
Fix $n<\omega$ such that $f_\alpha(m)<f_\beta(m)$ whenever $n\le m <\omega$. Let $n^*:=f_\beta(n)$. Put $D_\beta:=\{ \delta<\beta\mid e_\beta(\delta)\le n^*\}$, and likewise $D_\alpha:=\{\delta<\alpha\mid e_\alpha(\delta)\le n^*\}$. Since $e_\alpha$ and $e_\beta$ are injective, each of the sets $D_\alpha,D_\beta$ is finite, so we may find some $\delta\in L$ which is not in $D_\alpha\cup D_\beta$.
By $c(\delta,\beta)=1$, we get that $f_\beta(\Delta(\delta,\beta))\ge e_\beta(\delta)>n^*=f_\beta(n)$. As $f_\beta$ is strictly increasing, this means that $\Delta(\delta,\beta)>n$. Likewise, $f_\alpha(\Delta(\delta,\alpha))>n^*=f_\beta(n)>f_\alpha(n)$, and $\Delta(\delta,\alpha)> n.$ It follows that $f_\delta(n)=f_\beta(n)$ and $f_\delta(n)=f_\alpha(n)$, contradicting the fact that $f_\alpha(n)<f_\beta(n)$. $\square$

For a set $A\subseteq\omega_1$ and $t\in{}^{<\omega}\omega$, denote $A_t:=\{\alpha\in A\mid t\subseteq f_\alpha\}$.

Proposition 2. Every uncountable $A\subseteq\omega_1$, admits an uncountable subset $B\subseteq A$ such that $$\{ |B_t| \mid t\in{}^{<\omega}\omega\}=\{0,\aleph_1\}.$$
Proof. Let $B:=A\setminus\bigcup\{ A_t\mid t\in{}^{<\omega}\omega, |A_t|\le\aleph_0\}$. Then $B$ is uncountable and for every $t\in{}^{<\omega}\omega$, either $B_t$ is empty, or $B_t$ is uncountable. Fix $\alpha<\beta$ in $B$. Let

• $n:=\Delta(\alpha,\beta)$;
• $t:=f_\alpha\restriction n+1$;
• $C:=B\setminus B_t$.

Then $\{ |C_t| \mid t\in{}^{<\omega}\omega\}=\{0,\aleph_1\}.$ $\square$

Proposition 3.  For every uncountable $A\subseteq\omega_1$, the set $d“[A]^2$ contains a club.
Proof. Suppose that $A$ is a given uncountable set. By restricting our attention to an uncountable subset, we may assume that $A$ satisfies $\{ |A_t| \mid t\in{}^{<\omega}\omega\}=\{0,\aleph_1\}$. Denote $C^t:=\left\{ \alpha<\omega_1\mid \sup\left(A_t\cap\alpha\right)=\alpha\right\}$. Then $C:=\bigcap\{ C^t\mid t\in{}^{<\omega}\omega, A_t\neq\emptyset\}$ is the intersection of countably many clubs. Thus, it suffices to show that for every $\delta\in C$, there exists some $\alpha<\beta$ in $A$ for which $c(\alpha,\beta)=\delta$.

Fix $\delta\in C$.
Pick $\beta\in A$ above $\delta$. Put $n:=e_\beta(\delta)$, and $t:=f_\beta\restriction n$. Since $\beta\in A_t$, the set $A_t$ is non-empty, and hence uncountable, so let us pick $\sigma\in A_t$ above $\beta$. Put $n’:=\Delta(\beta,\sigma)$, $s:=f_\sigma\restriction(n’+1)$, $n^*:=f_\beta(n’)$, and $G=\{\gamma<\delta\mid e_\beta(\gamma)\le n^*\}$. Note:

• $G$ is finite, since $e_\beta$ is injective;
• $C\subseteq C^t$, since $\sigma$ witnesses that $A_s\neq\emptyset$;
• $\sup(A_s\cap\delta)=\delta$, since $\delta\in C\subseteq C^s$.

Fix $\alpha\in A_s\cap\delta$ above $\max(G)$. Then:

• $f_\sigma\restriction n =t$, since $\sigma\in A_t$;
• $t=f_\beta\restriction n$, and hence $\Delta(\beta,\sigma)\ge n$. That is, $n’\ge n$;
• $f_\alpha\restriction(n’+1)=s$, since $\alpha\in A_s$;
• $s=f_\sigma\restriction(n’+1)$, and hence $\Delta(\alpha,\sigma)\ge n’+1$;
• $\Delta(\beta,\sigma)=n'<\Delta(\alpha,\sigma)$, and hence $\Delta(\alpha,\beta)=n’$;
• $f_\beta(\Delta(\alpha,\beta))=f_\beta(n’)=n^* \ge n’ \ge n$, since $f_\beta$ is strictly increasing;
• $\delta\in H(\alpha,\beta)$, since $f_\beta(\Delta(\alpha,\beta))\ge n=e_\beta(\delta)$;
• if $\gamma\in H(\alpha,\beta)$, then $n^*\ge e_\beta(\gamma)$ and $\gamma\ge\alpha>\max(G)$;
• if $\gamma<\delta$ and $n^*\ge e_\beta(\gamma)$, then $\gamma\in G$.

If follows that $\delta=\min(H(\alpha,\beta))$. In particular, $d(\alpha,\beta)=\delta$. $\square$

Proposition 4. Suppose that $F=\{ f_\alpha\mid \alpha<\omega_1\}$ is unbounded in $\langle {}^\omega\omega,\le^*\rangle$.
Then $c“[A]^2\neq\{0\}$ for every uncountable subset $A\subseteq\omega_1$.
Proof. Suppose that $A$ is a given uncountable set. As in the proof of Propositon 3, we may assume that $\{ |A_t| \mid t\in{}^{<\omega}\omega\}=\{0,\aleph_1\}$, and consider the club  $C=\bigcap\{ C^t\mid t\in{}^{<\omega}\omega, A_t\neq\emptyset\}$.

Fix $\delta\in C$. Since $\{ f_\alpha\restriction\delta\mid \alpha\in A\}$ is countable, let us find an injection $e:\delta\rightarrow\omega$ and an uncountable subset $A^*\subseteq A\setminus\delta$ for which $\{ f_\alpha\restriction\delta\mid \alpha\in A^*\}=\{e\}$. Define $g:\omega\rightarrow\omega+1$, by letting $g(n):=\sup\{ f_\alpha(n)\mid \alpha\in A^*\}$ for all $n<\omega$. Note that $\omega\in\text{Rng(g)}$. [For suppose that $g$ is an element of ${}^\omega\omega$. As $F$ is unbounded in $\langle {}^\omega\omega,\le^*\rangle$, there exists some $\alpha<\omega_1$ such that $\{ n<\omega\mid g(n)<f_\alpha(n)\}$ is infinite, but then also $\{ n<\omega\mid g(n)<f_{\alpha^*}(n)\}$ is infinite for $\alpha^*:=\min(A^*\setminus\alpha)$, contradicting the fact that $f_{\alpha^*}(n)\le g(n)$ as the definition of $g$ dictates.]

Let $n<\omega$ be the least integer such that $g(n)=\omega$. Fix a sequence of ordinals $\langle \beta_i\mid i<\omega\}$ in $A^*$ such that $f_{\beta_i}(n)>i$ for all $i<\omega$. By minimality of $n$, there exists some $k<\omega$ such that $\{f_{\beta_i}\restriction n\mid i<\omega\}\subseteq {}^n k$. Thus, let us fix some $t\in{}^nk$ for which $\{ i<\omega\mid f_{\beta_i}\restriction n=t\}$ is infinite.
As $\beta_0$ witnesses that $A_t\neq\emptyset$, we infer that $\delta\in C^t$, and hence we may pick some $\alpha\in A_t\cap\delta$. Put $l:=e(\alpha)$, and let $i$ be least integer greater than $l$ for which $f_{\beta_i}\restriction n=t$. Then:

• $\alpha<\delta<\beta_i$, and $\alpha,\beta_i\in A$.
• $\Delta(f_\alpha,f_{\beta_i})\ge n$, since $f_\alpha\restriction n=t=f_{\beta_i}\restriction n$;
• $f_{\beta_i}(\Delta(f_\alpha,f_{\beta_i}))\ge f_{\beta_i}(n)>i>l=e(\alpha)$, since $f_{\beta_i}$ is order-preserving;
• $f_{\beta_i}(\Delta(f_\alpha,f_{\beta_i}))>e(\alpha)=e_{\beta_i}(\alpha)$, since $\beta_i\in A^*$.

It follows that $\alpha\in H(\alpha,\beta_i)$, and hence $c(\alpha,\beta_i)=1$. $\square$.

Corollary 1 (Todorcevic, 1989). $\mathfrak b=\omega_1$ entails $\omega_1\not\rightarrow(\omega_1,\omega+2)^2$.
Proof. Recall that $\mathfrak b=\omega_1$ iff there exists a sequence $\langle f_\alpha:\omega\rightarrow\omega\mid \alpha<\omega_1\rangle$ which is increasing and unbounded in $\langle {}^\omega\omega,\le^*\rangle$. $\square$

Corollary 2 (Hajnal, 1960). CH entails $\omega_1\not\rightarrow(\omega_1,\omega+2)^2$.
Proof. CH implies $\mathfrak b=\omega_1$. $\square$

Corollary 3 (Todorcevic, 1987). $\omega_1\not\rightarrow[\omega_1]^2_{\omega_1}$.
Proof. Let $\langle S_\delta\mid\delta<\omega_1\rangle$ be a partition of $\omega_1$ into mutually disjoint stationary sets. Define $d^*:[\omega_1]^2\rightarrow\omega_1$, by letting $$d^*(\alpha,\beta)=\min\{\delta<\omega_1\mid d(\alpha,\beta)\in S_\delta\}.$$ Then, for every uncountable $A\subseteq\omega_1$, $d“[A]^2$ contains a club, and hence $d^*“[A]^2=\omega_1$. $\square$