Hostname: page-component-78c5997874-t5tsf Total loading time: 0 Render date: 2024-11-05T10:31:28.197Z Has data issue: false hasContentIssue false
  • English
  • Français

HOW STRONG ARE SINGLE FIXED POINTS OF NORMAL FUNCTIONS?

Part of: Proof theory and constructive mathematics General logic Computability and recursion theory Set theory

Published online by Cambridge University Press:  20 July 2020

ANTON FREUND
ANTON FREUND*
Affiliation:
FACHBEREICH MATHEMATIK TECHNISCHE UNIVERSITÄT DARMSTADT SCHLOSSGARTENSTRASSE 7, 64289DARMSTADT, GERMANYE-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

In a recent paper by M. Rathjen and the present author it has been shown that the statement “every normal function has a derivative” is equivalent to $\Pi ^1_1$ -bar induction. The equivalence was proved over $\mathbf {ACA_0}$ , for a suitable representation of normal functions in terms of dilators. In the present paper, we show that the statement “every normal function has at least one fixed point” is equivalent to $\Pi ^1_1$ -induction along the natural numbers.

Keywords

normal functionfixed pointreverse mathematicsdilatorwell-ordering principleΠ11-induction

MSC classification

Primary: 03B30: Foundations of classical theories (including reverse mathematics)
Secondary: 03F15: Recursive ordinals and ordinal notations 03E10: Ordinal and cardinal numbers 03D60: Computability and recursion theory on ordinals, admissible sets, etc.
Type
Articles
Information
The Journal of Symbolic Logic , Volume 85 , Issue 2 , June 2020 , pp. 709 - 732
Copyright
© The Association for Symbolic Logic 2020

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

Aczel, P., Mathematical Problems in Logic, PhD Thesis, Oxford, 1966.Google Scholar
Aczel, P., Normal functors on linear orderings. this Journal, vol. 32 (1967), p. 430, abstract to a paper presented at the annual meeting of the Association for Symbolic Logic, Houston, Texas, 1967.Google Scholar
Freund, A., Type-Two Well-Ordering Principles, Admissible Sets, and ${\boldsymbol{\varPi}}_{\mathbf{1}}^{\mathbf{1}}$ -Comprehension, PhD thesis, University of Leeds, 2018. Available at http://etheses.whiterose.ac.uk/20929/ (accessed 10 May, 2019).Google Scholar
Freund, A., ${\varPi}_{1}^{1}$ -comprehension as a well-ordering principle . Advances in Mathematics, vol. 355 (2019), Article no. 106767.CrossRefGoogle Scholar
Freund, A., A categorical construction of Bachmann-Howard fixed points . Bulletin of the London Mathematical Society, vol. 51 (2019), no. 5, pp. 801–814.CrossRefGoogle Scholar
Freund, A., A note on ordinal exponentiation and derivatives of normal functions. Mathematical Logic Quarterly, to appear. http://arXiv:1908.00280.Google Scholar
Freund, A., Computable aspects of the Bachmann-Howard principle. Journal of Mathematical Logic, vol. 20 (2020), no. 2, Article no. 2050006.CrossRefGoogle Scholar
Freund, A. and Rathjen, M., Derivatives of normal functions in reverse mathematics, preprint, 2019. http://arXiv:1904.04630.Google Scholar
Girard, J. Y., ${\varPi}_2^1$ -logic, part 1: Dilators . Annals of Pure and Applied Logic, vol. 21 (1981), pp. 75–219.Google Scholar
Girard, J. Y., Proof Theory and Logical Complexity, vol. 1, Studies in Proof Theory, Bibliopolis, Napoli, 1987.Google Scholar
Girard, J. Y., Proof theory and logical complexity, vol. 2, manuscript, 1982. Available at: http://girard.perso.math.cnrs.fr/Archives4.html (accessed 21 November 2017).Google Scholar
Hirst, J. L., Reverse mathematics and ordinal exponentiation . Annals of Pure and Applied Logic, vol. 66 (1994), pp. 1–18.CrossRefGoogle Scholar
Marcone, A. and Montalbán, A., The Veblen functions for computability theorists, this Journal, vol. 76 (2011), pp. 575–602.Google Scholar
Schütte, K., Proof theory , Grundlehren der Mathematischen Wissenschaften, vol. 225, Springer, Berlin, 1977.Google Scholar
Simpson, S. G., Subsystems of second order arithmetic , Perspectives in Logic, Cambridge University Press, Cambridge, 2009.Google Scholar