Tree, no uncountable antichains

238 Views Asked by At

Show that if a $\omega_1$ tree (that is, each vertex has height less than $\omega_1$ and each level $\alpha < \omega_1$ is countable and non-empty) has no uncountable anti chains, and in addition each vertex has at least two immediate successors, then the tree has no uncountable chain.

2

There are 2 best solutions below

8
On BEST ANSWER

HINT: If there’s an uncountable chain, there’s a branch through $T$. Look at the $x$’s in the picture below:

         o  
         |\  
         o x  
         |\  
         o x  
         |\  
         o x  
         |\  
         o x  
          .  
          .  
          .

(Note that you don’t need the assumption that the levels are countable.)

0
On

Hint: Prove by contrapositive. Suppose there was an uncountable chain. Use the fact that each point in the chain has at least two successors and construct an antichain.

Remember that if $x<y$ in the chain, and $x_1$ and $y_1$ are successors of $x,y$ which are not in the chain then $x_1\nless y_1$, otherwise the order is not a tree.