TOPICS
Search

König's Lemma


A tree with a finite number of branches at each fork and with a finite number of leaves at the end of each branch is called a finitely branching tree.

König's lemma states that a finitely branching tree is infinite iff it has an infinite path.

This lemma is used in proofs of completeness in logic.


See also

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

This entry contributed by Alex Sakharov (author's link)

Explore with Wolfram|Alpha

References

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

Referenced on Wolfram|Alpha

König's Lemma

Cite this as:

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

Subject classifications