David Bourget (Western Ontario)
David Chalmers (ANU, NYU)
Rafael De Clercq
Jack Alan Reynolds
Learn more about PhilPapers
Journal of Symbolic Logic 59 (1):113-123 (1994)
Let CKDT be the assertion that for every countably infinite bipartite graph G, there exist a vertex covering C of G and a matching M in G such that C consists of exactly one vertex from each edge in M. (This is a theorem of Podewski and Steffens .) Let ATR0 be the subsystem of second-order arithmetic with arithmetical transfinite recursion and restricted induction. Let RCA0 be the subsystem of second-order arithmetic with recursive comprehension and restricted induction. We show that CKDT is provable in ART0. Combining this with a result of Aharoni, Magidor, and Shore , we see that CKDT is logically equivalent to the axioms of ATR0, the equivalence being provable in RCA0
|Keywords||Matchings coverings bipartite graph reverse mathematics second-order arithmetic subsystems|
|Categories||categorize this paper)|
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
No references found.
Citations of this work BETA
No citations found.
Similar books and articles
Peter A. Cholak, Carl G. Jockusch & Theodore A. Slaman (2001). On the Strength of Ramsey's Theorem for Pairs. Journal of Symbolic Logic 66 (1):1-55.
A. James Humphreys & Stephen G. Simpson (1999). Separation and Weak König's Lemma. Journal of Symbolic Logic 64 (1):268-278.
Ulrich Kohlenbach (1999). A Note on Goodman's Theorem. Studia Logica 63 (1):1-5.
Douglas K. Brown & Stephen G. Simpson (1993). The Baire Category Theorem in Weak Subsystems of Second-Order Arithmetic. Journal of Symbolic Logic 58 (2):557-578.
J. C. E. Dekker (1981). Twilight Graphs. Journal of Symbolic Logic 46 (3):539-571.
Victor Harnik & Michael Makkai (1976). Applications of Vaught Sentences and the Covering Theorem. Journal of Symbolic Logic 41 (1):171-187.
Stephen G. Simpson (1984). Which Set Existence Axioms Are Needed to Prove the Cauchy/Peano Theorem for Ordinary Differential Equations? Journal of Symbolic Logic 49 (3):783-802.
Carl Mummert & Stephen G. Simpson (2005). Reverse Mathematics and Π21 Comprehension. Bulletin of Symbolic Logic 11 (4):526-533.
Jeffry L. Hirst (1999). Ordinal Inequalities, Transfinite Induction, and Reverse Mathematics. Journal of Symbolic Logic 64 (2):769-774.
Sorry, there are not enough data points to plot this chart.
Added to index2009-01-28
Total downloads4 ( #272,064 of 1,139,970 )
Recent downloads (6 months)1 ( #157,515 of 1,139,970 )
How can I increase my downloads?