How statement and proof provenance work
The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.
- Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
- AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
- AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.
These labels describe origin, not correctness: citations and verification chips remain separate evidence.
König’s lemma for finite levels
Statement
In ZFC, every tree of height with finite levels has an infinite branch.
Facts & Assumptions
Given: Such a tree . AC is used once to fix a well-order of its node set; recursion thereafter takes least eligible nodes.
Every lower height has a unique predecessor; nodes with a common upper bound are comparable. Tree predecessors and compatibility
Assuming AC, every set can be well-ordered. The well-ordering theorem
A specified initial value and a self-map of a set determine a sequence by natural recursion. The recursion theorem
Assume the Axiom of Choice. The Axiom of Choice
Proof
Call good if the heights of nodes above or equal to are unbounded in . The height assumption and F1 imply that every level is nonempty. Some root is good: otherwise, each of the finitely many roots has a finite height bound on its extensions; their maximum bounds all nodes because each node has a root predecessor (or is a root). That contradicts height .
If a good node has height , its immediate successors are precisely its extensions at height , by F1. This is a finite set. Each higher extension of passes through one of these successors. If none were good, the maximum of their finitely many bounds, together with , would bound all extensions of . Thus a good immediate successor exists.
Fix a well-order of using AC. Let be the least good root and send each good node to its least good immediate successor. On the set of good nodes this is a self-map, so recursion gives at height with for every .
The set is an infinite chain. If could be added to it, put . Comparability with and the level-antichain conclusion of F1 force . Thus is already maximal, hence is an infinite branch.
Depends on
Used by
- Countable levels do not suffice for König’s lemma Counterexample
- The binary tree and a cofinal branch Example
Dependency tree · two levels
18 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.
Sources
- Monk, Set theory following Jech (2024), Theorem 9.32, printed p86 (standard reference, not scraped)