5
$\begingroup$

An $\omega_1$-tree is a tree of height $\omega_1$.

An $\omega_1$-tree $T$ is normal if:

  1. $T$ has a unique least point (the root);
  2. every level of $T$ is at most countable;
  3. if $x \in T$ then there are infinitely many nodes at the successor level;
  4. if $x \in T$ then there is $y>x$ at each higher level less than $\omega_1$;
  5. the order $<$ is extensional within each level $U_\gamma$ such that $\gamma < \omega_1$ is a limit ordinal, that is: for all $x,y \in U_\gamma$, if $\{z \in T \mid z<x\} = \{z \in T \mid z<y\}$ then $x=y$.

A Suslin tree is an $\omega_1$-tree whose antichains are at most countable and which has no $\omega_1$-branch.

Fact. If there exists a Suslin tree, then there exists a normal Suslin tree.

Question: I can't understand how this can possibly be true. How can an $\omega_1$-tree satisfy condition (4) and still have no $\omega_1$-branch? Doesn't condition (4) trivially allow us to build an $\omega_1$-branch by recursion? Where does this very easy proof fail?

Attempt of proof. Define $f \colon \omega_1 \to T$ strictly increasing by recursion as follows: $f(0)$ is the root, $f(\alpha+1)$ is one arbitrarily chosen immediate successor of $f(\alpha)$. For the limit case (suppose $\gamma$ is limit) I claim that there is a node $x$ at level $\gamma$ such that

$$f(\alpha) < x \text{ for all } \alpha < \gamma.$$

Assume towards a contradiction that $\beta < \gamma$ is such that there exists no $x$ at level $\gamma$ such that $f(\alpha) < x$ for all $\alpha \leq \beta$. But by condition (4) we have that there exists $y>f(\beta)$ at level $\gamma$. But then $y$ is greater than any $f(\alpha)$ for $\alpha \leq \beta$, which is a contradiction.

Hence define $f(\alpha) = x$. Then $\langle f(\alpha) \mid \alpha < \omega_1 \rangle$ is an $\omega_1$-branch in $T$.

Definitions are taken from chapter 9 of Set theory by T. Jech.

$\endgroup$
  • $\begingroup$ Have you seen explicit examples of such trees? (For instance, in $L$.) Examining the constructions is probably the best way to see where your intuition is failing. $\endgroup$ – Andrés E. Caicedo May 11 '16 at 14:50
  • $\begingroup$ Yes, I did (precisely in $L$), but the construction is quite involved to me, thus I can't grasp the intuitive idea behind them yet. And this question was meant as a first step to understand how it works, since the problem here is that the contradiction seems really trivial to me (though I must obviously be wrong). $\endgroup$ – user338783 May 11 '16 at 14:59
  • 3
    $\begingroup$ You already have three answers, but let me address the specific "Attempt of proof" in the question. The part "Assume toward contradiction ... which is a contradiction" correctly proves that, for every $\beta<\gamma$, there is an $x$ at level $\gamma$ such that $f(\alpha)<x$ for all $\alpha<\beta$. But then you seem to go from $\forall\beta\exists x$ to $\exists x\forall \beta$, pretending that there is a single $x$ that works uniformly for all $\beta<\gamma$ and can therefore serve as $f(\gamma)$. $\endgroup$ – Andreas Blass May 11 '16 at 16:37
  • $\begingroup$ @AndreasBlass ...which is exactly the mistake I thought I had made (see my comment under elizabeth's answer), and I was also able to realize it, but yesterday my laptop ran out of battery before I could edit my question :) thank you very much for your reply anyway! $\endgroup$ – user338783 May 12 '16 at 13:21
7
$\begingroup$

Straightforward use of condition (4) would allow you to build an $\omega$-chain in $T$: $t_0 < t_1 < \cdots < t_n < \cdots$. The problem, then, is extending this to an $(\omega+1)$-chain.

While we can take $\alpha \geq \sup \{ \operatorname{ht}(t_n) : n \in \omega \}$ and find an extension of each $t_n$ on the $\alpha$th level of $T$, there is no way to guarantee that a single node on the $\alpha$th level extends each $t_n$.

Consider the tree $$T = \{ t \in \omega^{<\omega_1} : t\text{ has finitely many }0\text{s} \}.$$ This is fairly easily seen to be a normal $\omega_1$-tree, using the end-extension order. (This tree also obviously has $\omega_1$-chains, but I think it will be instructive nonetheless.) If $t_n = \overbrace{0\ldots 0}^{n\text{ zeroes}}$ for each $n$, then clearly we have constructed an $\omega$-chain in $T$. Also, each $t_n$ has an extension on the $\omega$th level of $T$. However no node on the $\omega$th (or any higher) level of $T$ extends each $t_n$, since such a node would have to contain infinitely many zeroes.

$\endgroup$
  • $\begingroup$ Great answer. I feel this is finally helping me fixing my intuition. Now I'm trying to use this example to understand where is the mistake in the proof of my (updated) answer. My guess is that I'm inadvertedly inverting some quantifiers somewhere. $\endgroup$ – user338783 May 11 '16 at 15:45
2
$\begingroup$

Every such attempt to construct a branch necessarily dies out. The best approach is probably to look at some actual constructions. This PDF on Aronszajn trees gives a couple of constructions in very full detail. The construction in this PDF should also be helpful.

$\endgroup$
1
$\begingroup$

Every node has a continuation. But when you get to a limit level not every branch which "tickles" the limit level gets realized.

The whole idea in the usual constructions of normal Suslin trees is that we use some combinatorial principle to guess in advance which branches can be realized along the way without threading a cofinal branch.

$\endgroup$
  • $\begingroup$ I remember feeling the same way when I first learned about trees. It's a confusing time in every young set theorists' life. That, the whole generic filters thing, and the consistency strength of inaccessible cardinals. The three things that had me stumped for long after I actually used them in arguments. $\endgroup$ – Asaf Karagila May 11 '16 at 16:06
  • $\begingroup$ Hi Asaf! Thanks for your answer and especially for your comment. I was really relieved to read that. I also decided to ask this question using an anonymous account instead of mine because I was ashamed to ask such a silly question. Now I kind of regret it, but whatever... $\endgroup$ – user338783 May 12 '16 at 13:28
  • $\begingroup$ Well, you can merge accounts if you really want to. So there's no point in regretting anything. math.stackexchange.com/help/merging-accounts $\endgroup$ – Asaf Karagila May 12 '16 at 13:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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