`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.

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
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
.

- Introduction
- Subsystems of Second Order Arithmetic
- Proof of the Main Theorem
- Bibliography
- About this document ...