×

On the strength of König’s duality theorem for countable bipartite graphs. (English) Zbl 0798.03060

Summary: 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 K. P. Podewski and K. Steffens [J. Comb. Theory, Ser. B 21, 40-46 (1976; Zbl 0357.04017)].) Let \(\text{ATR}_ 0\) be the subsystem of second-order arithmetic with arithmetical transfinite recursion and restricted induction. Let \(\text{RCA}_ 0\) be the subsystem of second-order arithmetic with recursive comprehension and restricted induction. We show that CKDT is provable in \(\text{ATR}_ 0\). Combining this with a result of R. Aharoni, M. Magidor and R. A. Shore [ibid. 54, 257-290 (1992; Zbl 0754.05053)], we see the CKDT is logically equivalent to the axiom of \(\text{ATR}_ 0\), the equivalence being provable in \(\text{RCA}_ 0\).

MSC:

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

References:

[1] Logical analysis of some theorems of combinatorics and topological dynamics 65 pp 125– (1987) · Zbl 0652.03040
[2] Systems of second-order arithmetic with restricted induction I, II 41 pp 557– (1976)
[3] Journal of the London Mathematical Society (Second Series) 29 pp 1– (1984)
[4] Proof theory (1987)
[5] Proof theory pp 432– (1987)
[6] Logic Colloquium ’80 pp 239– (1982)
[7] Logic Colloquium ’80 pp 255– (1982)
[8] Theory of recursive functions and effective computability (1967) · Zbl 0183.01401
[9] DOI: 10.1016/0095-8956(76)90025-3 · Zbl 0357.04017 · doi:10.1016/0095-8956(76)90025-3
[10] Patras logic symposion (1982) · Zbl 0504.00001
[11] Logic colloquium ’80 (1982)
[12] DOI: 10.1016/0168-0072(91)90050-V · Zbl 0746.03049 · doi:10.1016/0168-0072(91)90050-V
[13] Logic and combinatorics 65 (1987)
[14] Theorie der Endlichen und Unendlichen Graphen (1936) · JFM 62.0654.05
[15] Patras logic symposion (1982) · Zbl 0504.00001
[16] DOI: 10.1016/0095-8956(92)90057-5 · Zbl 0754.05053 · doi:10.1016/0095-8956(92)90057-5
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.