Comparing rectangles with squares through rainbow sets

In Todorcevic’s class last week, he proved all the results of Chapter 8 from his Walks on Ordinals book, up to (and including) Theorem 8.1.11. The upshots are as follows:

• Every regular infinite cardinal $\theta$ admits a naturally defined function $osc:[\mathcal{P}(\theta ){]}^2\to \omega$;
• there exists, again natural, notion of unbounded subfamily of $\mathcal{P}(\theta )$, and if $\mathcal{X}$ is an unbounded subfamily of $\mathcal{P}(\theta )$, then $osc“[\mathcal{X}{]}^2=\omega$;
• if $\theta =cf(\theta )>\omega$ carries a non-trivial $C$-sequence (i.e., a sequence $⟨C_{\alpha }\mid \alpha <\theta ⟩$ such that $C_{\alpha }$ is a club in $\alpha$ for all limit $\alpha <\theta$, and such that for every club $D\subseteq \theta$, there exists an accumulation point $\alpha$ of $D$ such that $D\cap \alpha ⊈C_{\beta }$ for all $\beta <\theta$), then, roughly speaking, there is a way to convert cofinal sets $A\subseteq \theta$ into sets $A^{\prime }$ for which $⟨C_{\alpha }\mid \alpha \in A^{\prime }⟩$ forms an unbounded subfamily of $\mathcal{P}(\theta )$;
• building on the previous item, one can prove that every regular uncountable cardinal $\theta$ that carries a non-trivial $C$-sequence, admits a function $o:[\theta {]}^2\to \omega$ with the property that $o“[A{]}^2=\omega$ for every cofinal $A\subseteq \theta$.

I asked the lecturer whether a rectangular version of the above theorems is known. He started by saying that (in general) there is a huge difference between rectangular properties and square properties, and then provided the following:

• if $\mathcal{X},\mathcal{Y}$ are unbounded subfamilies of $\mathcal{P}(\theta )$, then $osc[\mathcal{X}\times \mathcal{Y}]$ is co-finite;
• it is unknown whether there is an analogous way to convert cofinal subsets $A,B$ of $\theta$ to cofinal $A^{\prime },B^{\prime }$ in way that will yield a function $o:[\theta {]}^2\to \omega$ with the property that $o“[A⊛B{]}^2=\omega$ for every cofinal $A,B\subseteq \theta$.

Naturally, after proving that every successor of a singular cardinal admits a function that transforms rectangles into squares, I’ve been periodically looking for a mathematical evidence for this well-agreed “huge” difference between the two forms. Of course, there is this meta-evidence that it took two decades between Todorcevic’s theorem that ${\omega }_1\nrightarrow [{\omega }_1{]}_{{\omega }_1}^2$ holds in ZFC, to Moore’s theorem that ${\omega }_1\nrightarrow [{\omega }_1;{\omega }_1{]}_{{\omega }_1}^2$ holds in ZFC, yet, it was only today that I finally found what I was looking for.

In a plenary lecture at the Logic Colloquium 2008, Lajos Soukup mentions a concept (and results) that allows to contrast the rectangular version with the square version, as follows.

Theorem 1 (Erdos-Hajnal, 1978). If $f$ witnesses ${\omega }_1\nrightarrow [{\omega }_1;{\omega }_1{]}_{\kappa }^2$, then to any coloring $d:[\omega {]}^2\to \kappa$, there exists a strictly-increasing function $\psi :\omega \to {\omega }_1$ such that $$f(\psi (n),\psi (m))=d(n,m),\text{ for all }n<m<\omega .$$

(so $f$ is universal for countable colorings $d:[\omega {]}^2\to \kappa$)

Theorem 2 (Shelah, 1975). CH entails the existence of a coloring $f$ that witnesses ${\omega }_1\nrightarrow [{\omega }_1{]}_{\omega }^2$, while $f\upharpoonright [B{]}^2$ is not injective for every subset $B\subseteq {\omega }_1$ of size $>2$.

(so $f$ does not even embed injections of the form $d:[3{]}^2\to 3$)

Now, this is a huge difference indeed.

Before turning to the proofs, let us introduce the notion of a rainbow set. Given a coloring $f:[\lambda {]}^2\to \kappa$, we say that $X\subseteq \lambda$ is $f$-rainbow if $f\upharpoonright [X{]}^2$ is injective. Then:

• Trivially, every coloring $f:[\lambda {]}^2\to \kappa$ with $\lambda \ge 2$ admits an  $f$-rainbow set of size $2$.
• Theorem 2 asserts that CH entails the existence of a coloring witnessing ${\omega }_1\nrightarrow [{\omega }_1{]}_{\omega }^2$ that does not admit a rainbow set of size $3$. Moreover, Shelah proved that $\mathrm{♢}(E_{\lambda }^{{\lambda }^{+}})$ entails the existence of a coloring witnessing ${\lambda }^{+}\nrightarrow [{\lambda }^{+}{]}_{{\lambda }^{+}}^2$ that does not admit a rainbow set of size $3$. According to Hajnal, it is unknown whether these hypotheses are necessary.
• By Theorem 1, every coloring witnessing ${\omega }_1\nrightarrow [{\omega }_1;{\omega }_1{]}_{\omega }^2$ admits an infinite rainbow set. Hajnal proved that the same conclusion holds for coloring witnessing ${\omega }_1\nrightarrow [{\omega }_1,{\omega }_1{]}_{\omega }^2$.
• In his paper, Soukup points out that CH entails a coloring witnessing ${\omega }_1\nrightarrow [\omega ;{\omega }_1{]}_{{\omega }_1}^2$ that does not admit an uncountable rainbow set. We noticed that any function witnessing ${\omega }_1\nrightarrow [{\omega }_1{]}_{{\omega }_1}^2$ does not admit an uncountable rainbow set. Either of the results shows that Theorem 1 cannot be improved to get universality for uncountable colorings.

Proof of Theorem 1. Suppose that $f$ witnesses ${\omega }_1\nrightarrow [{\omega }_1;{\omega }_1{]}_{\kappa }^2$ (or just ${\omega }_1\nrightarrow [\text{stat}({\omega }_1);\text{stat}({\omega }_1){]}_{\kappa }^2$).

Subclaim. For every sequence $⟨S_n\mid n<\omega ⟩$ of stationary subsets of ${\omega }_1$, and every function $g:\omega \to \kappa$, there exists a sequence $⟨T_n\mid n<\omega ⟩$ such that:

• $T_0\subseteq S_0$ is a singleton;
• $T_n\subseteq S_n$ is stationary whenever $0<n<\omega$;
• $f[T_0⊛T_n]=\{g(n)\}$ whenever $0<n<\omega$;
• $max(T_0)<min(T_n)$ whenever $0<n<\omega$.

Proof of subclaim. Suppose not, as witnessed by $⟨S_n\mid n<\omega ⟩$, and $g$. Then, for every $\alpha \in S_0$, there exists some positive $n<\omega$ such that $f[\{\alpha \}⊛T_n]\ne \{g(n)\}$ for every stationary $T_n\subseteq S_n$. It follows that there exists some positive $m<\omega$, and a stationary $T\subseteq S_0$ such that $f[\{\alpha \}⊛T_m]\ne \{g(m)\}$ for every $\alpha \in T$, and every stationary $T_m\subseteq S_m$. Pick clubs $⟨C_{\alpha }\mid \alpha <{\omega }_1⟩$ such that $C_{\alpha }$ is disjoint from $\{\beta \in S_m\mid f(\alpha ,\beta )=g(m)\}$ for all $\alpha \in T$. Let $C={\mathrm{\Delta }}_{\alpha <{\omega }_1}{C}_{\alpha }$ be the diagonal intersection, and $T_m:=C\cap S_m$. Then for every $(\alpha ,\beta )\in T⊛T_m$, we get that $\beta \in C_{\alpha }$, and hence $f(\alpha ,\beta )\ne g(m)$, contradicting the fact that $f[T⊛T_m]=\kappa$. $\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/15.0.3/svg/25fb.svg">}$

Now, suppose that we are given $d:[\omega {]}^2\to \kappa$. For all $i<\omega$, let $g_i:\omega \to \kappa$ be a function satisfying $g_i(n)=d(i,n)$ whenever $i<n<\omega$. By a recursive application of the preceding subclaim, we may then find a matrix $⟨S_{i,n}\mid i<\omega ,n<\omega ⟩$ such that:

• $S_{0,n}={\omega }_1$ for all $n<\omega$;
• $S_{i+1,i}\subseteq S_{i,i}$ is a singleton for all $i<\omega$;
• $S_{i+1,i+n}\subseteq S_{i,i+n}$ is stationary whenever $i<\omega$ and $0<n<\omega$;
• $f[S_{i+1,i}⊛S_{i+1,i+n}]=\{g_i(n)\}$, whenever $i<\omega$ and $0<n<\omega$;
• $max(S_{i+1,i})<min(S_{i+1,i+n})$, whenever $i<\omega$ and $0<n<\omega$.

Let $\psi :\omega \to {\omega }_1$ be the function satisfying $S_{i+1,i}=\{\psi (i)\}$ for all $i<\omega$. Then, $\psi$ is strictly increasing, and for every $i<n<\omega$, we have $\psi (i)\in S_{i+1,i}$ and $\psi (n)\in S_{i+1,n}$, and hence $$f(\psi (i),\psi (n))=g_i(n)=d(i,n).\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/15.0.3/svg/25fb.svg">}$$

Proof of Theorem 2. For all distinct $\eta ,\rho \in {}^{\omega }2$, let $$\mathrm{\Delta }(\eta ,\rho ):=min\{n<\omega \mid \eta (n)\ne \rho (n)\}.$$ Let $h:\omega \to \omega$ be a surjection such that $h^{-1}\{n\}$ is infinite for all $n<\omega$, and then define $f:[{}^{\omega }2{]}^2\to \omega$ by letting for all distinct $\eta ,\rho \in {}^{\omega }2$: $$f(\eta ,\rho ):=h(\mathrm{\Delta }(\eta ,\rho )).$$

It is clear that for every $B\subseteq {}^{\omega }2$ of size $>2$, the function $f\upharpoonright [B{]}^2$ is not injective, hence, our main goal is to find an uncountable $X\subseteq {}^{\omega }2$ for which $f\upharpoonright [X{]}^2$ witnesses ${\omega }_1\nrightarrow [{\omega }_1{]}_{\omega }^2$.

Here goes. By CH, let $\{A_i\mid i<{\omega }_1\}$ be some enumeration of $[{}^{\omega }2{]}^{{\mathrm{\aleph }}_0}$. We now define a family $\{{\eta }_i\mid i<{\omega }_1\}\subseteq {}^{\omega }2$ by recursion on $i<{\omega }_1$.
For the base case, we let ${\eta }_0$ be an arbitrary element of ${}^{\omega }2$.
Now, suppose that $i<{\omega }_1$ is nonzero, and that $\{{\eta }_j\mid j<i\}$ has already been defined. Let

• $\{A_k^i\mid k<\omega \}$ be some enumeration of $\{A_j\mid j<i\}$, and
• $\{{\eta }_k^i\mid k<\omega \}$ be some enumeration of $\{{\eta }_j\mid j<i\}$.

${\eta }_i$ will be defined as the limit of an increasing chain $\{{\rho }_{i,k}\mid k<\omega \}\subseteq {}^{<\omega }2$ which will be set by recursion on $k<\omega$. Of course, we commence with letting ${\rho }_{i,0}:=\mathrm{\varnothing }$.
Next, if $k<\omega$ and ${\rho }_{i,k}$ has been defined, we consider two cases:

1. ${\rho }_{i,k}\subseteq \sigma$ for some $\sigma \in A_{h(k)}^i$. In this case, we fix such $\sigma$ and find a large enough $l<\omega$ such that $|{\rho }_{i,k}|<l$ and $h(l)=|\{t<k\mid h(t)=h(k)\}|$. We then let $${\rho }_{i,k+1}:=(\sigma \upharpoonright l){}^{⌢}⟨1-\sigma (l)⟩{}^{⌢}⟨1-{\eta }_k^i(l+1)⟩.$$
2. otherwise. In this case, we let $l:=|{\rho }_{i,k}|$, and put: $${\rho }_{i,k+1}:={\rho }_{i,k}{}^{⌢}⟨1-{\eta }_k^i(l)⟩.$$

Let ${\eta }_i:=\bigcup _{k<\omega }{\rho }_{i,k}$. Then, ${\eta }_i\in {}^{\omega }2$ and for all $k<\omega$, ${\rho }_{i,k+1}\subseteq {\eta }_i$, while ${\rho }_{i,k+1}⊈{\eta }_k^i$. In particular, ${\eta }_i\notin \{{\eta }_j\mid j<i\}$. It follows that $X:=\{{\eta }_i\mid i<{\omega }_1\}$ is uncountable.

Subclaim. $f\upharpoonright [X{]}^2$ witnesses ${\omega }_1\nrightarrow [{\omega }_1{]}_{\omega }^2$.
Proof. Suppose that $A\subseteq X$ is uncountable, and $n<\omega$. We shall prove that $n\in f“[A{]}^2$. Fix a countable elementary submodel $M\prec H_{{\omega }_2}$ with $A\in M$. Let $j<{\omega }_1$ be such that $A_j=A\cap M$. Since $A$ is uncountable, pick a large enough $i\in (j,{\omega }_1)$ such that ${\eta }_i\in A\setminus M$. Let $m<\omega$ be such that $A_j=A_m^i$. Let $K:=\{k<\omega \mid h(k)=m\}$. Let $k$ be the $n_{th}$ element of $K$. Then:

• $h(k)=m$;
• $|\{t<k\mid h(t)=h(k)\}|=n$;
• $A_{h(k)}^i=A\cap M$.

As ${\rho }_{i,k}\in {}^{<\omega }2\subseteq M$ and $A\in M$, we get that $B:=\{\sigma \in A\mid {\rho }_{i,k}\subseteq \sigma \}$ is in $M$. Since ${\eta }_i$ witnesses that $B$ is non-empty, we infer the existence of some $\sigma \in A\cap M$ such that ${\rho }_{i,k}\subseteq \sigma$. So, ${\rho }_{i,k+1}$ has been defined according to case 1, and there exists some $\sigma \in A\cap M$ and $l<\omega$ such that

• $h(l)=|\{t<k\mid h(t)=h(k)\}|=n$, and
• ${\eta }_i\upharpoonright (l+1)=(\sigma \upharpoonright l){}^{⌢}⟨1-\sigma (l)⟩$.

It follows that $\mathrm{\Delta }(\sigma ,{\eta }_i)=l$, and hence $f(\sigma ,{\eta }_i)=h(l)=n$. $\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/15.0.3/svg/25fb.svg">}$ $\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/15.0.3/svg/25fb.svg">}$

Remark: The above usage of an elementary submodel was an overkill. All one needs to know is that the Cantor space is hereditary separable, and hence there exists some $j<{\omega }_1$ such that $A_j$ is a dense subspace of $A$. That is, $A_j\subseteq A$, $|A_j|={\mathrm{\aleph }}_0$, and yet $$\{\sigma \upharpoonright n\mid \sigma \in A_j,n<\omega \}=\{\sigma \upharpoonright n\mid \sigma \in A,n<\omega \}.$$

Proof of Soukup’s theorem. Recall the original construction of Erdos-Hajnal-Milner from CH of a function witnessing ${\omega }_1\nrightarrow [\omega ;{\omega }_1{]}_{{\omega }_1}^2$. Let $\{A_{\gamma }\mid \gamma <{\omega }_1\}$ be some enumeration of $[{\omega }_1{]}^{{\mathrm{\aleph }}_0}$. For all infinite $\beta <{\omega }_1$ do the following:

• fix a surjection ${\psi }_{\beta }:\omega \to \beta$ such that ${\psi }_{\beta }^{-1}\{\gamma \}$ is infinite for all $\gamma <\beta$;
• pick an injection ${\varphi }_{\beta }:\omega \to {\omega }_1$ such that ${\varphi }_{\beta }(i)\in A_{{\psi }_{\beta }(i)}$ for all $i<\omega$. This can be done recursively, where at step $i<\omega$, we utilize the fact that $$|{\varphi }_{\beta }[i]|=|i|<{\mathrm{\aleph }}_0=|A_{{\psi }_{\beta }(i)}|.$$
• for all $\gamma <\beta$, denote $A_{\gamma ,\beta }:=\{{\varphi }_{\beta }(i)\mid {\psi }_{\beta }(i)=\gamma \}$. Then $A_{\gamma ,\beta }$ is an infinite subset of $A_{\gamma }$, and ${\gamma }_1<{\gamma }_2<\beta$ implies $A_{{\gamma }_1,\beta }\cap A_{{\gamma }_2,\beta }=\mathrm{\varnothing }$.
• for all $\gamma <\beta$, fix a surjection $g_{\gamma ,\beta }:A_{\gamma ,\beta }\to \beta$.

Finally, pick a function $f:[{\omega }_1{]}^2\to {\omega }_1$ such that for all $\alpha <\beta <{\omega }_1$:

$$f(\alpha ,\beta )=\{\begin{array}{ll}0,& \alpha \notin \bigcup _{\gamma <\beta }{A}_{\gamma ,\beta }\\ g_{\gamma ,\beta }(\alpha ),& \alpha \in A_{\gamma ,\beta }\end{array}.$$

Subclaim. $f$ witnesses ${\omega }_1\nrightarrow [\omega ;{\omega }_1{]}_{{\omega }_1}^2$.
Proof. Suppose that $Y$ is an infinite countable subset of ${\omega }_1$, $Z$ is an uncountable subset of ${\omega }_1$, and $\delta <{\omega }_1$. We shall show that $\delta \in f[Y⊛Z]$.

Fix $\gamma <{\omega }_1$ such that $A_{\gamma }=Y$. Pick a large enough $\beta \in Z$ such that $\beta >max\{\gamma ,\delta ,sup(Y)\}$.

Since $\delta <\beta$ and $g_{\gamma ,\beta }:A_{\gamma ,\beta }\to \beta$ is surjective, we may now pick $\alpha \in A_{\gamma ,\beta }$
such that $g_{\gamma ,\beta }(\alpha )=\delta$. Then $\alpha \in A_{\gamma ,\beta }\subseteq Y\cap \beta$ and $$f(\alpha ,\beta )=g_{\gamma ,\beta }(\alpha )=\delta .\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/15.0.3/svg/25fb.svg">}$$

It now follows from the upcoming observation that the function just constructed does not admit an uncountable rainbow set. $\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/15.0.3/svg/25fb.svg">}$

Observation. If $f$ witnesses $\kappa \nrightarrow [\kappa {]}_{\theta }^2$, then $f$ does not admit a rainbow set of size $min\{\kappa ,{\theta }^{+}\}$.
Proof. Given a set $X$ of size $\kappa$, decompose $X$ as $X_0\uplus X_1$, such that $X_i$ is of size $\kappa$, for all $i<2$. Then $f“[X_0{]}^2=\theta$ and $f“[X_1{]}^2=\theta$. In particular $f\upharpoonright [X_0\cup X_1{]}^2$ is not injective. Given a set $X$ of size ${\theta }^{+}$, it is trivial that $f\upharpoonright [X{]}^2:[X{]}^2\to \theta$ is not injective. $\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/15.0.3/svg/25fb.svg">}$