König’s lemma
Theorem (König’s lemma).
Let $T$ be a rooted directed tree. If each vertex has finite degree but there are arbitrarily long rooted paths in $T$, then $T$ contains an infinite^{} path.
Proof.
For each $n\ge 1$, let ${P}_{n}$ be a rooted path in $T$ of length $n$, and let ${c}_{n}$ be the child of the root appearing in ${P}_{n}$. By assumption^{}, the set $\{{c}_{n}\mid n\ge 1\}$ is finite. Since the set $\{{P}_{n}\mid n\ge 1\}$ is infinite, the pigeonhole principle^{} implies that there is a child $c$ of the root such that $c={c}_{n}$ for infinitely many $n$.
Now let us look at the subtree ${T}_{c}$ of $T$ rooted at $c$. Each vertex has finite degree, and since there are paths ${P}_{n}$ of arbitrarily long length in $T$ passing through $c$, there are arbitrarily long paths in ${T}_{c}$ rooted at $c$. Hence if $T$ satisfies the hypothesis of the lemma, the root has a child $c$ such that ${T}_{c}$ also satisfies the hypothesis of the lemma. Hence we may inductively build up a path in $T$ of infinite length, at each stage selecting a child so that the subtree rooted at that vertex still has arbitrarily long paths. ∎
References
- 1 Kleene, Stephen., Mathematical Logic, New York: Wiley, 1967.
Title | König’s lemma |
---|---|
Canonical name | KonigsLemma |
Date of creation | 2013-03-22 15:38:26 |
Last modified on | 2013-03-22 15:38:26 |
Owner | mps (409) |
Last modified by | mps (409) |
Numerical id | 6 |
Author | mps (409) |
Entry type | Theorem |
Classification | msc 05C05 |
Synonym | Koenig’s lemma |