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)|
References found in this work BETA
Borel Quasi-Orderings in Subsystems of Second-Order Arithmetic.Alberto Marcone - 1991 - Annals of Pure and Applied Logic 54 (3):265-291.
Citations of this work BETA
Formalizing Forcing Arguments in Subsystems of Second-Order Arithmetic.Jeremy Avigad - 1996 - Annals of Pure and Applied Logic 82 (2):165-191.
Reverse Mathematics: The Playground of Logic.Richard A. Shore - 2010 - Bulletin of Symbolic Logic 16 (3):378-402.
A Model-Theoretic Approach to Ordinal Analysis.Jeremy Avigad & Richard Sommer - 1997 - Bulletin of Symbolic Logic 3 (1):17-52.
Similar books and articles
On the Strength of Ramsey's Theorem for Pairs.Peter A. Cholak, Carl G. Jockusch & Theodore A. Slaman - 2001 - Journal of Symbolic Logic 66 (1):1-55.
Separation and Weak König's Lemma.A. James Humphreys & Stephen G. Simpson - 1999 - Journal of Symbolic Logic 64 (1):268-278.
The Baire Category Theorem in Weak Subsystems of Second-Order Arithmetic.Douglas K. Brown & Stephen G. Simpson - 1993 - Journal of Symbolic Logic 58 (2):557-578.
Applications of Vaught Sentences and the Covering Theorem.Victor Harnik & Michael Makkai - 1976 - Journal of Symbolic Logic 41 (1):171-187.
Which Set Existence Axioms Are Needed to Prove the Cauchy/Peano Theorem for Ordinary Differential Equations?Stephen G. Simpson - 1984 - Journal of Symbolic Logic 49 (3):783-802.
Reverse Mathematics and Π21 Comprehension.Carl Mummert & Stephen G. Simpson - 2005 - Bulletin of Symbolic Logic 11 (4):526-533.
Ordinal Inequalities, Transfinite Induction, and Reverse Mathematics.Jeffry L. Hirst - 1999 - Journal of Symbolic Logic 64 (2):769-774.
Added to index2009-01-28
Total downloads6 ( #553,471 of 2,158,461 )
Recent downloads (6 months)1 ( #354,692 of 2,158,461 )
How can I increase my downloads?