Prolific Souslin trees

In a paper from 1971, Erdos and Hajnal asked whether (assuming CH) every coloring witnessing ${\mathrm{\aleph }}_1\nrightarrow [{\mathrm{\aleph }}_1{]}_3^2$ 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 ${\mathrm{\aleph }}_1\nrightarrow [{\mathrm{\aleph }}_1{]}_{\omega }^2$ 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 {]}_{\kappa }^2$ 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\upharpoonright \beta$ and $t{}^{⌢}⟨\beta ⟩$ 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 \ne \beta$, denote $$\mathrm{\Delta }(\alpha ,\beta ):=\{\begin{array}{ll}min\{\alpha ,\beta \},& \text{if }{t}_{\alpha }\cup t_{\beta }\in T;\\ min\{\epsilon \mid t_{\alpha }(\epsilon )\ne t_{\beta }(\epsilon )\},& \text{otherwise}.\end{array}$$
Finally, define a coloring $c:[\kappa {]}^2\to \kappa$ by letting for all $\alpha \ne \beta$:$$c(\alpha ,\beta ):=\{\begin{array}{ll}{t}_{\beta }(\alpha ),& \text{if }{t}_{\alpha }\subset t_{\beta };\\ t_{\alpha }(\beta ),& \text{if }{t}_{\beta }\subset t_{\alpha };\\ min\{t_{\alpha }(\mathrm{\Delta }(\alpha ,\beta )),t_{\beta }(\mathrm{\Delta }(\alpha ,\beta ))\},& \text{otherwise}.\end{array}$$

Claim 1. $c$ witnesses $\kappa \nrightarrow [\kappa {]}_{\kappa }^2$.
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 }{}^{⌢}⟨i⟩\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 }{}^{⌢}⟨i⟩)\subset (t_{\beta }{}^{⌢}⟨i⟩).$$In particular, $(t_{\alpha }{}^{⌢}⟨i⟩)\subset (t_{\beta })$. So $t_{\alpha }\subset t_{\beta }$ and $c(\alpha ,\beta )=t_{\beta }(\alpha )=i$, as sought. $\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/15.0.3/svg/25fb.svg">}$

Claim 2. $c$ does not admit a rainbow triangle.
That is, for every $X\subseteq \kappa$ of size $3$, the restriction $c\upharpoonright [X{]}^2$ is not injective.
Proof. Let $X\subseteq \kappa$ of size $3$ be arbitrary.
If $\mathrm{\Delta }\upharpoonright [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 $\mathrm{\Delta }(\alpha ,\gamma )=\mathrm{\Delta }(\beta ,\gamma )<\mathrm{\Delta }(\alpha ,\beta )$, and hence $c(\alpha ,\gamma )=c(\beta ,\gamma )$. $\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/15.0.3/svg/25fb.svg">}$

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 \mathrm{\exists }\beta <\kappa \mathrm{\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 $\epsilon <\kappa$ such that $A\subseteq S\upharpoonright \epsilon$. Let $$B:=\{x\in S\mid (x^{\uparrow },{<}_S)\text{ is linearly ordered}\}.$$ Since $(S,{<}_S)$ has no cofinal branches, we know that $B\subseteq A$. Consequently,
$$D:=\{\beta <\kappa \mid (\mathrm{\forall }x\in S\upharpoonright [\epsilon ,\beta ))(\mathrm{\exists }{y}_0,y_1\in S_{\beta })[y_0,y_1\text{ are incompatible extensions of }x]\}\setminus \epsilon$$ is a club in $\kappa$. Denote $S\upharpoonright D:=\{x\in S\mid \text{ht}(x)\in D\}$.

Subclaim. Suppose  $y\in S\upharpoonright 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\upharpoonright (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$. $\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◼"\; src="https://s.w.org/images/core/emoji/15.0.3/svg/25fc.svg">}$

By the subclaim, we may define a function $g:D\to D$, stipulating:
$$g(\alpha ):=min\{\beta \in D\mid \mathrm{\forall }y\in S_{\alpha }\mathrm{\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 $⟨h_{\alpha }:S_{\pi (\alpha )}\to {}^{\alpha }\kappa \mid \alpha <\kappa ⟩$ by recursion:

• Let $h_0:=\{(r,\mathrm{\varnothing })\}$, where $r$ denotes the unique root of $(S,{<}_S)$.
• Suppose $\beta <\kappa$ and $⟨h_{\alpha }\mid \alpha \le \beta ⟩$ 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)}\to {}^{\beta +1}\kappa$ that satisfies for all $x\in S_{\pi (\beta )}$:$$h_{\beta +1}“\mathcal{I}(x)\supseteq \{h_{\beta }(x){}^{⌢}⟨i⟩\mid i<\beta \}.$$
• Suppose that $\beta$ is a nonzero limit ordinal, and $⟨h_{\alpha }\mid \alpha <\beta ⟩$ has already been defined. Define $h_{\beta }:S_{\pi (\beta )}\to {}^{\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\upharpoonright 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. $\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/15.0.3/svg/25fb.svg">}$

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?