König's Lemma in set theory, why is the finite branching needed?

361 Views Asked by At

The answers here are quite mathematical. I hope somebody can explain this particular point here.


Why is it for a tree with height $\omega$ that all its levels need to be finite in order to have an infinite branch ? This question is about the necessity of the finiteness of the levels. For example what is false about the picture below ? I don't see why existance or the absence of the (encircled) subset on the right, affects the existance of the infinite branch ?

enter image description here

Definitions

A tree $(T,<)$ is a partially ordered set with $\forall y \in T:\ T_{<x} := \{y\in T|y<x\}\ \text{is well-ordered}$.

The height of an element $x$ is the ordinal $ht(x,T):=\alpha_x \cong T_{<x}$, i.e. of the order-type of $T_{<y}$.

The $\alpha$th level of the tree is $T(\alpha) = \{x\in T|\ ht(x,T) \cong \alpha\}$

A branch is a subset of $T$ that is maximal chain

The height of the tree is $ht(T) = \sup\{ht(x,T)+1|\ x \in T\}$,


Added:

I doubt about this last definition, for if we have an $\omega$-long branch, the tree would be $(\omega+1)$-heigh. Though this definition is found also in Kunen, Set Theory, An Introduction to Independence Proofs (1992), §5 Trees, p. 68. Could anyone explain what is wrong with this ?

3

There are 3 best solutions below

0
On BEST ANSWER

Take a collection of finite trees, such that your collection contains trees of every possible finite height.

Graft them all onto a single new root node.

Then the combined tree has height $\omega$ (it certainly can't have any finite height) -- but it can't contain any infinite branch. Such a branch would have to contain one of the successors of the new root node. But that successor is the root of one of the original trees, so it cannot be in an infinite branch.

2
On

A tree with a single root and infinitely many children (which all are leaves) is an infinite tree without infinite branch.

7
On

It seems to me that you are misunderstanding König's lemma. It gives a sufficient (and not necessary) condition for a tree to have an infinitely long ray/path. Namely, if a tree is infinite (has infinitely many vertices) and finitely branching (locally finite/each node has finitely many children), then it has infinite ray/path from the root (note this is much stronger than asserting that the suprema of the heights is infinite). This doesn't contradict your example.