Dushnik-Miller for regular cardinals (part 3)

Here is what we already know about the Dushnik-Miller theorem in the case of $\omega_1$ (given our earlier posts on the subject):

• $\omega_1\rightarrow(\omega_1,\omega+1)^2$ holds in ZFC;
• $\omega_1\rightarrow(\omega_1,\omega+2)^2$ may consistently fail;
• $\omega_1\rightarrow(\omega_1,\omega_1)^2$ fails in ZFC.

In this post, we shall provide a proof of Todorcevic’s theorem that PFA implies $\omega_1\rightarrow(\omega_1,\alpha)^2$ for all $\alpha<\omega_1$.

We commence with a sequence of lemmas.

Lemma 1.  Suppose that $\langle I_\beta\mid \beta<\omega_1\rangle$ is a given sequence of sets, with $I_\beta\subseteq\beta$ for all $\beta<\omega_1$. For $Z\subseteq\omega_1$, denote $$\mathcal I(Z):=\{ X\in[Z]^{\le\aleph_0}\mid |\{\beta\in Z\mid X\cap I_\beta\text{ is infinite}\}|\le\aleph_0\}.$$

If $A\subseteq Z\subseteq\omega_1$ are uncountable sets, and $[A]^{\aleph_0}\subseteq\mathcal I(Z)$, then there exists some uncountable $B\subseteq A$ such that $\alpha\not\in I_{\beta}$ for all $\alpha<\beta$ in $B$.
Proof. As $A\cap\delta\in\mathcal I(Z)$ for all $\delta<\omega_1$, we may recursively construct a strictly-increasing function $f:\omega_1\rightarrow A$ such that $f[\beta]\cap I_{f(\beta)}$ is finite for all $\beta<\omega_1$. Let $A_1:=f“[\omega_1]$. Then $A_1$ is an uncountable subset of $A$, and $x_\beta:=A_1\cap I_\beta$ is finite for all $\beta\in A_1$. There are two cases to consider:

• If $\{ x_\beta\mid \beta\in A_1\}$ is countable, then $B:=A_1\setminus\bigcup\{ x_\beta\mid \beta\in A_1\}$ is an uncountable subset with the desired property;
• Otherwise, let $A_2$ be an uncountable subset of $A_1$ for which $\{ x_\beta\mid \beta\in A_2\}$ forms a $\Delta$-system with root $r$. As the sets in $\{ (x_\beta\setminus r)\mid  \beta\in A_2\}$ are mutually disjoint, we get that $\sup\{ \min(x_\beta\setminus r)\mid  \beta\in A_2\}=\omega_1$, so it is possible to recursively construct an uncountable subset $B\subseteq(A_2\setminus r)$ such that $\alpha\not\in x_\beta$ for all $\alpha<\beta$ in $B$.  $\square$

Lemma 2. If $\mathfrak b>\aleph_1$, then $\mathcal I(Z)$ is a P-ideal for every $Z\subseteq\omega_1$.

[Reminder. The cardinal $\mathfrak b$ is defined as the smallest size of a family $\mathcal B\subseteq{}^\omega\omega$ with the property that for every $f:\omega\rightarrow\omega$, there exists some $b\in\mathcal B$ such that $\{ n<\omega\mid f(n)<b(n)\}$ is infinite. We say that an ideal $\mathcal I$ is a P-ideal if for every $\mathcal A\in[\mathcal I]^{\aleph_0}$, there exists some $B\in\mathcal I$ such that $A\setminus B$ is finite for all $A\in\mathcal A$. (slang: every countable collection of $\mathcal I$-sets, admits a pseudounion within $\mathcal I$).]

Proof of Lemma 2.  If $Z$ is countable, then $\mathcal I(Z)=\mathcal P(Z)$, and we are done. Now, suppose that $Z$ is uncountable, and that we are given a countable subcollection $\{ X_n\mid n<\omega\}\subseteq\mathcal I$, and let us show that it admits a pseudounion. As $\mathcal I$ is downward closed, we shall avoid trivialities and assume that $\{ X_n\mid n<\omega\}$ are mutually disjoint. Let $\delta<\omega_1$ be large enough so that $$\bigcup_{n<\omega}\{\beta<\omega_1\mid X_n\cap I_\beta\text{ is infinite}\}\subseteq\delta.$$ Fix a bijection $\psi:\omega\rightarrow \bigcup_{n<\omega}X_n$ . Then for all $\beta\in Z\setminus\delta$, define $f_\beta:\omega\rightarrow\omega$ by letting for all $n<\omega$: $$f_\beta(n):=\min\{ m<\omega\mid X_n\cap I_\beta\subseteq \psi“m\}.$$

As $\mathfrak b>\omega_1$, we may pick a function $f:\omega\rightarrow\omega$ such that $\{ n<\omega\mid f_\beta(n)> f(n)\}$ is finite, for all $\beta\in Z\setminus\delta$. Now, let $X:=\bigcup\{X_n\setminus \psi[f(n)]\mid n<\omega\}$. Then, for every $n<\omega$, $X_n\setminus X\subseteq \psi[f(n)]$ is finite. Assume towards a contradiction that $X\not\in\mathcal I$. Then, in particular, there exists some $\beta\in Z\setminus\delta$ such that $I_\beta\cap X$ is infinite. As $f_\beta\le^* f$ while $I_\beta\cap X_n$ is finite for all $n<\omega$, let us pick a large enough $n<\omega$ such that $f_\beta(n)\le f(n)$ and $(I_\beta\cap X)\cap X_n\neq\emptyset$. Pick $\gamma\in I_\beta\cap X\cap X_n$, and let $m:=\psi^{-1}(\gamma)$. Since $\gamma\in I_\beta\cap X_n$, we get that $f_\beta(n)>m$. In particular, $f(n)>m$, and so by definition of $X$, we get that $\psi(m)\not\in X$, contradicting the choice of $\gamma=\psi(m)$ in $X$. $\square$

Lemma 3. Suppose that $A\subseteq Z\subseteq\omega_1$ satisfies $[A]^{\aleph_0}\cap\mathcal I(Z)=\emptyset$.  Denote $$\mathcal F(A,Z):=\left\{ F\in[Z]^{<\omega}\mid \left(A\setminus \bigcup_{\beta\in F}I_\beta\right)\text{ is finite }\right\}.$$ If $\mathfrak p>\aleph_1=|Z|>|A|$, then $\sup\{\min(F)\mid F\in\mathcal F(A,Z)\}=\omega_1$.

[Reminder. The cardinal $\mathfrak p$ is defined as the smallest size of a family $\mathcal A$ of subsets of $\omega$ such that $|\bigcap\mathcal F|=\aleph_0$ for all finite $\mathcal F\subseteq\mathcal A$, while $\mathcal A$ does not admit a pseudointersection. (A pseudointersection for $\mathcal A$ is an infinite set $B$ such that $B\setminus A$ is finite for all $A\in\mathcal A$). Note that $\mathfrak b\ge\mathfrak p$.]
Proof of Lemma 3. Suppose not, and let $\delta:=\sup\{\min(F)\mid F\in\mathcal F(A,Z)\}$. Then, the intersection of any finite family of sets from $\{ A\setminus I_\beta\mid \beta\in Z\setminus\delta+1\}$ is infinite. Then, by $\mathfrak p>\omega_1$, there must exist a pseudointersection $B\subseteq A$, namely, $B\setminus( A\setminus I_\beta)$ is finite whenever $\beta\in Z\setminus\delta+1$. In particular, $\{ \beta\in Z\mid B\cap I_\beta\text{ is finite}\}$ is co-countable, and then $B\in\mathcal I(Z)$, contradicting the fact that $B\subseteq A$, and $[A]^{\aleph_0}\cap\mathcal I(Z)=\emptyset$. $\square$

Lemma 4 (Laver, 1973). For every nonzero $\alpha<\omega_1$, and every matrix $\langle A_{i,\zeta}\mid i<n,\zeta<\kappa\rangle$, if all of the following conditions are met:

1. $n<\omega$;
2. $\kappa<\mathfrak p$;
3. $\bigcup_{i<n}A_{i,\zeta}=\omega^\alpha$ for all $\zeta<\kappa$,

then, there exists a function $f:\kappa\rightarrow n$ and a set $B\subseteq\omega^\alpha$ of order-type $\omega^\alpha$ such that $B\subseteq^* A_{f(\zeta),\zeta}$ for all $\zeta<\kappa$. (By $B\subseteq^*A$, we mean that $\sup(B\setminus A)<\sup(B)$.)

Proof. By induction on $\alpha$. For the base case $\alpha=1$, fix a uniform ultrafilter $\mathcal F$ over $\omega$. Then, let $f:\kappa\rightarrow n$ be a function such that $A_{f(\zeta),\zeta}\in\mathcal F$ for all $\zeta<\kappa$. As $\kappa<\mathfrak p$, the collection $\{ A_{f(\zeta),\zeta}\mid \zeta<\kappa\}$ must admit a pseudointersection.
Next, suppose that $1<\alpha<\omega_1$, and that the lemma holds for all $\beta<\alpha$. Let $\langle \beta_m\mid m<\omega\rangle$ be a non-decreasing sequence of ordinals such that $1\le\beta_m<\alpha$ for all $m<\omega$, and $\sum_{m<\omega}\omega^{\beta_m}=\omega^\alpha$. Denote  $$A^m_{i,\zeta}:=A_{i,\zeta}\cap\left(\left(\sum_{k\le m}\omega^{\beta_k}\right)\setminus\left(\sum_{k< m}\omega^{\beta_k}\right)\right).$$ Then $A^m_{i,\zeta}$ is simply the $m_{th}$-section of $A_{i,\zeta}$. In particular:

• $A_{i,\zeta}=\uplus_{m<\omega}A^m_{i,\zeta}$ for all $i<n$ and $\zeta<\kappa$;
• $\text{otp}(\bigcup_{i<n}A^m_{i,\zeta})=\omega^{\beta_m}$ for all $m<\omega$, and $\zeta<\kappa$.

By the induction hypothesis, for every $m<\omega$, there exists a function $f_m:\kappa\rightarrow n$ such that $\left\{ A^m_{f_m(\zeta),\zeta}\mid \zeta<\kappa\right\}$ admits a pseduointersection $B_m$ of order-type $\omega^{\beta_m}$. In particular, $\sup(B_m)=\sum_{k\le m}\omega^{\beta_k}$. For all $m<\omega$, let $\langle \beta^j_m\mid j<\omega\rangle$ be an increasing sequence of ordinals that converges to $\sum_{k\le m}\omega^{\beta_k}$. Then, for all $\zeta<\kappa$, define a function $h_\zeta:\omega\rightarrow\omega$, by letting:

$$h_\zeta(m):=\min\left\{ j<\omega\mid \left(B_m\setminus A^m_{f_m(\zeta),\zeta}\right)\subseteq \beta^j_m\right\},\quad(m<\omega).$$

As $\kappa<\mathfrak p\le\mathfrak b$, let us pick function $h:\omega\rightarrow\omega$ such that $\{ m<\omega\mid h(m)<h_\zeta(m)\}$ is finite for all $\zeta<\kappa$. Next, we shall utilize the fact that $\{ f_m(\zeta)\mid m<\omega\}$ is finite for all $\zeta<\kappa$. Fix a uniform ultrafilter $\mathcal F$ over $\omega$, and then a function $g:\kappa\rightarrow n$ such that for all $\zeta<\kappa$:$$\{ m<\omega \mid f_m(\zeta)=g(\zeta)\}\in\mathcal F.$$
As $\kappa<\mathfrak p$, we may then find an infinite $M\subseteq\omega$ such that $\{ m\in M\mid f_m(\zeta)\neq g(\zeta)\}$ is finite for all $\zeta<\kappa$. Finally, appeal to $h$, and $M$, by letting $$B:=\biguplus\{ B_m\setminus \beta_m^{h(m)}\mid m\in M\}.$$ Then:

• $\text{otp}(B_m\setminus \beta_m^{h(m)})=\text{otp}(B_m)=\omega^{\beta_m}$ for all $m\in M$, since $\beta_m^{h(m)}<\sum_{k\le m}\omega^{\beta_k}=\sup(B_m)$ ;
• $\text{otp}(B)=\sum_{m\in M}\omega^{\beta_m}=\omega^\alpha$, since $\sup(M)=\omega$.

Thus, we are left with verifying that $B$ is indeed a pseudointersection of $\{ A_{g(\zeta),\zeta}\mid \zeta<\kappa\}$. For this, fix an arbitrary $\zeta<\kappa$. Let $t<\omega$ be large enough so that $$t>\max\{ m\in M\mid h(m)<h_\zeta(m)\ \&\ f_m(\zeta)\neq g(\zeta)\}.$$ We claim that $(B\setminus A_{g(\zeta),\zeta})\subseteq\sum_{k\le t}\omega^{\beta_k}<\omega^\alpha$. Suppose not, and fix $\delta\in (B\setminus A_{g(\zeta),\zeta})$ above $\sum_{k\le t}\omega^{\beta_k}$. Let $m\in M$ be the unique integer such that $\delta\in B_m \setminus \beta_m^{h(m)}$. Then $m>t$ and hence $h_\zeta(m)\le h(m)$, and $f_m(\zeta)=g(m)$. It follows that $$\delta\in\left(B_m\setminus A_{g(\zeta),\zeta}\right)\subseteq\left(B_m\setminus A^m_{g(\zeta),\zeta}\right)=\left(B_m\setminus A^m_{f_m(\zeta),\zeta}\right)\subseteq \beta^{h_\zeta(m)}_m\subseteq \beta^{h(m)}_m,$$contradicting the fact that $\delta\in B$. $\square$

Definition (Todorcevic). The P-ideal Dichotomy (abbreviated PID) asserts that for every uncountable set $Z$, and every P-Ideal $\mathcal I$ over $[Z]^{\le\aleph_0}$, exactly one of the following holds:

• There exists an uncountable $A\subseteq Z$ such that $[A]^{\aleph_0}\subseteq\mathcal I$;
• There exists a sequence $\langle Z_n\mid n<\omega\rangle$ such that $\bigcup_{n<\omega}Z_n=Z$, and $[Z_n]^{\aleph_0}\cap\mathcal I=\emptyset$ for all $n<\omega$.

Now, we are ready to prove the main result of this post.

Theorem (Todorcevic, 1983). Assume PID+($\mathfrak p>\omega_1$). Then $\omega_1\rightarrow(\omega_1,\alpha)^2$ holds for all $\alpha<\omega_1$.
Proof. We prove $\omega_1\rightarrow(\omega_1,\omega^\alpha)^2$ by induction on $\alpha<\omega_1$. The base case $\alpha=1$, is covered by the original Dushnik-Miller theorem. Next, suppose that $1<\alpha<\omega_1$, and that $\omega_1\rightarrow(\omega_1,\omega^\beta)^2$ holds for all $\beta<\alpha$, and let us establish $\omega_1\rightarrow(\omega_1,\omega^\alpha)^2$. For this, suppose that $c:[\omega_1]^2\rightarrow 2$ is a given coloring such that $c“[B]^2\neq\{0\}$ for every uncountable subset $B\subseteq\omega_1$.
For all $\beta<\omega_1$, denote $I_\beta:=\{\gamma<\beta\mid c(\gamma,\beta)=1\}$. Then $c(\gamma,\beta)=0$ iff $\gamma\not\in I_\beta$. In particular, we infer from Lemma 1 that for every uncountable $A\subseteq Z\subseteq\omega_1$, $[A]^{\aleph_0}\nsubseteq\mathcal I(Z)$. Namely, the first alternative of the P-ideal dichotomy fails for $\mathcal I(Z)$. As we assume PID$+(\mathfrak p>\omega_1)$, and since $\mathfrak b\ge\mathfrak p$, we infer from Lemma 2 that for every uncountable $Z\subseteq\omega_1$, there exists a sequence $\langle Z_n\mid n<\omega\rangle$ such that $\bigcup_{n<\omega}Z_n=Z$, and $[Z_n]^{\aleph_0}\cap\mathcal I(Z)=\emptyset$ for all $n<\omega$.
Altogether, we conclude that for every uncountable set $ Z\subseteq\omega_1$, there exists an uncountable subset $Y\subseteq Z$ such that $[Y]^{\aleph_0}\cap\mathcal I(Z)=\emptyset$.

Next, fix a non-decreasing sequence of ordinals $\langle \alpha_m\mid m<\omega\rangle$ such that $1\le\alpha_m<\alpha$ for all $m<\omega$ and $\sum_{m<\omega}\omega^{\alpha_m}=\omega^\alpha$. We shall construct by recursion on $m<\omega$, a sequence $\langle (A_m,B_{m},\tau_{m},Z_m,Y_m,X_m)\mid m<\omega\rangle$, such that all of the following holds for all $m<\omega$;

• $B_{m}\subseteq A_m\subseteq Y_m\subseteq Z_m\supseteq X_m\supseteq Z_{m+1}$;
• $\text{otp}(B_m)=\text{otp}(A_m)=\omega^{\alpha_m}$;
• $\text{otp}(Y_m)=\text{otp}(Z_m)=\text{otp}(X_m)=\omega_1$;
• $\tau_{m}<\sup(B_{m})<\min(B_{m+1})$;
• $c“[B_{m}]^2=\{1\}$;
• $c“[(B_{m}\setminus\tau_{m})\times X_{m}]=\{1\}$.

Let $Z_0=\omega_1$. Then, let $Y_0$ be an uncountable subset of $Z_0$ such that $[Y_0]^{\aleph_0}\cap\mathcal I(Z_0)=\emptyset$. By the induction hypothesis, pick $A_0\subseteq Y_0$ of order-type $\omega^{\alpha_0}$ such that $c“[A_0]^2=\{1\}$. Since $[A_0]^{\aleph_0}\cap\mathcal I(Z_0)=\emptyset$, we get from Lemma 3 that $\mathcal F(A_0,Z_0)$ contains an uncountable family $\mathcal F_0\subseteq[Z_0]^{<\omega}$ consisting of mutually-disjoint sets of some fixed size $n$. Then, by Lemma 4, there exists a choice function $f_0:\mathcal F_0\rightarrow Z_0$ and $B_0\subseteq A_0$ of order-type $\omega^{\alpha_0}$ such that $B_0\subseteq^* I_{f_0(F)}$ for all $F\in\mathcal F_0$. Fix $\tau_0<\sup(B_0)$, and an uncountable subset $X_0\subseteq\text{rng}(f_0)$ such that $(B_0\setminus\tau_0)\subseteq I_\beta$ for all $\beta\in X_0$.
Now, suppose that $m<\omega$ is given, and $(A_m,B_{m},\tau_{m},Z_m,Y_m,X_m)$ has already been defined. Let us define $(A_{m+1},B_{m+1},\tau_{m+1},Z_{m+1},Y_{m+1},X_{m+1})$. Put $Z_{m+1}:=X_m$. Pick $Y_{m+1}\in[Z_{m+1}\setminus(\sup(B_m)+1)]^{\aleph_1}$ such that $[Y_{m+1}]^{\aleph_0}\cap\mathcal I(Z_{m+1})=\emptyset$. Pick $A_{m+1}\subseteq Y_{m+1}$ of order-type $\omega^{\alpha_{m+1}}$ such that $c“[A_{m+1}]^2=\{1\}$. Then, use Lemma 4 to find $B_{m+1}\subseteq A_{m+1}$ of order-type $\omega^{\alpha_{m+1}}$, $\tau_{m+1}<\sup(B_{m+1})$, and an uncountable $X_{m+1}\subseteq Z_{m+1}$ such that $c“[(B_{m+1}\setminus\tau_{m+1})\times X_{m+1}]^2=\{1\}$. This completes the construction.

Finally, let $B:=\bigcup_{n<\omega}(B_n\setminus\tau_n)$. Then $\text{otp}(B)=\omega^\alpha$, and $c“[B]^2=\{1\}$. $\square$