I am trying, carefully, to prove König's Lemma that an infinite binary tree $T$ has an infinite simple path.
Let $R$ denote the root vertex of $T$. If I start at $v_1=R$, there must be a vertex adjacent to $R$, call it $v_2$, such that infinitely many vertices of $T$ are reachable by going up the tree from $v_2$.
If not, the tree would be a finite tree (finite union of finite sets of vertices).
I can repeat this process. Whenever I am at vertex $v_n$, I can find a vertex $v_{n+1}$ such that there are infinitely many vertices still available above $v_{n+1}$ in the tree.
By induction, for any $n$ I can have that there exists a path of length $n$, in $T$.
How do I get from this an infinite path? Surely mathematical induction gives me the existence of an arbitrarily long finite path, which is not the same thing?
Edit: Ah, I think I've got it. I can order the vertices in each level of the tree from the left to the right, and at every step define $p(n)=$ the leftmost (resp. rightmost) vertex that has infinitely many vertices above it. Induction gives me the path $p(1)p(2)\ldots p(n)$ for every natural $n$ and then the infinite path is the set-theoretic union over $\Bbb N$ of these arbitrarily long finite paths?
Best Answer
You can rearrange your argument a little bit. We recursively construct a set $\{ s_n \mid n \in \mathbb N \}$ of $0/1$ sequences such that $s_0 = ()$ is the root of your tree. Given $s_n$, we let $s_{n+1} = s_{n} \ ^\frown (0)$, if there are infinitely many points above $s_{n} \ ^\frown (0)$ and otherwise we let $s_{n+1} = s_{n} \ ^\frown (1)$. Note that in either case there are infinitely many points above $s_{n+1}$ - so this construction never breaks down.
Let $s$ be the unique infinite $0/1$ sequence such that the first $n-1$ entries of $s$ agree with $s_{n}$ - for every $n \in \mathbb N$. By construction $s$ is an infinite branch through our tree.