Date: September 18, 1992
Title: On the Strength of K"onig's Duality Theorem
for Countable Bipartite Graphs
Author: Stephen G. Simpson
Definitions: A bipartite graph is an ordered triple (X,Y,E) such that
X and Y are disjoint sets and E is a subset of {{x,y}:x in X, y in Y}.
The vertices are the elements of X union Y. The edges are the
elements of E. A covering is a set of vertices which meets every
edge. A matching is a pairwise dijoint set of edges.
History: K"onig's duality theorem says that, for every finite
bipartite graph, the minimum cardinality of a covering is equal to the
maximum cardinality of a matching. This is proved by showing that for
every finite bipartite graph there exists a K"onig covering, i.e. an
ordered pair (C,M) such that C is a covering, M is a matching, and C
consists of exactly one vertex from each edge in M. Podewski and
Steffens showed that every countably infinite bipartite graph has a
K"onig covering. Aharoni proved the same result for uncountable
bipartite graphs. Aharoni, Magidor, and Shore (Journal of
Combinatorial Theory (B), 54, 1992, 257-290) studied the following
logical or foundational question: Which set existence axioms are
needed to prove the Podewski-Steffens theorem and Aharoni's theorem?
They showed that the Podewski-Steffens theorem logically implies the
axioms of ATR_0, this implication being provable in RCA_0. (Here
ATR_0 is the subsystem of second order arithmetic with arithmetical
transfinite recursion and restricted induction, and RCA_0 is the
subsystem of second order arithmetic with recursive comprehension and
restricted induction.)
New results: We show that the Podewski-Steffens theorem is provable in
ATR_0. This solves a problem stated by Aharoni, Magidor and Shore.
Combining our result with theirs, we see that the Podewski-Steffens
theorem is logically equivalent to the principal axiom of ATR_0, this
equivalence being provable in RCA_0. Thus ATR_0 is the weakest
natural subsystem of second order arithmetic in which the
Podewski-Steffens theorem is provable.
Author email: simpson@math.psu.edu
Available: http://math.psu.edu/simpson/papers/bipartite.ps
Format: PostScript (AMS-LaTeX source is also available)
Publication: Journal of Symbolic Logic, vol. 59, 1994, pp. 113-123.