This post continues the study of the cardinal invariant $\mathfrak p$. We refer the reader to a previous post for all the needed background. For ordinals $\alpha,\alpha_0,\alpha_1,\beta,\beta_0,\beta_1$, the polarized partition relation $$\left(\begin{array}{c}\alpha\\\beta\end{array}\right)\rightarrow\left(\begin{array}{cc}\alpha_0&\alpha_1\\\beta_0&\beta_1\end{array}\right)$$ asserts that for every coloring $f:\alpha\times\beta\rightarrow 2$, (at least) one of the following holds:
- there are $A\subseteq\alpha$ and $B\subseteq\beta$ with $\text{otp}(A)=\alpha_0, \text{otp}(B)=\beta_0$ s.t. $f[A\times B]=\{0\}$;
- there are $A\subseteq\alpha$ and $B\subseteq\beta$ with $\text{otp}(A)=\alpha_1, \text{otp}(B)=\beta_1$ s.t. $f[A\times B]=\{1\}$.
Erdős and Rado proved that $$\left(\begin{array}{c}\omega_1\\\omega\end{array}\right)\rightarrow\left(\begin{array}{cc}\omega_1&n\\\omega&\omega\end{array}\right)$$ holds for all $n<\omega$. The current post will center around a proof of the following relative:
Theorem (A.L. Jones, 2008). For all $\alpha<\mathfrak p$: $$\left(\begin{array}{c}\mathfrak p\\\omega\end{array}\right)\rightarrow\left(\begin{array}{cc}\mathfrak p&\alpha\\\omega&\omega\end{array}\right).$$
Proof. Suppose that we are given a coloring $f:\mathfrak p\times\omega\rightarrow 2$. Denote $$1_\tau:=\{ n<\omega\mid f(\tau,n)=1\},$$ and let $X$ be a maximal (with respect to inclusion) subset of $\mathfrak p$ with the property that the intersection of any finite collection of subsets from $\mathcal A_X:=\{ 1_\tau\mid \tau\in X\}$ is infinite. The proof is now divided into two.
$\blacktriangleright$ Suppose that $|X|<\mathfrak p$.
By $|\mathcal A_X|<\mathfrak p$, let us fix an infinite pseudointersection $P$ for $\mathcal A_X$ (indeed, if $X=\emptyset$, we simply take $P:=\omega$). Notice that if $Q\subseteq\omega$ and $P\cap Q$ is infinite, then $Q\cap\bigcap_{\tau\in I}1_\tau$ is infinite for all $I\in[X]^{<\omega}$. Thus, it follows from the maximality of $X$ that $P\cap 1_\tau$ is finite for all $\tau\in\mathfrak p\setminus X$. Put $Y:=\mathfrak p\setminus X$ and define $g:Y\rightarrow[P]^{<\omega}$ by letting $g(\tau):=P\cap 1_\tau$ for all $\tau\in Y$. Then, by $\mathfrak p=\text{cf}(\mathfrak p)>\omega$, we may find a subset $A\subseteq Y$ of size $\mathfrak p$ on which $g$ is constant. In particular, $B:=\bigcap_{\tau\in A}(\omega\setminus 1_\tau)$ contains the infinite set $P\setminus g(\min(A))$.
Altogether, $\text{otp}(A)=\mathfrak p$, $\text{otp}(B)=\omega$, and $f[A\times B]=\{0\}$.
$\blacktriangleright$ Suppose that $|X|=\mathfrak p$.
Let $\langle M_\alpha\mid\alpha<\mathfrak p\rangle$ be a continuous $\epsilon$-chain of elementary submodels of $(\mathcal H(\theta),\in,<_\theta)$ for a large enough regular $\theta$, such that $f,X\in M_0$ and $M_\alpha\cap\mathfrak p\in \mathfrak p$ for all $\alpha<\mathfrak p$.
Suppose that we are given a limit ordinal $\alpha<\mathfrak p$. Pick $\chi\in (X\cap M_{\alpha+1})\setminus M_\alpha$, and consider the poset $\mathbb P:=\langle P,\le\rangle$, where $$P:=\{ (a,b)\in[X\cap M_\alpha]^{<\omega}\times[\omega]^{<\omega}\mid \chi\in a, f[a\times b]=\{1\}\},$$ and $(a_0,b_0)\le (a_1,b_1)$ iff $a_0\subseteq a_1$ and $b_0\subseteq b_1$.
For all $b\in[\omega]^{<\omega}$, put $P_b:=\{ (a’,b’)\in P\mid b’=b\}$. Then $\langle P_b\mid b\in[\omega]^{<\omega}\rangle$ witnesses that $\mathbb P$ is $\sigma$-centered.
For all $n<\omega$, let $$D_n:=\{ (a,b)\in P\mid \max(b)>n\}.$$ Recalling that the intersection of any finite collection of subsets from $\{ 1_\tau\mid \tau\in X\}$ is infinite, we see that $D_n$ is cofinal in $\mathbb P$.
For all $\beta<\alpha$, let $$E_\beta:=\{ (a,b)\in P\mid (a\cap M_{\beta+1})\setminus M_\beta\neq\emptyset\}.$$Then, by $\chi\in(a\cap M_{\alpha+1})\setminus M_\alpha$ for all $(a,b)\in P$, and a standard elementarity argument, we see that $E_\beta$ is cofinal in $\mathbb P$.
Finally, let us pick some subset $G(\alpha)\subseteq P$ such that:
- $\{p\}^\uparrow\cap\{q\}^\uparrow\neq\emptyset$ for all $p,q\in G(\alpha)$;
- $G(\alpha)_\downarrow\cap D_n\neq\emptyset$ for all $n<\omega$;
- $G(\alpha)_\downarrow\cap E_\beta\neq\emptyset$ for all $\beta<\alpha$.
Put $A:=\bigcup\{ a\mid (a,b)\in G(\alpha)\}$ and $B:=\bigcup\{ b\mid (a,b)\in G(\alpha)\}$.
Then item 1 entails that $f[a\times b]=\{1\}$, item 2 entails that $\text{otp}(B)=\omega$, and item 3 entails that $\text{otp}(A)\ge\alpha$. $\square$
Let us point out that the above proof works equally well for stationary sets.
Proposition. For every stationary subset $S$ of a regular uncountable cardinal $\kappa$, and every coloring $f:S\times\omega\rightarrow 2$, one of the following holds:
- there exists a stationary $A\subseteq S$ and an infinite $B\subseteq\omega$ such that $f[A\times B]=\{0\}$;
- for every $\epsilon<\min\{\kappa,\mathfrak p\}$, there exists $A\subseteq S$ of order-type $\epsilon$ and an infinite $B\subseteq\omega$ such that $f[A\times B]=\{1\}$.
Proof (sketch). Given the coloring $f:S\times\omega\rightarrow 2$, let $1_\tau:=\{ n<\omega\mid f(\tau,n)=1\}$. Let $X$ be a maximal subset of $S$ with the property that the intersection of any finite collection of subsets from $\mathcal A_X:=\{ 1_\tau\mid \tau\in X\}$ is infinite.
Write $\mu:=\min\{\kappa,\mathfrak p\}$, and consider two complimentary cases.
$\blacktriangleright$ Suppose that $|X|<\mu$.
Fix an infinite pseudointersection $P$ for $\mathcal A_X$ (or let $P=\omega$ in case that $X$ is empty). Then $P\cap 1_\tau$ is finite for all $\tau\in S\setminus X$. Define $g:S\setminus X\rightarrow[P]^{<\omega}$ by stipulating that $g(\tau):=P\cap 1_\tau$. Then, by $\text{cf}(\kappa)>\omega$, we may find a stationary $A\subseteq S\setminus X$ on which $g$ is constant. Put $B:=\bigcap_{\tau\in A}(\omega\setminus 1_\tau)$. Then $B$ is infinite, and $f[A\times B]=\{0\}$.
$\blacktriangleright$ Suppose that $|X|\ge\mu$.
Fix a limit $\epsilon<\mu$. Let $\langle M_\alpha\mid\alpha<\epsilon+1\rangle$ be a continuous $\epsilon$-chain of elementary submodels with $f,X\in M_0$ and $M_\alpha\cap\mu\in\mu$ for all $\alpha$. Pick $\chi\in X\setminus M_\epsilon$, and consider the poset $\mathbb P:=\langle P,\le\rangle$, where $P:=\{ (a,b)\in[X\cap M_\epsilon]^{<\omega}\times[\omega]^{<\omega}\mid \chi\in a, f[a\times b]=\{1\}\}$, and $(a_0,b_0)\le (a_1,b_1)$ iff $a_0\subseteq a_1$ and $b_0\subseteq b_1$. As before, $\mathbb P$ is $\sigma$-centered. Also, for all $n<\omega$ and $\beta<\epsilon$, the set $$D^\beta_n:=\{ (a,b)\in P\mid (a\cap M_{\beta+1})\setminus M_\beta\neq\emptyset\text{ and }|b|>n\}$$ is cofinal in $\mathbb P$. Thus, by $\epsilon<\mathfrak p$, we can pick a subset $G\subseteq P$ such that $\{p\}^\uparrow\cap\{q\}^\uparrow\neq\emptyset$ for all $p,q\in G$, and $G_\downarrow\cap D^\beta_n\neq\emptyset$ for all $n<\omega$ and $\beta<\epsilon$.
Put $A:=\bigcup\{ a\mid (a,b)\in G(\alpha)\}$ and $B:=\bigcup\{ b\mid (a,b)\in G(\alpha)\}$. Then $B$ is infinite, $\text{otp}(A)\ge\epsilon$, and $f[a\times b]=\{1\}$. $\square$
As $\mathfrak p$ is provably uncountable in ZFC, Jones’ theorem shows that the integer $n$ in the above-cited theorem of Erdos and Rado, may be replaced with any countable ordinal $\alpha$. We conclude this post by addressing the remaining case, that is, the case of $\omega_1$.
Theorem (Sierpiński). CH entails $$\left(\begin{array}{c}\omega_1\\\omega\end{array}\right)\nrightarrow\left(\begin{array}{cc}\omega_1&\omega_1\\\omega&\omega\end{array}\right).$$
Proof. Sierpinski proved in the 1930’s that CH implies the existence of sequence of functions $\langle f_n:\mathbb R\rightarrow\mathbb R\mid n<\omega\rangle$ such that for every uncountable set of reals $A$, there exists some $m<\omega$ such that $f_n[A]=\mathbb R$ for all $n\ge m$. By CH, let us also fix a bijection $\psi:\omega_1\leftrightarrow\mathbb R$. Finally, define $f:\omega_1\times\omega\rightarrow 2$ by letting $f(\tau,n):=0$ iff $f_n(\psi(\tau))=0$.
Then $f$ witnesses the failure of $\left(\begin{array}{c}\omega_1\\\omega\end{array}\right)\rightarrow\left(\begin{array}{cc}\omega_1&\omega_1\\\omega&\omega\end{array}\right)$. $\square$
In contrast:
Theorem (Laver, 1973). $MA_{\aleph_1}$ entails$$\left(\begin{array}{c}\omega_1\\\omega\end{array}\right)\rightarrow\left(\begin{array}{cc}\omega_1&\omega_1\\\omega&\omega\end{array}\right).$$
Moreover, for every ordinal $\kappa<\mathfrak p$ of uncountable cofinality, any nonzero limit ordinal $\alpha<\omega_1$, and any positive integer $n<\omega$ we have:$$\left(\begin{array}{c}\kappa\\\omega^\alpha\end{array}\right)\rightarrow\left(\begin{array}{cc}\kappa\\\omega^\alpha\end{array}\right)_n.$$
Proof. Given a coloring $f:\kappa\times\omega^\alpha\rightarrow n$, write $A_{i,\zeta}:=\{ \beta<\omega^\alpha\mid f(\beta,\zeta)=i\}$. Then by Lemma 4 from a previous post, there exists a function $g:\kappa\rightarrow n$ and a set $B\subseteq\omega^\alpha$ of order-type $\omega^\alpha$ such that $B\subseteq^* A_{g(\zeta),\zeta}$ for all $\zeta<\kappa$. Fix $i^*<n$ such that $g^{-1}\{i^*\}$ is cofinal in $\kappa$, and put $A:=g^{-1}\{i^*\}$. Let $\{ \beta_k \mid k<\omega\}$ be some cofinal subset of $\omega^\alpha$, and then, define $h:A\rightarrow\omega$ by stipulating $$h(\zeta):=\min\{k<\omega\mid (B\setminus\beta_k)\subseteq A_{i^*,\zeta}\}.$$As $\text{cf}(\kappa)>\omega$, let us fix $k^*<\omega$ such that $h^{-1}\{k^*\}$ is cofinal in $\kappa$. Put $A^*:=h^{-1}\{k^*\}$ and $B^*:=B\setminus\beta_{k^*}$. Then $\text{otp}(A^*)=\kappa, \text{otp}(B^*)=\omega^\alpha$, and $f[A\times B]=\{i^*\}$. $\square$
