Hostname: page-component-cd9895bd7-gvvz8 Total loading time: 0 Render date: 2024-12-26T12:59:11.482Z Has data issue: false hasContentIssue false
  • English
  • Français

A NOTE ON PREDICATIVE ORDINAL ANALYSIS I: ITERATED COMPREHENSION AND TRANSFINITE INDUCTION

Published online by Cambridge University Press:  13 February 2019

SATO KENTARO
SATO KENTARO*
Affiliation:
INSTITUTE OF COMPUTER SCIENCE UNIVERSITY OF BERN NEUBRÜCKSTRASSE 10 BERN 3012, SWITZERLANDE-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

We determine the proof-theoretic ordinals (i) of ${\cal C} - {\bf{TI}}[\alpha ]$, the transfinite induction along α, for any hyperarithmetical level ${\cal C}$, in the first order setting and (ii) of any combination of iterated arithmetical comprehension and ${\cal C} - {\bf{TI}}[\alpha ]$ for ${\cal C}\, \equiv \,{\rm{\Pi }}_k^i ,{\rm{\Sigma }}_k^i$ ($i\, = \,0,1$) in the second order setting.

Keywords

03F0503F1503F2503F3003F3503D20proof-theoretic ordinalpartial conservationinfinitary semi-formal systemMints’s repetition ruleBuchholz’s finite code of infinitary proofprovably total functionHardy hierarchy
Type
Articles
Information
The Journal of Symbolic Logic , Volume 84 , Issue 1 , March 2019 , pp. 226 - 265
Copyright
Copyright © The Association for Symbolic Logic 2019 

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

Afshari, B. and Rathjen, M., Ordinal analysis and the infinite Ramsey theorem, How the World Computes: Turing Centenary Conference and 8th Conference on Computability in Europe, CiE 2012, (Cooper, S. B., Dawar, A., and Löwe, B., editors), Springer, Berlin, 2012, pp. 1–10.Google Scholar
Arai, T., A consistency proof of a system including Feferman’s IDξ by Takeuti’s reduction method. Tsukuba Journal of Mathematics, vol. 11 (1987), no. 2, pp. 227–239.10.21099/tkbjm/1496160577CrossRefGoogle Scholar
Avigad, J. and Sommer, R., A model-theoretic approach to ordinal analysis. The Bulletin of Symbolic Logic, vol. 3 (1997), no. 1, pp. 17–52.10.2307/421195CrossRefGoogle Scholar
Beklemishev, L., Proof-theoretic analysis by iterated reflection. Archive for Mathematical Logic, vol. 42 (2003), no. 6, pp. 515–552.10.1007/s00153-002-0158-7CrossRefGoogle Scholar
Buchholz, W., Explaining Gentzen’s consistency proof within infinitary proof theory, Computational Logic and Proof Theory: 5th Kurt Gödel Colloquium, KGC ’97 (Gottlob, G., Leitsch, A., and Mundici, D., editors), Springer, Berlin, 1997, pp. 4–17.10.1007/3-540-63385-5_29CrossRefGoogle Scholar
Feferman, S., Systems of predicative analysis, II: Representations of ordinals, this Journal, vol. 33 (1968), no. 2, pp. 193–220.Google Scholar
Flumini, D. and Sato, K., From hierarchies to well-foundedness. Archive for Mathematical Logic, vol. 53 (2014), no. 7-8, pp. 855–863.10.1007/s00153-014-0392-9CrossRefGoogle Scholar
Hájek, P. and Pudlák, P., Metamathematics of First-Order Arithmetic, Springer, Berlin, 1993.10.1007/978-3-662-22156-3CrossRefGoogle Scholar
Mints, G., Finite investigations of transfinite derivations. Journal of Soviet Mathematics, vol. 10 (1978), no. 4, pp. 548–596.10.1007/BF01091743CrossRefGoogle Scholar
Pohlers, W., Proof Theory: The First Step into Impredicativity, Springer, Berlin, 2009.Google Scholar
Rüede, C. and Strahm, T., Intuitionistic fixed point theories for strictly positive operators. Mathematical Logic Quarterly, vol. 48 (2002), no. 2, pp. 195–202.10.1002/1521-3870(200202)48:2<195::AID-MALQ195>3.0.CO;2-S3.0.CO;2-S>CrossRefGoogle Scholar
Sato, K., Monotone and cofinal transfinite induction, draft, 2016.Google Scholar
Simpson, S., Subsystems of Second Order Arithmetic, Cambridge University Press, New York, 2009.10.1017/CBO9780511581007CrossRefGoogle Scholar
Simpson, S., Comparing WO($\omega ^\omega $) with ${\rm{\Sigma }}_2^0 $ induction, 2015, arXiv:1508.02655.Google Scholar
Tait, W., Nested recursion. Mathematische Annalen, vol. 143 (1961), no. 3, pp. 236–250.10.1007/BF01342980CrossRefGoogle Scholar