Kőnig's Lemma

Kőnig's lemma states that an infinite rooted tree in which every vertex has only finitely many children contains an infinite path. Such a rooted tree is called finitely branching.

This lemma is used in proofs of completeness in logic.

See also

Branch, Fork, Kruskal's Tree Theorem, Tree, Tree Leaf

Portions of this entry contributed by Alex Sakharov (author's link)

Explore with Wolfram|Alpha

More things to try:

References

Kleene, S. C. Mathematical Logic. New York: Dover, 2002.

Referenced on Wolfram|Alpha

Cite this as:

Weisstein, Eric W., with contributions by Alex Sakharov. "Kőnig's Lemma." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/KoenigsLemma.html

Subject classifications