On the Strength of König's Duality Theorem for Countable Bipartite Graphs

Stephen G. Simpson

simpson@math.psu.edu
Pennsylvania State University
September 18, 1992

Research partially supported by NSF Grant DMS-9002072. The referee provided some useful suggestions.

Published in Journal of Symbolic Logic, 59, 1994, pp. 113-123.

Abstract:

Let CKDT be the assertion that, for every countably infinite bipartite graph G, there exist a vertex covering C of Gand 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 $\mathsf{ATR}_0$ be the subsystem of second order arithmetic with arithmetical transfinite recursion and restricted induction. Let $\mathsf{RCA}_0$ be the subsystem of second order arithmetic with recursive comprehension and restricted induction. We show that CKDT is provable in $\mathsf{ATR}_0$. Combining this with a result of Aharoni, Magidor and Shore [2], we see that CKDT is logically equivalent to the axioms of $\mathsf{ATR}_0$, the equivalence being provable in $\mathsf{RCA}_0$.