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

Ordinal inequalities, transfinite induction, and reverse mathematics

Published online by Cambridge University Press:  12 March 2014

Jeffry L. Hirst
Jeffry L. Hirst*
Affiliation:
Department of Mathematical Sciences, Appalachian State University, Boone, NC 28608, E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

If α and β are ordinals, α ≤ β, and β ≰ α then α+ 1 < β. The first result of this paper shows that the restriction of this statement to countable well orderings is provably equivalent to ACA0, a subsystem of second order arithmetic introduced by Friedman. The proof of the equivalence is reminiscent of Dekker's construction of a hypersimple set. An application of the theorem yields the equivalence of the set comprehension scheme ACA0 and an arithmetical transfinite induction scheme.

Keywords

reverse mathematicsproof theory
Type
Research Article
Information
The Journal of Symbolic Logic , Volume 64 , Issue 2 , June 1999 , pp. 769 - 774
Copyright
Copyright © Association for Symbolic Logic 1999

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] Avigad, J. and Sommer, R., The model-theoretic ordinal analysis of predicative theories, pre-print.Google Scholar
[2] Dekker, J.C.E., A theorem on hypersimple sets, Proceedings of the American Mathematical Society, vol. 5 (1955), pp. 791–796.Google Scholar
[3] Friedman, H., Some systems of second order arithmetic and their use, Proceedings of the international congress of mathematicians, vol. 1, (Vancouver, Canada, 1974), Canadian Mathematical Congress, 1975, pp. 235–242.Google Scholar
[4] Friedman, H., Systems of second order arithmetic with restricted induction (abstracts), this Journal, vol. 41 (1976), pp. 557–559.Google Scholar
[5] Friedman, H. and Hirst, J., Weak comparability of well orderings and reverse mathematics, Annals of Pure and Applied Logic, vol. 47 (1990), pp. 11–29.CrossRefGoogle Scholar
[6] Girard, J., Proof theory and logical complexity, Bibliopolis, Napoli, 1987.Google Scholar
[7] Hirst, J., Reverse mathematics and ordinal exponentiation, Annals of Pure and Applied Logic, vol. 66 (1994), pp. 1–18.Google Scholar
[8] Simpson, S., and transfinite induction, Logic Colloquium '80, North Holland, 1982, pp. 239–253.Google Scholar
[9] Simpson, S., Reverse mathematics, Proceedings of Symposia in Pure Mathematics, vol. 42 (1985), pp. 461–471.Google Scholar
[10] Simpson, S., Subsystems of second order arithmetic, Springer-Verlag, Berlin/Heidelberg, 1998.Google Scholar