# $\kappa$-Suslin (Aronszajn, Kurepa) subtree of the complete binary tree, $2^{\lt \kappa}$

This is from chapter 2 of Kunen, Set theory: an introduction to independence proofs.

Given $\kappa$ a regular cardinal, and the existence of a $\kappa$-Suslin (Aronszajn, Kurepa) tree, show that there is one which is a subtree of the complete binary tree $2^{<\kappa}$.

-

For $\kappa$-Kurepa trees the result is an immediate consequence of the proof of Theorem II.5.18. Now suppose that $T$ is a $\kappa$-Aronszajn tree. We may assume that $T$ is well-pruned.

Added: For $\alpha<\kappa$ let $T_\alpha=\bigcup_{\xi<\alpha}\operatorname{Lev}_\xi(T)$ as a subtree of $T$, and let $\Lambda$ be the set of limit ordinals less than $\kappa$. By performing the following surgery, we may further assume that if $\eta\in\Lambda$, and $B$ is a branch through $T_\eta$, then there is at most one $t\in\operatorname{Lev}_\eta(T)$ that extends $B$.

For each $\eta\in\Lambda$ let $\mathscr{B}_\eta$ be the set of branches through $T_\eta$ that have at least one extension in $\operatorname{Lev}_\eta(T)$. Let

$$T\,'=T\cup\bigcup_{\eta\in\Lambda}\mathscr{B}_\eta\;,$$

and extend the tree relation $\le$ to $T\,'$ by setting $x\le y$ iff

\begin{align*} &x,y\in T\text{ and }x\le y\;,\\ &x,y\in T\,'\setminus T\text{ and }x\subseteq y\;,\\ &x\in T,y\in T\,'\setminus T,\text{ and }x\in y\;,\text{ or}\\ &x\in T\,'\setminus T,y\in T,\text{ and }\forall y\in x(x<y)\;. \end{align*}

In words, we first replace each limit level $\operatorname{Lev}_\eta(T)$ with a level containing exactly one point for every branch through $T_\eta$ that has at least one extension in $\operatorname{Lev}_\eta(T)$. Then we push each level $\operatorname{Lev}_{\eta+k}(T)$ for $k\in\omega$ up one level: as sets, $\operatorname{Lev}_{\eta+k}(T)=\operatorname{Lev}_{\eta+k+1}(T\,')$. Clearly $T\,'$ is still a $\kappa$-tree, and this operation does not introduce any $\kappa$-chains or $\kappa$-antichains.

I will inductively construct a subtree $S$ of $T$ labelled by elements of $^{<\kappa}2$.

Let $s_{\langle\rangle}$ be the root of $T$; $\operatorname{Lev}_0(S)=\{s_{\langle\rangle}\}$. Suppose that we've constructed $\operatorname{Lev}_\eta(S)$ for some $\eta<\kappa$ in such a way that $\operatorname{Lev}_\eta(S)\subseteq\operatorname{Lev}_\alpha(T)$ for some $\alpha<\kappa$. Clearly $|\operatorname{Lev}_\eta(S)|<\kappa$. By Lemma II.5.12, for each $s_\sigma\in\operatorname{Lev}_\eta(S)$ there is a $\beta_\sigma>\alpha$ such that $s_\sigma$ has at least two successors in $\operatorname{Lev}_{\beta_\sigma}(T)$. Let $\beta=\sup\{\beta_{\sigma}:s_\sigma\in\operatorname{Lev}_\eta(S)\}$; $\kappa$ is regular, so $\beta<\kappa$. Since $T$ is well-pruned, each $s_\sigma\in\operatorname{Lev}_\eta(S)$ has at least two successors in $\operatorname{Lev}_\beta(T)$. For each $s_\sigma\in\operatorname{Lev}_\eta(S)$ choose two successors in $\operatorname{Lev}_\beta(T)$, label them $s_{\sigma^{\frown}0}$ and $s_{\sigma^{\frown}1}$, and let $\operatorname{Lev}_{\eta+1}(S)=\{s_{\sigma^{\frown}i}:s_\sigma\in\operatorname{Lev}_\eta(S)\text{ and }i\in\{0,1\}\}\subseteq\operatorname{Lev}_\beta(T)$.

Now suppose that $\eta<\kappa$ is a limit ordinal and that we've constructed $\operatorname{Lev}_\xi(S)$ for $\xi<\eta$ in such a way that there is an increasing sequence $\langle\alpha_\xi:\xi<\eta\rangle$ in $\kappa$ such that $\operatorname{Lev}_\xi(S)\subseteq\operatorname{Lev}_{\alpha_\xi}(T)$ for each $\xi<\eta$. Let $$S_\eta=\bigcup_{\xi<\eta}\operatorname{Lev}_\xi(S)\;,\tag{1}$$ a subtree of $T$ of height $\eta$. Suppose that $B$ is a branch through $S_\eta$; the construction ensures that there is a $\sigma\in{^\eta 2}$ such that $B=\{s_{\sigma\upharpoonright\xi}:\xi<\eta\}$. Let $\alpha=\sup\{\alpha_\xi:\xi<\eta\}<\kappa$. There is at most one element of $\operatorname{Lev}_\alpha(T)$ that extends $B$; if there is one, label it $s_\sigma$. Let $\operatorname{Lev}_\eta(S)$ be the set of such $s_\sigma$, one for each branch through $S_\eta$ that has an extension in $\operatorname{Lev}_\alpha(T)$.

Clearly that this construction can be carried through to construct $\operatorname{Lev}_\eta(S)$ for all $\eta<\kappa$; the tree $S$ is then $S_\kappa$ as defined by $(1)$, and the desired subtree of $^{<\kappa}2$ is $S'=\{\sigma\in{^{<\kappa}2}:s_\sigma\in S\}$. It should be clear that $S$ and $S'$ are isomorphic, so it suffices to verify that $S$ is $\kappa$-Aronszajn. But this is clear: by construction any chain in $S$ is a chain in $T$.

It should also be clear that any antichain in $S$ is already an antichain in $T$, so if $T$ is $\kappa$-Suslin, so is $S$.

-
When you define Lev_eta(S) for eta a limit ordinal, and take alpha=sup{alpha_xi}, why is there at most one x in Lev_alpha(T) that extends B? –  el barto May 21 '12 at 3:06
@elbarto: Because that’s the way I normally define my trees, and I forgot that Ken doesn’t do so here. I’ve added an argument to justify it, by modifying the original tree if necessary. –  Brian M. Scott May 21 '12 at 4:07