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\rightarrow\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 $\langle C_\alpha\mid\alpha<\theta\rangle$ 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\nsubseteq C_\beta$ for all $\beta<\theta$), then, roughly speaking, there is a way to convert cofinal sets $A\subseteq\theta$ into sets $A’$ for which $\langle C_\alpha\mid \alpha\in A’\rangle$ 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\rightarrow\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’,B’$ in way that will yield a function $o:[\theta]^2\rightarrow\omega$ with the property that $o“[A\circledast 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]^2_{\omega_1}$ holds in ZFC, to Moore’s theorem that $\omega_1\nrightarrow[\omega_1;\omega_1]^2_{\omega_1}$ 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]^2_{\kappa}$, then to any coloring $d:[\omega]^2\rightarrow\kappa$, there exists a strictly-increasing function $\psi:\omega\rightarrow\omega_1$ such that $$f(\psi(n),\psi(m))=d(n,m),\quad\text{ for all }n<m<\omega.$$

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

Theorem 2 (Shelah, 1975). CH entails the existence of a coloring $f$ that witnesses $\omega_1\nrightarrow[\omega_1]^2_\omega$, while $f\restriction[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\rightarrow 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\rightarrow\kappa$, we say that $X\subseteq\lambda$ is $f$-rainbow if $f\restriction[X]^2$ is injective. Then:

  • Trivially, every coloring $f:[\lambda]^2\rightarrow\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]^2_{\omega}$ that does not admit a rainbow set of size $3$. Moreover, Shelah proved that $\diamondsuit(E^{\lambda^+}_\lambda)$ entails the existence of a coloring witnessing $\lambda^+\nrightarrow[\lambda^+]^2_{\lambda^+}$ 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]^2_{\omega}$ admits an infinite rainbow set. Hajnal proved that the same conclusion holds for coloring witnessing $\omega_1\nrightarrow[\omega_1,\omega_1]^2_{\omega}$.
  • In his paper, Soukup points out that CH entails a coloring witnessing $\omega_1\nrightarrow[\omega;\omega_1]^2_{\omega_1}$ that does not admit an uncountable rainbow set. We noticed that any function witnessing $\omega_1\nrightarrow[\omega_1]^2_{\omega_1}$ 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]^2_{\kappa}$ (or just $\omega_1\nrightarrow[\text{stat}(\omega_1);\text{stat}(\omega_1)]^2_\kappa$).

Subclaim. For every sequence $\langle S_n\mid n<\omega\rangle$ of stationary subsets of $\omega_1$, and every function $g:\omega\rightarrow\kappa$, there exists a sequence $\langle T_n\mid n<\omega\rangle$ such that:

  • $T_0\subseteq S_0$ is a singleton;
  • $T_n\subseteq S_n$ is stationary whenever $0<n<\omega$;
  • $f[T_0\circledast 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 $\langle S_n\mid n<\omega\rangle$, and $g$. Then, for every $\alpha\in S_0$, there exists some positive $n<\omega$ such that $f[\{\alpha\}\circledast T_n]\neq\{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\}\circledast T_m]\neq\{g(m)\}$ for every $\alpha\in T$, and every stationary $T_m\subseteq S_m$. Pick clubs $\langle C_\alpha\mid \alpha<\omega_1\rangle$ such that $C_\alpha$ is disjoint from $\{ \beta\in S_m\mid f(\alpha,\beta)=g(m)\}$ for all $\alpha\in T$. Let $C=\Delta_{\alpha<\omega_1}C_\alpha$ be the diagonal intersection, and $T_m:=C\cap S_m$. Then for every $(\alpha,\beta)\in T\circledast T_m$, we get that $\beta\in C_\alpha$, and hence $f(\alpha,\beta)\neq g(m)$, contradicting the fact that $f[T\circledast T_m]=\kappa$. $\square$

Now, suppose that we are given $d:[\omega]^2\rightarrow\kappa$. For all $i<\omega$, let $g_i:\omega\rightarrow\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 $\langle S_{i,n}\mid i<\omega,n<\omega\rangle$ 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}\circledast 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\rightarrow\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). \square$$


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

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

Here goes. By CH, let $\{ A_i \mid i<\omega_1\}$ be some enumeration of $[{}^\omega2]^{\aleph_0}$. We now define a family $\{ \eta_i\mid i<\omega_1\}\subseteq{}^\omega2$ by recursion on $i<\omega_1$.
For the base case, we let $\eta_0$ be an arbitrary element of ${}^\omega2$.
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}:=\emptyset$.
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\restriction l){}^\frown\langle 1-\sigma(l)\rangle{}^\frown\langle 1-\eta^i_k(l+1)\rangle.$$
  2. otherwise. In this case, we let $l:=|\rho_{i,k}|$, and put: $$\rho_{i,k+1}:=\rho_{i,k}{}^\frown\langle 1-\eta^i_k(l)\rangle.$$

Let $\eta_i:=\bigcup_{k<\omega}\rho_{i,k}$. Then, $\eta_i\in{}^\omega2$ and for all $k<\omega$, $\rho_{i,k+1}\subseteq\eta_i$, while $\rho_{i,k+1}\not\subseteq\eta^i_k$. In particular, $\eta_i\not\in\{\eta_j \mid j<i\}$. It follows that $X:=\{ \eta_i\mid i<\omega_1\}$ is uncountable.

Subclaim. $f\restriction[X]^2$ witnesses $\omega_1\nrightarrow[\omega_1]^2_{\omega}$.
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^i_m$. 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^i_{h(k)}=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\restriction(l+1)=(\sigma\restriction l){}^\frown\langle 1-\sigma(l)\rangle$.

It follows that $\Delta(\sigma,\eta_i)=l$, and hence $f(\sigma,\eta_i)=h(l)=n$. $\square$ $\square$

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|=\aleph_0$, and yet $$\{ \sigma\restriction n\mid \sigma\in A_j, n<\omega\}=\{ \sigma\restriction 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]^2_{\omega_1}$. Let $\{ A_\gamma\mid \gamma<\omega_1\}$ be some enumeration of $[\omega_1]^{\aleph_0}$. For all infinite $\beta<\omega_1$ do the following:

  • fix a surjection $\psi_\beta:\omega\rightarrow\beta$ such that $\psi_\beta^{-1}\{\gamma\}$ is infinite for all $\gamma<\beta$;
  • pick an injection $\phi_\beta:\omega\rightarrow\omega_1$ such that $\phi_\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 $$|\phi_\beta[i]|=|i|<\aleph_0=|A_{\psi_\beta(i)}|.$$
  • for all $\gamma<\beta$, denote $A_{\gamma,\beta}:=\{ \phi_\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}=\emptyset$.
  • for all $\gamma<\beta$, fix a surjection $g_{\gamma,\beta}:A_{\gamma,\beta}\rightarrow\beta$.

Finally, pick a function $f:[\omega_1]^2\rightarrow\omega_1$ such that for all $\alpha<\beta<\omega_1$:

g_{\gamma,\beta}(\alpha),&\alpha\in A_{\gamma,\beta}

Subclaim. $f$ witnesses $\omega_1\nrightarrow[\omega;\omega_1]^2_{\omega_1}$.
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\circledast 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}\rightarrow\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. \square$$

It now follows from the upcoming observation that the function just constructed does not admit an uncountable rainbow set. $\square$

Observation. If $f$ witnesses $\kappa\nrightarrow[\kappa]^2_\theta$, 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\restriction [X_0\cup X_1]^2$ is not injective. Given a set $X$ of size $\theta^+$, it is trivial that $f\restriction[X]^2:[X]^2\rightarrow\theta$ is not injective. $\square$

This entry was posted in Blog and tagged , . Bookmark the permalink.

One Response to Comparing rectangles with squares through rainbow sets

  1. saf says:

    Historical remark (which I learned today from Stevo):
    More than 30 years before the Erdos-Hajnal-Milner paper in which they proved that CH entails $\omega_1\nrightarrow[\omega;\omega_1]^2_{\omega_1}$, Sierpiński proved (see, e.g, chapter I, page 12, in his book), that CH entails the existence of a function $f:\mathbb N\times\mathbb R\rightarrow\mathbb R$ such that $f[A\times X]=\mathbb R$ for every infinite $A\subseteq\mathbb N$ and every uncountable $X\subseteq\mathbb R$. To see that the former follows from the latter, consult page 290 of this paper.


Leave a Reply

Your email address will not be published. Required fields are marked *

+ four = 8

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>