Article contents
Ordinal inequalities, transfinite induction, and reverse mathematics
Published online by Cambridge University Press: 12 March 2014
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
- Type
- Research Article
- Information
- Copyright
- Copyright © Association for Symbolic Logic 1999
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
[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
- 4
- Cited by