In a paper from 1971, Erdos and Hajnal asked whether (assuming CH) every coloring witnessing $\aleph_1\nrightarrow[\aleph_1]^2_3$ has a rainbow triangle. The negative solution was given in a 1975 paper by Shelah, and the proof and relevant definitions may be found in this previous blog post.
Shelah’s construction of a coloring witnessing $\aleph_1\nrightarrow[\aleph_1]^2_\omega$ with no rainbow triangles was from CH, but there is a finer proof assuming the existence of a Luzin set (see Erdos-Hajnal, 1978). I am not aware of a ZFC construction, but another consistent construction is the following:
Theorem (Todorcevic, 1981). Suppose $\kappa$ is a regular uncountable cardinal, and there exists a $\kappa$-Souslin tree. Then there exists a coloring witnessing $\kappa\nrightarrow[\kappa]^2_\kappa$ that does not admit a rainbow triangle.
The goal of the current post is to present Todorcevic’s proof by relying on the notion of a prolific Souslin tree.
Definition (Brodsky-Rinot). A subset $T\subset{}^{<\kappa}\kappa$ is a prolific $\kappa$-Souslin tree iff $|T|=\kappa$, $(T,\subset)$ has no antichains of size $\kappa$, and for all $t\in T$ and $\beta<\text{dom}(t)$: $t\restriction\beta$ and $t{}^\smallfrown\langle\beta\rangle$ are in $T$.
Remark. The above definition is slightly simpler than the one of our paper, but the two coincide on all tree levels $\ge\omega$.
A folklorish observation asserts that the existence of a $\kappa$-Souslin tree entails the existence of a prolific one. Before we prove this, let us show how to derive Todorcevic’s theorem.
Let $T$ be a prolific $\kappa$-Souslin tree. For every $\alpha<\kappa$, pick $t_\alpha\in T\cap{}^\alpha\kappa$.
For every $\alpha\neq\beta$, denote $$\Delta(\alpha,\beta):=\begin{cases}\min\{\alpha,\beta\},&\text{if }t_\alpha\cup t_\beta\in T;\\
\min\{\varepsilon\mid t_\alpha(\varepsilon)\neq t_\beta(\varepsilon)\},&\text{otherwise}.\end{cases}$$
Finally, define a coloring $c:[\kappa]^2\rightarrow\kappa$ by letting for all $\alpha\neq\beta$:$$c(\alpha,\beta):=\begin{cases}t_\beta(\alpha),&\text{if }t_\alpha\subset t_\beta;\\
t_\alpha(\beta),&\text{if }t_\beta\subset t_\alpha;\\
\min\{t_\alpha(\Delta(\alpha,\beta)),t_\beta(\Delta(\alpha,\beta))\},&\text{otherwise}.\end{cases}$$
Claim 1. $c$ witnesses $\kappa\nrightarrow[\kappa]^2_\kappa$.
That is, for every $X\subseteq\kappa$ of size $\kappa$, we have $c“[X]^2=\kappa$.
Proof. Let $X\subseteq\kappa$ of size $\kappa$ and $i<\kappa$ be arbitrary. We shall find $\alpha<\beta$ from $X$ with $c(\alpha,\beta)=i$.
Let $Y:=T\cap\{ t_\alpha{}^\smallfrown\langle i\rangle\mid \alpha\in X\}$. Since $T$ is prolific, $Y$ is a subset of $T$ of size $\kappa$, and hence $Y$ is not an antichain with respect to $\subset$. That is, there exist $\alpha<\beta$ from $X$ such that $$(t_\alpha{}^\smallfrown\langle i\rangle)\subset(t_\beta{}^\smallfrown\langle i\rangle).$$In particular, $(t_\alpha{}^\smallfrown\langle i\rangle)\subset(t_\beta{})$. So $t_\alpha\subset t_\beta$ and $c(\alpha,\beta)=t_\beta(\alpha)=i$, as sought. $\square$
Claim 2. $c$ does not admit a rainbow triangle.
That is, for every $X\subseteq\kappa$ of size $3$, the restriction $c\restriction[X]^2$ is not injective.
Proof. Let $X\subseteq\kappa$ of size $3$ be arbitrary.
If $\Delta\restriction[X]^2$ is a constant function, then clearly, $|c“ [X]^2|=2$.
Otherwise, we may find $\alpha,\beta,\gamma$ such that $X=\{\alpha,\beta,\gamma\}$ and $\Delta(\alpha,\gamma)=\Delta(\beta,\gamma)<\Delta(\alpha,\beta)$, and hence $c(\alpha,\gamma)=c(\beta,\gamma)$. $\square$
I find the above to be a considerably simpler consistency proof than the one from CH.
Next, to show how to obtain a prolific Souslin tree from a plain one, we recall some definitions and set up our notation.
A tree is a poset $(S,<_S)$ for which the downward cone $x_\downarrow:=\{y\in S\mid y<_S x\}$ is well-ordered by $<_S$, for all $x \in S$. Write $\text{ht}(x):=\text{otp}(x_\downarrow,<_S)$. For all $\beta$, denote by $S_\beta$ the $\beta^{th}$-level of the tree, that is, $S_\beta:=\{ x\in S\mid \text{ht}(x)=\beta\}$. Note that every level is an antichain. The tree $(S,<_S)$ is said to Hausdorff iff for all limit $\beta$ and $x,y\in S_\beta$, if $x_\downarrow=y_\downarrow$, then $x=y$.
A $\kappa$-Souslin tree is a tree of size $\kappa$ having no chains or antichains of size $\kappa$. A moment reflection makes it clear that if $(S,<_S)$ is a $\kappa$-Souslin tree, then $(\{ x_\downarrow\mid x\in S\},\subset)$ is an Hausdorff $\kappa$-Souslin tree.
Observation. Suppose that $\kappa$ is a regular uncountable cardinal.
If there exists a $\kappa$-Souslin tree, then there exists a prolific one.
Proof. Fix an Hausdorff $\kappa$-Souslin tree $(S,<_S)$. In particular, $|S_0|=1$, that is, $(S,<_S)$ admits a unique root. Put:
$$A:=\{ x\in S\mid \exists \beta<\kappa\forall y\in S_\beta(y\text{ is incomparable with }x)\}.$$Since $(S,<_S)$ has no antichains of size $\kappa$, we may pick a large enough $\varepsilon<\kappa$ such that $A\subseteq S\restriction\varepsilon$. Let $$B:=\{ x\in S\mid \left(x^\uparrow,<_S\right)\text{ is linearly ordered}\}.$$ Since $(S,<_S)$ has no cofinal branches, we know that $B\subseteq A$. Consequently,
$$D:=\{ \beta<\kappa\mid (\forall x\in S\restriction[\varepsilon,\beta))(\exists y_0,y_1\in S_\beta)[y_0,y_1\text{ are incompatible extensions of $x$}]\}\setminus\varepsilon$$ is a club in $\kappa$. Denote $S\restriction D:=\{ x\in S\mid \text{ht}(x)\in D\}$.
Subclaim. Suppose $y\in S\restriction D$, and $\mu<\kappa$ is some infinite cardinal. Then there exists some $\beta<\kappa$ such that $|S_\gamma\cap y^\uparrow|\ge\mu$ for all $\gamma\in D\setminus\beta$.
Proof. Write $\alpha:=\text{ht}(y)$. Since $\text{otp}(D\setminus\alpha)=\kappa>\mu$, let $\beta$ be the unique element of $D$ to satisfy $\text{otp}((D\setminus\alpha)\cap\beta)=\mu$. Let $f:\mu\leftrightarrow (D\setminus\alpha)\cap\beta$ be the order-preserving bijection.
By $\alpha,\beta\in D$, let us pick $z\in S_\beta$ with $y<_S z$. For all $i<\mu$, let $y_i$ be the unique element of $S_{f(i)}$ to satisfy $y_i<_S z$. Since $(z_\downarrow,<_S)$ is linearly ordered, we have $y=y_0$ and $y_i<_S y_j$ whenever $i<j<\mu$.
Let $i<\mu$ be arbitrary. By $\text{ht}(y_i),\text{ht}(y_{i+1})\in D$, let us pick $x_i\in S_{\text{ht}(y_{i+1})}$ that extends $y_i$ and is distinct from $y_{i+1}$.
Then $\{ x_i\mid i<\mu\}\subseteq S\restriction (D\cap\beta)$ is an antichain consisting of elements above $y$.
Finally, let $\gamma\in D\setminus\beta$ be arbitrary. For all $i<\mu$, by $\text{ht}(y_i),\gamma\in D$, let us pick some $z_i\in S_\gamma$ such that $y_i<_S z_i$. Then $|S_\gamma\cap y^\uparrow|\ge|\{z_i\mid i<\mu\}|=|\{y_i\mid i<\mu\}|=\mu$. $\blacksquare$
By the subclaim, we may define a function $g:D\rightarrow D$, stipulating:
$$g(\alpha):=\min\{\beta\in D\mid \forall y\in S_\alpha\forall\gamma\in D\setminus\beta~|S_\gamma\cap y^\uparrow|\ge|\alpha|\}.$$
Let $E:=\{\alpha<\kappa\mid g[\alpha]\subseteq\alpha\}$. Then $E\setminus\{0\}$ is a club subset of $D$. Fix the order-preserving bijection $\pi:\kappa\leftrightarrow E$.
Now, we define injections $\langle h_\alpha:S_{\pi(\alpha)}\rightarrow{}^\alpha\kappa\mid \alpha<\kappa\rangle$ by recursion:
- Let $h_0:=\{(r,\emptyset)\}$, where $r$ denotes the unique root of $(S,<_S)$.
- Suppose $\beta<\kappa$ and $\langle h_\alpha\mid \alpha\le\beta\rangle$ has already been defined. For all $x\in S_{\pi(\beta)}$, denote $\mathcal I(x):=\{ y \in S_{\pi(\beta)+1}\mid x<_S y\}$. By $\pi(\beta),\pi(\beta+1)\in E$, we have $|\mathcal I(x)|\ge|\pi(\beta)|\ge|\beta|$. So it is easy to find an injection $h_{\beta+1}:S_{\pi(\beta+1)}\rightarrow{}^{\beta+1}\kappa$ that satisfies for all $x\in S_{\pi(\beta)}$:$$h_{\beta+1}“\mathcal I(x)\supseteq\{ h_\beta(x){}^\smallfrown\langle i\rangle \mid i<\beta\}.$$
- Suppose that $\beta$ is a nonzero limit ordinal, and $\langle h_\alpha\mid\alpha<\beta\rangle$ has already been defined. Define $h_\beta:S_{\pi(\beta)}\rightarrow{}^\beta\kappa$ by letting for all $x\in S_{\pi(\beta)}$:$$h_\beta(x):=\bigcup\{ h_\alpha(y)\mid \alpha<\beta, y\in S_{\pi(\alpha)}\cap x_\downarrow\}.$$Since $(S,<_S)$ is Hausdorff, $h_\beta$ is injective.
This completes the construction. Let $h:=\bigcup_{\alpha<\kappa}h_\alpha$, and $T:=\text{Image}(h)$. Then $h$ is an order-preserving bijection from $(S\restriction E,<_S)$ to $(T,\subset)$. In particular, $|T|=\kappa$, and $(T,\subset)$ has no antichains of size $\kappa$. Of course, the above construction ensures that $T$ is prolific. $\square$
Back to the beginning of the post, let us point out that if we did not care about rainbow triangles, we could have let $c(\alpha,\beta)=t_\beta(\alpha)$ uniformly for all $\alpha<\beta<\kappa$. The latter is a stronger coloring, and is of a particular interest when the tree $T$ is either coherent or free.
This reminds me of an open problem I heard from Zapletal: Suppose that there exists a $\kappa$-Souslin tree. Must there also be a free one?
