Infinite chains in infinite trees

Question

I am stuck on proving this theorem:

$T$ is an infinite with finitely many elements of each finite height $\to \exists C \in T$, $C$ - infinite chain.

I tried constructing

$C$ = {$s\in T$: {$t \in T: s \lt T$} $\in U$}

where $U$ is a free ultrafilter on $T$ trying to show that if $s \in C$ then $\exists k \in C: k>s$

because if {$t \in T: s \lt T$} $\in U$ then {$t \in T: k \lt T$} $\in U$

but I could not prove that this chain is necessarily infinite. I think I should somehow utilize the finiteness of every tree level

Answer 1

This will work, and is very close to how the standard proof goes - we identify a collection $\mathcal{U}$ of "large" subsets of $T$, and then build a path through $T$ by picking at each stage some node $s$ such that $\{t: t\in T, s\prec t\}$ is "large."

However, you don't need to go to an ultrafilter to do this: while an ultrafilter lets you build a "canonical" path as you've done, the collection of all infinite subsets of $T$ is enough to build a path! That is, we can inductively define a path through $T$ as follows:

• Let $s_0$ be the root of $T$.

• Having defined $s_n$, let $s_{n+1}$ be some immediate successor of $s_n$ such that $\{t\in T: s_{n+1}\prec t\}$ is infinite.

Since $T$ is finitely branching, if $s$ has infinitely many nodes above it, then some successor of $s$ also has infinitely many nodes above it (since otherwise the set of all nodes above $s$ is a finite union (finitely many successors of $s$) of finite sets (finitely many nodes above each successor)); so this procedure in fact does build an infinite path.

Note that there are many possible choices for $s_{n+1}$, given $s_n$, so this doesn't build a single specific path. Indeed, what this really builds is a subtree of $T$: let $$T'=\{s\in T: \{t\in T: s\prec t\}\mbox{ is infinite}\}.$$ $T'$ is the set of extendible nodes of $T$, that is, the nodes of $T$ which lie on some infinite path through $T$. And $T'$ has no dead ends, so you can just "walk up" $T'$ however you like to get a path through $T$.

---

Your ultrafilter construction also works, though - the key point (as in the above argument) is:

If $\{t: s\prec t\}\in\mathcal{U}$, then $s$ has some immediate successor $s'$ such that $\{t: s'\prec t\}\in \mathcal{U}$ (that is, if $s\in C$ then $s$ has some immediate successor $s'$ which is also $\in C$).

To do this, just show that the union of finitely-many sets not in the ultrafilter is not in the ultrafilter . . .

---

It's also worth pointing out the usefulness of ultrafilters elsewhere in combinatorics. Although they're really overkill in this problem, using a nonprincipal ultrafilter can somewhat simplify the proof of Ramsey's theorem for pairs, and can greatly simplify the proof of Hindman's theorem (although there we need a special kind of ultrafilter, the existence of which takes more work than just a nonprincipal ultrafilter).

Answer 2

This is an instance of König's lemma:

let $v_0$ be (a/the) root of the tree (point with no predecessors). Having defined $v_n$ we define $v_{n+1} > v_n$ by picking a neighbour of $v_n$ that has inifitely many elements below it; such must exist, as otherwise (as $v_n$ has only finitely many points directly below as levels are finite) the tree would be a finite union of finite sets, which cannot be.

It's clear the $v_n$ form an infinite chain.