On the strength of könig's duality theorem for countable bipartite graphs
Journal of Symbolic Logic 59 (1):113-123 (1994)
| Abstract | 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 [12].) 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 [2], we see that CKDT is logically equivalent to the axioms of ATR0, the equivalence being provable in RCA0 | |||||||||
| Keywords | No keywords specified (fix it) | |||||||||
| Categories | ||||||||||
| Options |
|
|||||||||
Download options| PhilPapers Archive |
Upload a copy of this paper Check publisher's policy on self-archival Papers currently archived: 5,664 |
| External links |
 |
| Through your library | Configure |
Similar books and articlesPeter 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.
Analytics
Monthly downloads
Sorry, there are not enough data points to plot this chart.
|
Added to index2009-01-28Total downloads0Recent downloads (6 months)0How can I increase my downloads? |
My notes
Discussion
