Hostname: page-component-cd9895bd7-dzt6s Total loading time: 0 Render date: 2024-12-25T02:53:57.915Z Has data issue: false hasContentIssue false
  • English
  • Français

A Model-Theoretic Approach to Ordinal Analysis

Published online by Cambridge University Press:  15 January 2014

Jeremy Avigad  and
Richard Sommer
Jeremy Avigad
Affiliation:
Department of Philosophy, Carnegie Mellon University, Pittsburgh, PA 15213, USA, E-mail: [email protected]
Richard Sommer
Affiliation:
Department of Mathematics, Stanford University, Stanford, CA 94305-2125, USA, E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

We describe a model-theoretic approach to ordinal analysis via the finite combinatorial notion of an α-large set of natural numbers. In contrast to syntactic approaches that use cut elimination, this approach involves constructing finite sets of numbers with combinatorial properties that, in nonstandard instances, give rise to models of the theory being analyzed. This method is applied to obtain ordinal analyses of a number of interesting subsystems of first- and second-order arithmetic.

Type
Research Article
Information
Bulletin of Symbolic Logic , Volume 3 , Issue 1 , March 1997 , pp. 17 - 52
Copyright
Copyright © Association for Symbolic Logic 1997

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] Aczel, Peter, An introduction to inductive definitions, in [5], pp. 739–782.Google Scholar
[2] Avigad, Jeremy, Formalizing forcing arguments in subsystems of second-order arithmetic, Annals of Pure and Applied Logic, vol. 82 (1996), pp. 165–191.Google Scholar
[3] Avigad, Jeremy, On the relationship between ATR0 and , Journal of Symbolic Logic, vol. 61 (1996), pp. 768–779.CrossRefGoogle Scholar
[4] Avigad, Jeremy and Sommer, Richard, The model-theoretic ordinal analysis of theories of predicative strength, Journal of Symbolic Logic, to appear.Google Scholar
[5] Barwise, Jon, The handbook of mathematical logic, North-Holland, 1977.Google Scholar
[6] Feferman, Solomon, Theories of finite type related to mathematical practice, in [5], pp. 913–971.Google Scholar
[7] Feferman, Solomon, Iterated inductive fixed-point theories: Application to Hancock's conjecture, Patras logic symposium (Metakides, G., editor), North-Holland, 1982.Google Scholar
[8] Friedman, Harvey, Iterated inductive definitions and -AC, Intuitionism and proof theory (Kino, A. et al., editors), North-Holland, 1970, pp. 435–442.Google Scholar
[9] Friedman, Harvey, McAloon, Kenneth, and Simpson, Stephen, A finite combinatorial principle which is equivalent to the 1-consistency of predicative analysis, Patras logic symposium (Metakides, G., editor), North-Holland, 1982, pp. 197–230.Google Scholar
[10] Hájek, Petr and Pudlák, Pavel, Metamathematics of first-order arithmetic, Springer-Verlag, 1991.Google Scholar
[11] Kaye, Richard, Models of Peano arithmetic, Oxford University, 1991.Google Scholar
[12] Ketonen, Jussi and Solovay, Robert, Rapidly growing Ramsey functions, Annals of Mathematics, vol. 113 (1981), pp. 267–314.CrossRefGoogle Scholar
[13] Kirby, L. and Paris, J., Initial segments of models of Peano's axioms, Springer-Verlag Lecture Notes in Mathematics, vol. 619, 1977, pp. 211–216.Google Scholar
[14] Kotlarski, H. and Ratajczyk, Z., Inductive full satisfaction classes, Annals of Pure and Applied Logic, vol. 47 (1990), pp. 199–223.Google Scholar
[15] Paris, Jeff B., A hierarchy of cuts in models of arithmetic, Springer-Verlag Lecture Notes in Mathematics, vol. 834, 1980, pp. 312–337.Google Scholar
[16] Paris, Jeff B. and Harrington, Leo, A mathematical incompleteness in Peano arithmetic, in [5], pp. 1132–1142.Google Scholar
[17] Pohlers, Wolfram, Proof theory: An introduction, Springer-Verlag Lecture Notes in Mathematics, vol. 1407, 1989.Google Scholar
[18] Pohlers, Wolfram, A short course in ordinal analysis, Proof theory (Aczel, et al., editors), Cambridge University Press, 1993.Google Scholar
[19] Ratatczyk, Zygmunt, Subsystems of true arithmetic and hierarchies of functions, Annals of Pure and Applied Logic, vol. 64 (1993), pp. 95–152.Google Scholar
[20] Rathjen, Michael, Admissible proof theory and beyond, Logic, methodology, and the philosophy of science IX (Prawitz, D. et al., editors), Elsevier, 1994, pp. 123–147.Google Scholar
[21] Rathjen, Michael, Proof theory of reflection, Annals of Pure and Applied Logic, vol. 68 (1994), pp. 181–224.Google Scholar
[22] Rathjen, Michael, Recent advances in ordinal analysis: -CA and related systems, this Bulletin, vol. 1 (1995), pp. 468–485.Google Scholar
[23] Rose, H. E., Subrecursion: Functions and hierarchies, Clarendon, 1984.Google Scholar
[24] Schütte, Kurt, Proof theory, Springer-Verlag, 1977.CrossRefGoogle Scholar
[25] Schwichtenberg, Helmut, Proof theory: Some applications of cut-elimination, in [5], pp. 867–895.Google Scholar
[26] Simpson, Stephen G., Subsystems of second order arithmetic, preprint.Google Scholar
[27] Simpson, Stephen G., Subsystems of Z2 and reverse mathematics, appendix to Gaisi Takeuti, Proof theory, second ed., North-Holland, 1987.Google Scholar
[28] Simpson, Stephen G., On the strength of König's duality theorem of countable bipartite graphs, Journal of Symbolic Logic, vol. 59 (1994), pp. 113–123.Google Scholar
[29] Smith, Rick, The consistency strengths of some finite forms of the Higman and Kruskal theorems, Harvey Friedman's research on the foundations of mathematics (Harrington, Leo et al., editors), North-Holland, 1985, pp. 119–135.Google Scholar
[30] Sommer, Richard, Transfinite induction and hierarchies generated by transfinite recursion within Peano arithmetic, Ph.D. thesis , University of California, Berkeley, 1990.Google Scholar
[31] Sommer, Richard, Ordinals in bounded arithmetic, Arithmetic, proof theory, and complexity (Clote, Peter and Krajiček, Jan, editors), Oxford University Press, 1992.Google Scholar
[32] Sommer, Richard, Transfinite induction within Peano arithmetic, Annals of Pure and Applied Logic, vol. 76 (1995), pp. 231–289.Google Scholar
[33] Wainer, S. S., A classification of the ordinal recursive functions, Archiv für mathematische Logik, vol. 13 (1970), pp. 136–153.CrossRefGoogle Scholar