Reverse mathematics, countable and uncountable: a computational approach

doi:10.1017/CBO9781139028592.009

Reverse mathematics, countable and uncountable: a computational approach

Published online by Cambridge University Press: 05 December 2013

Richard A. Shore

Edited by

Noam Greenberg ,

Denis Hirschfeldt ,

Joel David Hamkins and

Russell Miller

Show author details

Noam Greenberg: Affiliation:
Victoria University of Wellington
Denis Hirschfeldt: Affiliation:
University of Chicago
Joel David Hamkins: Affiliation:
College of Staten Island
Russell Miller: Affiliation:
Queens College, City University of New York

Book contents

Get access

Summary

Abstract Reverse mathematics analyzes the complexity of mathematical statements in terms of the strength of axiomatic systems needed to prove them. Its setting is countable mathematics and subsystems of second order arithmetic. We present a similar analysis based on (recursion-theoretic) computational complexity instead. In the countable case, this view is implicit in many of results in the area. By making it explicit and precise, we provide an alternate approach to this type of analysis for countable mathematics. It may be more intelligible to some mathematicians in that it replaces logic and proof systems with relative computability. In the uncountable case, second order arithmetic and its proof theory is insufficient for the desired analysis. Our computational approach, however, supplies a ready made paradigm for similar analyses. It can be implemented with any appropriate notion of computation on uncountable sets.

§1. Introduction. The enterprise of calibrating the strength of theorems of classical mathematics in terms of the (set existence) axioms needed to prove them, was begun by Harvey Friedman in the 1970s (as in [6] and [7]). It is now called Reverse Mathematics as, to prove that some set of axioms is actually necessary to establish a given theorem, one reverses the standard paradigm by proving that the axioms follow from the theorem (in some weak base theory). The original motivations for the subject were foundational and philosophical. It has become a remarkably fruitful and successful endeavor supplying a framework for both the philosophical questions about existence assumptions and foundational or mathematical ones about construction techniques needed to actually produce the objects that the theorems assert exist.

Type: Chapter
Information: Effective Mathematics of the Uncountable , pp. 150 - 163

DOI: https://doi.org/10.1017/CBO9781139028592.009 [Opens in a new window]

Publisher: Cambridge University Press

Print publication year: 2013

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

[1] Aharoni, R., Konig's duality theorem for infinite bipartite graphs, J. Lon. Math. Soc. (3) 29 (1984), 1–12.Google Scholar

[2] Aharoni, R., Magidor, M., and Shore, R.A., On the strength of Konig's duality theorem for infinite bipartite graphs, J. Combin. Theory Ser. B 54 (1992) 257–290.Google Scholar

[3] Blum, Lenore, Cucker, Felipe, Shub, Michael and Smale, Steve, Complexity and Real Computation, Springer-Verlag, New York, 1998.

[4] Chong, C.T.Techniques of Admissible Recursion Theory, LNM 1106, Springer-Verlag, Berlin, 1984.

[5] Fenstad, Jens Erik, General Recursion Theory: An Axiomatic Approach, Perspectives in Mathematical Logic, Springer-Verlag, Berlin-New York, 1980.

[6] Friedman, H., Higher set theory and mathematical practice, Ann. Math. Logic 2 (1971), 326–357.Google Scholar

[7] Friedman, H., Some systems of second order arithmetic and their use, Proc. Intl. Cong. Math., Vancouver 1974, vol. 1, Can. Math. Congress, 1975, 235–242.

[8] Grilliot, T.J.On effectively discontinuous type-2 objects. J. Symbolic Logic 36 (1971) 245–248.Google Scholar

[9] Hirst, J., Marriage theorems and reverse mathematics. In Logic and Computation (Pittsburgh, PA, 1987), Contemporary Mathematics 106, Amer. Math. Soc., Providence, RI, 1990, 181–196.

[10] Jockusch, C.G. Jr. and Soare, R.I., classes and the degrees of theories, Tran. AMS 173 (1972), 33–56.Google Scholar

[11] Kohlenbach, U., Higher order reverse mathematics. In Reverse Mathematics 2001, S., Simpson ed., 281–295, Lect. Notes Log. 21, Association for Symbolic Logic and A.K. Peters, Wellesley MA 2005.

[12] Lovasz, L. and Plummer, M. D., Matching Theory, Ann. Discrete Math. 29, North-Holland, Amsterdam, 1986.

[13] Metakides, G. and Nerode, A., Recursively enumerable vector spaces, Ann. Math. Logic 11 (1977), 147–171.Google Scholar

[14] Moldestad, J., Computations in Higher Types, LNM 574, Springer-Verlag, Berlin, 1977.

[15] Mummert, C. and Simpson, S.G., Reverse Mathematics and comprehension, Bulletin ofSymbolic Logic 11 (2005) 526–533.Google Scholar

[16] Montalban, A. and Shore, R.A., The limits of determinacy in second order arithmetic, Proceedings of the London Mathematical Society 104(3) (2012), 223–252.Google Scholar

[17] Sacks, Gerald E., Higher Recursion Theory, Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1990.

[18] Shore, R.A., On the jump of an α-recursively enumerable set, Trans. AMS 217 (1976), 351–364.Google Scholar

[19] Simpson, S., On the strength of König's duality theorem for countable bipartite graphs, J. Symbolic Logic 59 (1994) 113–123.Google Scholar

[20] Simpson, S., Subsystems ofSecond Order Arithmetic, 2nd edition, Perspectives in Logic, Association for Symbolic Logic and Cambridge University Press, New York, 2009.

Book contents

Reverse mathematics, countable and uncountable: a computational approach

Summary

Access options

References

Save book to Kindle

Save book to Dropbox

Save book to Google Drive