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

Let $T$ be a Suslin tree - that is to say a tree of height $\omega_1$ such that every branch in $T$ (i.e. every maximal linearly ordered subset of $T$) is countable, and every antichain in $T$ is countable). It follows that every level of the tree is countable.

For each $x \in T$ define $T_x = \{ y \in T \mid y \ge x \}$. We define a new tree $T_1 = \{ x \in T \mid T_x \text{ is uncountable}\}$. For every chain $C = \{z \mid z < y \}$ of limit length, we add another element $a_C$ to the tree $T_1$ and change the order so that $z < a_C$ for all $z \in C$ and $a_C < x$ for all $x$ with the property that $x > z$ for all $z \in C$. Add these extra elements to obtain a tree $T_2$.

$\bf{QUESTION\ 1}$: I want to show that if $\beta < \omega_1$ is a limit ordinal, and $x,y$ are both on level $\beta$ of $T_2$, then $\{ z \mid z < x \} = \{ z \mid \ z < y\} \implies x = y$. To me this would follow immediately if level $\beta$ consisted of elements of the form $a_C$. But I'm not sure how to show this, if this is the case. If I consider the order type/height of an element $a_C$ in this new tree at a limit level, does the order type rise if I have more elements below in $T_2$ than I have below it in $T_1$?

$\bf{QUESTION\ 2}$: Define a new tree $T_3$ to be the branching points of $T_2$, i.e. the elements in $T_2$ where there at least two elements in the level above it. I want to verify the above property is true in this case too. I thought that removing branching points would possibly change the levels of some elements in the tree, so I'm having trouble getting my head round this.

Could anyone help me with the above two questions? Thank you very much. My question is based on Jech 9.13.

share|cite|improve this question
You’re adding the new elements to $T_1$, not to $T$, right? (You didn’t actually say.) Second, do you really want to add a new element for every chain $C$ in $T_1$ of the form $\{z:z<y\}$? – Brian M. Scott Mar 27 '12 at 18:22
Apologies - we only consider chains of limit length, and we add to $T_1$. Fixed the question. – Paul Slevin Mar 27 '12 at 18:25
Okay; I’ll need to give it a little thought, but that makes much better sense. – Brian M. Scott Mar 27 '12 at 18:28
Sorry for the spam, but it's strange that the characters in the emboldened text have different heights (the "E" and "T" are shorter than the others, at least on my system)... – David Mitra Mar 27 '12 at 18:30
@David: You should take a screenshot and post that issue on the meta site, – Asaf Karagila Mar 27 '12 at 19:19
up vote 2 down vote accepted

I think that the following works.

Question 1. It would appear sufficient to show that every $x \in T_1$ has successor height in $T_2$. This seems to follow from two observations:

  • If $x$ was of successor height in $T_1$, it is still of successor height in $T_2$, as its immediate predecessor in $T_1$ is an immediate predecessor in $T_2$.
  • If $x$ was of limit height, then the family $C = \{ z \in T_1 : z < x \}$ is a chain in $T_1$ of limit height, and $x$ can be shown to be an immediate successor of $a_C$ in $T_2$.

Question 2. Note that if $x , y \in T_3$ are of limit height and have the same set of predecessors in $T_3$, then they also have the same set of predecessors in $T_2$. If not, then let $\beta$ be minimal such that the predecessor $x^\prime$ of $x$ on the $\beta$th level of $T_2$ is different from the predecessor $y^\prime$ of $y$ on the $\beta$th level of $T_2$.

  • If $\beta$ is a successor ordinal, then it must be that the immediate predecessors of $x^\prime$ and $y^\prime$ coincide (by minimality of $\beta$), so let's call this node $a$. Note that $a \in T_3$. It can be shown that no node $z \in T_2$ satisfying either $a < z < x$ or $a < z < y$ can be in $T_3$ (since then such a node would witness the difference of the predecessors of $x$ and $y$ in $T_3$). But then $x$ and $y$ are immediate successors of $a$ in $T_3$, contradicting the assumption that they are of limit height in $T_3$!

  • if $\beta$ is a limit ordinal, then by the above $x^\prime = a_{C}$ for some chain $C$ in $T_1$, and $y^\prime = a_{D}$ for some chain $D$ in $T_1$. But as $x^\prime \neq y^\prime$ it follows that $C \neq D$, contradicting the minimality of $\beta$ in $T_2$!

Thus $x$ and $y$ have the same set of predecessors in $T_2$. If $x$ and $y$ are of successor height in $T_2$, then if different their immediate predecessor is branching, and thus in $T_3$, contradicting that $x,y$ are of limit height in $T_3$. Thus $x$ and $y$ are of limit height in $T_2$, are are thus equal.

share|cite|improve this answer
Thank you very much for the above - is it easy to see that, if we define $T_4$ to be the tree given by taking the limit levels of $T_3$, that the same property holds once more? I'm having some trouble showing this. If I take 2 elements $x,y$ on a limit level of $T_4$ with the same predecessors, it doesnt seem obvious to me that they have the same predecessors on $T_3$. – Paul Slevin Mar 28 '12 at 16:06
@Paul: Note that if $x$ on a limit level of $T_4$, then the family of predecessors of $x$ in $T_4$ is actually cofinal in the family of all predecessors of $x$ in $T_3$ (cofinal in the $T_3$ sense). So if $x$ and $y$ have different sets of predecessors in $T_3$, they will also have difference sets of predecessors in $T_4$. – arjafi Mar 28 '12 at 16:50
When trying to prove it myself I basically got to this point, but I was unable to show that one was cofinal in the other - is there an easy way to see this? I'm just confused why we can't pick some limit level, and the next limit level above that is the one where $x$ originally came from. Thanks again. – Paul Slevin Mar 28 '12 at 17:07
@Paul: I am pretty sure that is $x$ is of height $\alpha$ in $T_4$, then $x$ was of height $\omega \alpha$ in $T_3$. So if $x$ is of limit height in $T_4$, then $\alpha$ is a limit ordinal, and given any cofinal sequence $\{ \alpha_n \}$ ($n \in \omega$) in $\alpha$ it follows that $\{ \omega \alpha_n \}$ ($n \in \omega$) is a cofinal sequence of limit ordinals in $\omega \alpha$. – arjafi Mar 28 '12 at 17:27

Instead of giving a formal argument, I’m going to try to give a clearer picture of what’s really going on and see if that helps you complete the argument.

If $T$ is any tree, and $x\in T$, let $\operatorname{pred}(x,T)=\{z\in T:z<x\}$, let $\operatorname{ht}(x,T)$ be the height of $x$ in $T$, and for any ordinal $\alpha$ let $\operatorname{Lev}_\alpha(T)=\{x\in T:\operatorname{ht}(x,T)=\alpha\}$.

The whole point of the construction is to replace the Suslin tree $T$ with nicer Suslin tree. The step from $T$ to $T_1$ prunes the ‘dead’ branches of $T$, leaving only nodes that have successors arbitrarily high in the tree.

A ‘nice’ tree branches only at successor levels, so that nodes at limit levels are completely determined by their sets of predecessors. Thus, we’d like $T_1$ to have the property that if $\beta$ is a limit ordinal, $x,y\in\operatorname{Lev}_\beta(T_1)$, and $x\ne y$, then $\operatorname{pred}(x,T_1)\ne\operatorname{pred}(y,T_1)$. Unfortunately, it’s quite possible that $T_1$ does branch at limit levels; the step from $T_1$ to $T_2$ is designed to get rid of this unwanted branching.

Suppose that $\beta$ is a limit ordinal, $x,y\in\operatorname{Lev}_\beta(T_1)$, $x\ne y$, and $\operatorname{pred}(x,T_1)=\operatorname{pred}(y,T_1)$. Let $C=\operatorname{pred}(x,T_1)$; then $C$ is a chain of limit length in $T_1$, so in $T_2$ we have a vertex $a_C$. Where does it fit into $T_1$? Clearly it lies above every $z\in C$, but it lies below both $x$ and $y$. If it were the only new vertex, it would clearly be in $\operatorname{Lev}_\beta(T_2)$, immediately below $x$ and $y$, which would be pushed up from $\operatorname{Lev}_\beta(T_1)$ to $\operatorname{Lev}_{\beta+1}(T_2)$. All successors of $x$ and $y$ at heights $\beta+n$ for $n\in\omega$ would also be pushed up one level, but there would be no change at heights $\ge\beta+\omega$.

Of course we’ve no reason to suppose that this $a_C$ is the only new vertex. However, this turns out not to be a problem if we look at the construction in steps rather than all at once. Imagine climbing $T_1$ and examining each limit level in turn. Say that you’ve reached $\operatorname{Lev}_\beta(T_1)$ for some limit ordinal $\beta<\omega_1$. You find all of the unwanted splits at Level $\beta$ (if any) and treat them as we did the single split in the last paragraph. This does not change the structure of the tree below Level $\beta$ in any way, so it has no effect on changes that we’ve already made lower in the tree. It does ensure that distinct vertices in $\operatorname{Lev}_\beta(T_2)$ have distinct sets of predecessors in $T_2$. And it has no effect on the structure of the tree at heights $\ge\beta+\omega$. In particular, it has no effect on the higher limit levels. Thus, we can repair the unwanted splits one limit level at a time, knowing that repairs at one level can neither affect earlier repairs at lower levels nor affect the unwanted splits at higher levels.

Now the construction that you specified in the problem is just a little different from the one that I just described. I added new elements at limit levels only where that was necessary in order to repair an unwanted split. Your construction is actually going to replace the whole limit level with new elements, whether they’re actually needed or not. This is less intuitive, but it makes the process a little easier to handle, because it makes it more consistent. Your construction amounts to doing the following at a limit level $\beta$.

For $x,y\in\operatorname{Lev}_\beta(T_1)$ write $x\sim y$ iff $\operatorname{pred}(x,T_1)=\operatorname{pred}(y,T_1)$; clearly $\sim$ is an equivalence relation on $\operatorname{Lev}_\beta(T_1)$. For each $\sim$-class $[x]$ let $C([x])=\operatorname{pred}(x,T_1)$, a chain of limit length in $T_1$. Let $\operatorname{Lev}_\beta(T_2)=\{a_{C([x])}:x\in\operatorname{Lev}_\beta(T_1)\}$. Then fix up the order as you described in your construction.

When a vertex $x$ is the only member of its $\sim$-class, it wasn’t part of an unwanted split, so the new vertex $a_{C([x])}$ isn’t actually necessary. The nice thing, though, is that this uniform construction simply pushes the next $\omega$ levels of $T_1$ up a notch: for each $n\in\omega$ we have $\operatorname{Lev}_{\beta+n+1}(T_2)=\operatorname{Lev}_{\beta+n}(T_1)$. All we’re doing is replacing the limit levels in a way that kills off any splits at levels that may have been present in $T_1$.

The final step, from $T_2$ to $T_3$, is intended to get rid of ‘fake’ nodes, i.e., nodes at which no branching occurs. (After all, if there’s no branching there, why have a vertex there?) This can indeed affect the heights of vertices and hence the composition of the levels; a vertex on Level $\omega$ of $T_2$ could end up on Level $1$ of $T_3$, for instance. Note, though, that all level changes are downward: $\operatorname{ht}(x,T_3)\le\operatorname{ht}(x,T_2)$ for all $x\in T_3$.

(I need to run off and take care of a few chores. I’ll post this much for now, since I think that it’s a useful start for you, and finish it off in a bit.)

share|cite|improve this answer
Thanks for this deeply insightful answer. – Paul Slevin Mar 27 '12 at 23:48

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.