König's Lemma

König's lemma states that every finitely branching infinite tree has an infinite branch.

To prove this we show how such an infinite branch can be constructed. Starting at the root, t0, we construct a branch, t0, t1, ..., so that every ti in the sequence has infinitely many descendants. Since the tree is finitely branching, and the finite union of finite sets is finite, then at least one child of the ultimate node in the sequence has infinitely many children and so this sequence can always be extended.

References

Doets, Kees. From Logic to Logic Programming. MIT Press, 1994.