Hostname: page-component-cd9895bd7-gbm5v Total loading time: 0 Render date: 2024-12-23T18:49:49.122Z Has data issue: false hasContentIssue false
  • English
  • Français

On the strength of König's duality theorem for countable bipartite graphs

Published online by Cambridge University Press:  12 March 2014

Stephen G. Simpson
Stephen G. Simpson*
Affiliation:
Department of Mathematics, Pennsylvania State University, University Park, State College, Pennsylvania16802, E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

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

Keywords

Matchingscoveringsbipartitegraphreverse mathematicssecond-order arithmeticsubsystems
Type
Research Article
Information
The Journal of Symbolic Logic , Volume 59 , Issue 1 , March 1994 , pp. 113 - 123
Copyright
Copyright © Association for Symbolic Logic 1994

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

[1]Aharoni, R., König's duality theorem for infinite bipartite graphs, Journal of the London Mathematical Society (Second Series), vol. 29 (1984), pp. 1–12.Google Scholar
[2]Aharoni, R., Magidor, M., and Shore, R. A., On the strength of König's duality theorem for infinite bipartite graphs, Journal of Combinatorial Theory (B), vol. 54 (1992), pp. 257–290.CrossRefGoogle Scholar
[3]Blass, A. R., Hirst, J. L., and Simpson, S. G., Logical analysis of some theorems of combinatorics and topological dynamics, (Simpson, S. G., editor), Contemporary Mathematics, vol. 65, American Mathematical Society, Providence, Rhode Island, 1987, pp. 125–156.Google Scholar
[4]Friedman, H., Subsystems of set theory and analysis, Ph.D. Thesis, Massachusetts Institute of Technology, Cambridge, Massachusetts, 1967.Google Scholar
[5]Friedman, H., Systems of second-order arithmetic with restricted induction I, II (abstracts), this Journal, vol. 41 (1976), pp. 557–559.Google Scholar
[6]Friedman, H. M., McAloon, K., and Simpson, S. G., A finite combinatorial principle which is equivalent to the l-consistency of predicative analysis, Patras logic symposion (Metakides, G., editor), North-Holland, Amsterdam, 1982.Google Scholar
[7]König, D., Theorie der Endlichen und Unendlichen Graphen, Akademische Verlagsgesellschaft, Leipzig, 1936; reprinted by Chelsea, New York, 1950.Google Scholar
[8]Simpson, S. G. (editor), Logic and combinatorics, Contemporary Mathematics, vol. 65, American Mathematical Society, Providence, Rhode Island, 1987.CrossRefGoogle Scholar
[9]van Dalen, D., Lascar, D., and Smiley, J. (editor), Logic colloquium '80, North-Holland, Amsterdam, 1982.Google Scholar
[10]Marcone, A., Borel quasiorderings in subsystems of second-order arithmetic, Annals of Pure and Applied Logic, vol. 54 (1991), pp. 265–291.CrossRefGoogle Scholar
[11]Metakides, G. (editor), Patras logic symposion, North-Holland, Amsterdam, 1982.Google Scholar
[12]Podewski, K. P. and Steffens, K., Injective choice functions for countable families, Journal of Combinatorical Theory (B), vol. 21 (1976), pp. 40–46.CrossRefGoogle Scholar
[13]Rogers, H. Jr., Theory of recursive functions and effective computability, McGraw-Hill, New York, 1967; reprinted by M.I.T. Press, Cambridge, Massachusetts, 1987.Google Scholar
[14]Simpson, S. G., Set-Theoretic aspects of ATR0, Logic Colloquium '80 (van Dalen, D., Lascar, D., and Smiley, J., editors), North-Holland, Amsterdam, 1982, pp. 255–271.Google Scholar
[15]Simpson, S. G., and transfinite induction, Logic Colloquium '80 (van Dalen, D., Lascar, D., and Smiley, J., editors), North-Holland, Amsterdam, 1982, pp. 239–253.Google Scholar
[16]Simpson, S. G., Subsystems of Z2 and reverse mathematics, Proof theory (second edition) (Takeuti, G., editor), North-Holland, Amsterdam, 1987, pp. 432–446.Google Scholar
[17]Simpson, S. G., Subsystems of second-order arithmetic, in preparation.Google Scholar
[18]Takeuti, G., Proof theory (second edition), North-Holland, Amsterdam, 1987.Google Scholar