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\to ({\omega }_1,\omega +1{)}^2$ holds in ZFC;
• ${\omega }_1\to ({\omega }_1,\omega +2{)}^2$ may consistently fail;
• ${\omega }_1\to ({\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\to ({\omega }_1,\alpha {)}^2$ for all $\alpha <{\omega }_1$.

We commence with a sequence of lemmas.

Lemma 1.  Suppose that $⟨I_{\beta }\mid \beta <{\omega }_1⟩$ 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 {\mathrm{\aleph }}_0}\mid |\{\beta \in Z\mid X\cap I_{\beta }\text{ is infinite}\}|\le {\mathrm{\aleph }}_0\}.$$

If $A\subseteq Z\subseteq {\omega }_1$ are uncountable sets, and $[A{]}^{{\mathrm{\aleph }}_0}\subseteq \mathcal{I}(Z)$, then there exists some uncountable $B\subseteq A$ such that $\alpha \notin 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\to 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 $\mathrm{\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 \notin x_{\beta }$ for all $\alpha <\beta$ in $B$.  $\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/15.0.3/svg/25fb.svg">}$

Lemma 2. If $\mathfrak{b}>{\mathrm{\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 \to \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}{]}^{{\mathrm{\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 \to \bigcup _{n<\omega }{X}_n$ . Then for all $\beta \in Z\setminus \delta$, define $f_{\beta }:\omega \to \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 \to \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\notin \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 }^{\ast }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\ne \mathrm{\varnothing }$. 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)\notin X$, contradicting the choice of $\gamma =\psi (m)$ in $X$. $\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/15.0.3/svg/25fb.svg">}$

Lemma 3. Suppose that $A\subseteq Z\subseteq {\omega }_1$ satisfies $[A{]}^{{\mathrm{\aleph }}_0}\cap \mathcal{I}(Z)=\mathrm{\varnothing }$.  Denote $$\mathcal{F}(A,Z):=\{F\in [Z{]}^{<\omega }\mid (A\setminus \bigcup _{\beta \in F}{I}_{\beta })\text{ is finite }\}.$$ If $\mathfrak{p}>{\mathrm{\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}|={\mathrm{\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{]}^{{\mathrm{\aleph }}_0}\cap \mathcal{I}(Z)=\mathrm{\varnothing }$. $\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/15.0.3/svg/25fb.svg">}$

Lemma 4 (Laver, 1973). For every nonzero $\alpha <{\omega }_1$, and every matrix $⟨A_{i,\zeta }\mid i<n,\zeta <\kappa ⟩$, 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 \to n$ and a set $B\subseteq {\omega }^{\alpha }$ of order-type ${\omega }^{\alpha }$ such that $B{\subseteq }^{\ast }{A}_{f(\zeta ),\zeta }$ for all $\zeta <\kappa$. (By $B{\subseteq }^{\ast }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 \to 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 $⟨{\beta }_m\mid m<\omega ⟩$ 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_{i,\zeta }^m:=A_{i,\zeta }\cap (\left(\sum _{k\le m}{\omega }^{{\beta }_k}\right)\setminus \left(\sum _{k<m}{\omega }^{{\beta }_k}\right)).$$ Then $A_{i,\zeta }^m$ is simply the $m_{th}$-section of $A_{i,\zeta }$. In particular:

• $A_{i,\zeta }={\uplus }_{m<\omega }{A}_{i,\zeta }^m$ for all $i<n$ and $\zeta <\kappa$;
• $\text{otp}(\bigcup _{i<n}{A}_{i,\zeta }^m)={\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 \to n$ such that $\{A_{f_m(\zeta ),\zeta }^m\mid \zeta <\kappa \}$ 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 $⟨{\beta }_m^j\mid j<\omega ⟩$ 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 \to \omega$, by letting:

$$h_{\zeta }(m):=min\{j<\omega \mid (B_m\setminus A_{f_m(\zeta ),\zeta }^m)\subseteq {\beta }_m^j\},(m<\omega ).$$

As $\kappa <\mathfrak{p}\le \mathfrak{b}$, let us pick function $h:\omega \to \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 \to 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 )\ne g(\zeta )\}$ is finite for all $\zeta <\kappa$. Finally, appeal to $h$, and $M$, by letting $$B:=⨄\{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)\mathrm{\&}{f}_m(\zeta )\ne 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 (B_m\setminus A_{g(\zeta ),\zeta })\subseteq (B_m\setminus A_{g(\zeta ),\zeta }^m)=(B_m\setminus A_{f_m(\zeta ),\zeta }^m)\subseteq {\beta }_m^{h_{\zeta }(m)}\subseteq {\beta }_m^{h(m)},$$contradicting the fact that $\delta \in B$. $\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/15.0.3/svg/25fb.svg">}$

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

• There exists an uncountable $A\subseteq Z$ such that $[A{]}^{{\mathrm{\aleph }}_0}\subseteq \mathcal{I}$;
• There exists a sequence $⟨Z_n\mid n<\omega ⟩$ such that $\bigcup _{n<\omega }{Z}_n=Z$, and $[Z_n{]}^{{\mathrm{\aleph }}_0}\cap \mathcal{I}=\mathrm{\varnothing }$ 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\to ({\omega }_1,\alpha {)}^2$ holds for all $\alpha <{\omega }_1$.
Proof. We prove ${\omega }_1\to ({\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\to ({\omega }_1,{\omega }^{\beta }{)}^2$ holds for all $\beta <\alpha$, and let us establish ${\omega }_1\to ({\omega }_1,{\omega }^{\alpha }{)}^2$. For this, suppose that $c:[{\omega }_1{]}^2\to 2$ is a given coloring such that $c“[B{]}^2\ne \{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 \notin I_{\beta }$. In particular, we infer from Lemma 1 that for every uncountable $A\subseteq Z\subseteq {\omega }_1$, $[A{]}^{{\mathrm{\aleph }}_0}⊈\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 $⟨Z_n\mid n<\omega ⟩$ such that $\bigcup _{n<\omega }{Z}_n=Z$, and $[Z_n{]}^{{\mathrm{\aleph }}_0}\cap \mathcal{I}(Z)=\mathrm{\varnothing }$ 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{]}^{{\mathrm{\aleph }}_0}\cap \mathcal{I}(Z)=\mathrm{\varnothing }$.

Next, fix a non-decreasing sequence of ordinals $⟨{\alpha }_m\mid m<\omega ⟩$ 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 $⟨(A_m,B_m,{\tau }_m,Z_m,Y_m,X_m)\mid m<\omega ⟩$, 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{]}^{{\mathrm{\aleph }}_0}\cap \mathcal{I}(Z_0)=\mathrm{\varnothing }$. 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{]}^{{\mathrm{\aleph }}_0}\cap \mathcal{I}(Z_0)=\mathrm{\varnothing }$, 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\to Z_0$ and $B_0\subseteq A_0$ of order-type ${\omega }^{{\alpha }_0}$ such that $B_0{\subseteq }^{\ast }{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){]}^{{\mathrm{\aleph }}_1}$ such that $[Y_{m+1}{]}^{{\mathrm{\aleph }}_0}\cap \mathcal{I}(Z_{m+1})=\mathrm{\varnothing }$. 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\}$. $\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/15.0.3/svg/25fb.svg">}$