König's Infinity Lemma and Beth's Tree Theorem

History and Philosophy of Logic 38 (1):48-56 (2017)

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 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 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.
Keywords No keywords specified (fix it)
Categories (categorize this paper)
Reprint years 2017
ISBN(s)
DOI 10.1080/01445340.2015.1065460
Options
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

Our Archive


Upload a copy of this paper     Check publisher's policy     Papers currently archived: 43,694
External links

Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
Through your library

References found in this work BETA

Set Theory.K. Kuratowski, A. Mostowski & M. Maczynski - 1975 - Journal of Symbolic Logic 40 (4):629-630.
Introduction to Mathematical Logic.Elliott Mendelson - 1964 - Journal of Symbolic Logic 34 (1):110-111.
Mathematical Logic.Stephen Cole Kleene - 1967 - Journal of Symbolic Logic 35 (3):438-440.
Hilbert's programme.Georg Kreisel - 1958 - Dialectica 12 (3‐4):346-372.

View all 9 references / Add more references

Citations of this work BETA

Add more citations

Similar books and articles

Ramsey’s Theorem and König’s Lemma.T. E. Forster & J. K. Truss - 2007 - Archive for Mathematical Logic 46 (1):37-42.
On Uniform Weak König's Lemma.Ulrich Kohlenbach - 2002 - Annals of Pure and Applied Logic 114 (1-3):103-116.
Reverse Mathematics and a Ramsey-Type König's Lemma.Stephen Flood - 2012 - Journal of Symbolic Logic 77 (4):1272-1280.
Weak König's Lemma Implies Brouwer's Fan Theorem: A Direct Proof.Hajime Ishihara - 2006 - Notre Dame Journal of Formal Logic 47 (2):249-252.
Generalizing König's Infinity Lemma.Robert H. Cowen - 1977 - Notre Dame Journal of Formal Logic 18 (2):243-247.
The Differences Between Kurepa Trees and Jech-Kunen Trees.Renling Jin - 1993 - Archive for Mathematical Logic 32 (5):369-379.
Variations on a Theme by Weiermann.Toshiyasu Arai - 1998 - Journal of Symbolic Logic 63 (3):897-925.
Measure Theory and Weak König's Lemma.Xiaokang Yu & Stephen G. Simpson - 1990 - Archive for Mathematical Logic 30 (3):171-180.
The Weak König Lemma and Uniform Continuity.Josef Berger - 2008 - Journal of Symbolic Logic 73 (3):933-939.
Lebesgue Convergence Theorems and Reverse Mathematics.Xiaokang Yu - 1994 - Mathematical Logic Quarterly 40 (1):1-13.
On the Hamkins Approximation Property.William J. Mitchell - 2006 - Annals of Pure and Applied Logic 144 (1):126-129.

Analytics

Added to PP index
2016-09-28

Total views
8 ( #825,347 of 2,264,518 )

Recent downloads (6 months)
2 ( #612,816 of 2,264,518 )

How can I increase my downloads?

Downloads

My notes

Sign in to use this feature