Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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}$.

share|cite|improve this question

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


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$.

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.