Next: Introduction

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

Stephen G. Simpson

t20@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 be the subsystem of second order arithmetic with arithmetical transfinite recursion and restricted induction. Let be the subsystem of second order arithmetic with recursive comprehension and restricted induction. We show that CKDT is provable in . Combining this with a result of Aharoni, Magidor and Shore [2], we see that CKDT is logically equivalent to the axioms of , the equivalence being provable in .

Stephen G Simpson
1998-10-25