On the strength of König's duality theorem for countable bipartite graphs

DOI10.2307/2275254zbMath0798.03060OpenAlexW2133598398MaRDI QIDQ4292597

Stephen G. Simpson

Publication date: 3 November 1994

Published in: Journal of Symbolic Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.2307/2275254

zbMATH Keywords

matchingreverse mathematicsvertex coveringrecursive comprehensionsubsystem of second-order arithmeticcountably infinite bipartite graph

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Transversal (matching) theory (05D15) Second- and higher-order arithmetic and fragments (03F35)

Related Items

The model-theoretic ordinal analysis of theories of predicative strength ⋮ Reverse Mathematics: The Playground of Logic ⋮ The computational strength of matchings in countable graphs ⋮ Menger's theorem in \(\Pi^1_1 \mathrm {-CA}_0\) ⋮ A Model-Theoretic Approach to Ordinal Analysis ⋮ Computing maximal chains ⋮ On the relationship between ATR₀ and ⋮ 2010 European Summer Meeting of the Association for Symbolic Logic. Logic Colloquium '10 ⋮ Ordinals and graph decompositions ⋮ Formalizing forcing arguments in subsystems of second-order arithmetic

Cites Work

• Unnamed Item
• Unnamed Item
• Borel quasi-orderings in subsystems of second-order arithmetic
• On the strength of König's duality theorem for infinite bipartite graphs
• Injective choice functions for countable families
• Patras Logic Symposion. Proceedings of the Logic Symposion held at Patras, Greece, August 18--22, 1980

This page was built for publication: On the strength of König's duality theorem for countable bipartite graphs