The Infinity Lemma: Foundations, Proofs, and Applications Across Mathematics and Logic
Abstract The Infinity Lemma , also known as Kőnig’s Lemma , is a fundamental result in combinatorics and logic that asserts that every infinite, finitely branching tree contains an infinite path. This paper provides a comprehensive exploration of the lemma’s historical origins, formal statements, and multiple proof strategies, including constructive and non-constructive approaches. We situate the lemma within the framework of reverse mathematics, highlighting its equivalence to subsystems of second-order arithmetic and its role in compactness arguments. Applications are examined across graph theory, proof theory, computer science, and set theory, demonstrating the lemma’s versatility in ensuring infinite structures within finite constraints. Comparative analysis illustrates its philosophical significance in debates on infinity, constructivism, and determinism. Generalizations such as Weak Kőnig’s Lemma and topological variants are discussed, alongside future directions in constructive ...
