König's Infinity Lemma and Beth's Tree Theorem. Issue 1 (2nd January 2017)

• Record Type: Journal Article
• Authors: Weaver, George
• Is Part Of: History and philosophy of logic. Volume 38:Issue 1(2017)
• Page Start: 48
• Page End: 56
• Publication Date: 2017-01-02
• Subjects: Logic -- Periodicals; 160.905
• DOI: 10.1080/01445340.2015.1065460
• Languages: English
• ISSNs: 0144-5340

Abstract

Abstract : König, D. [1926. 'Sur les correspondances multivoques des ensembles', Fundamenta Mathematica, 8, 114–34] includes a result subsequently called König's Infinity Lemma. Konig, D. [1927. 'Über eine Schlussweise aus dem Endlichen ins Unendliche', Acta Litterarum ac Scientiarum, Szeged, 3, 121–30] includes a graph theoretic formulation: an infinite, locally finite and connected (undirected) graph includes an infinite path. Contemporary applications of the infinity lemma in logic frequently refer to a consequence of the infinity lemma: an infinite, locally finite (undirected) tree with a root has a infinite branch. This tree lemma can be traced to [Beth, E. W. 1955. 'Semantic entailment and formal derivability', Mededelingen der Kon. Ned. Akad. v. Wet., new series 18, 13, 309–42]. It is argued that Beth independently discovered the tree lemma in the early 1950s and that it was later recognized among logicians that Beth's result was a consequence of the infinity lemma. The equivalence of these lemmas is an easy consequence of a well known result in graph theory: every connected, locally finite graph has among its partial subgraphs a spanning tree.