Hostname: page-component-cd9895bd7-hc48f Total loading time: 0 Render date: 2024-12-26T00:44:27.241Z Has data issue: false hasContentIssue false
  • English
  • Français

Transfinite Progressions: A Second Look at Completeness

Published online by Cambridge University Press:  15 January 2014

Torkel Franzén
Torkel Franzén*
Affiliation:
Department of Computer Science and Electrical Engineering, Luleå University of Technology, SE-97187, Luleå, SwedenE-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Extract

§1. Iterated Gödelian extensions of theories. The idea of iterating ad infinitum the operation of extending a theory T by adding as a new axiom a Gödel sentence for T, or equivalently a formalization of “T is consistent”, thus obtaining an infinite sequence of theories, arose naturally when Godel's incompleteness theorem first appeared, and occurs today to many non-specialists when they ponder the theorem. In the logical literature this idea has been thoroughly explored through two main approaches. One is that initiated by Turing in his “ordinal logics” (see Gandy and Yates [2001]) and taken very much further in Feferman's work on transfinite progressions, which also introduced the more general study of extensions by reflection principles, of which consistency statements are a special case. This approach starts from an assignment of theories to ordinal notations, and extracts sequences of theories through a suitable choice of a path in the set of ordinal notations. The second approach, illustrated in particular by the work of Schmerl and Beklemishev, starts instead from a suitably well-behaved primitive recursive well-ordering, which is used to define a sequence of theories. This second approach has led to precise results about the relative proof-theoretical strength of sequences of theories obtained by iterating different reflection principles. The Turing-Feferman approach, on the other hand, lends itself well to an investigation in qualitative and philosophical terms of the relevance of such iterated reflection extensions to mathematical knowledge, in particular because of two developments associated with this approach.

Type
Research Article
Information
Bulletin of Symbolic Logic , Volume 10 , Issue 3 , September 2004 , pp. 367 - 389
Copyright
Copyright © Association for Symbolic Logic 2004

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

Beklemishev, L. [1995], Iterated local reflection versus iterated consistency, Annals of Pure and Applied Logic, vol. 75, pp. 25–48.Google Scholar
Feferman, S. [1960], Arithmetization of metamathematics in a general setting, Fundamenta Mathematicae, vol. 49, pp. 35–92.Google Scholar
Feferman, S. [1962a], Classifications of recursive functions by means of hierarchies, Transactions of the American Mathematical Society, vol. 104, pp. 101–122.Google Scholar
Feferman, S. [1962b], Transfinite recursive progressions of axiomatic theories, The Journal of Symbolic Logic, vol. 27, pp. 259–316.Google Scholar
Feferman, S. and Spector, C. [1962], Incompleteness along paths in progressions of theories, The Journal of Symbolic Logic, vol. 27, pp. 383–390.Google Scholar
Fenstad, J. [1968], On the completeness of some transfinite recursive progressions of axiomatic theories, The Journal of Symbolic Logic, vol. 33, pp. 69–76.Google Scholar
Franzén, T. [2004], Inexhaustibility: a non-exhaustive study, Lecture Notes in Logic, Association for Symbolic Logic and A K Peters, To appear.Google Scholar
Gandy, R.O. and Yates, C.E.M. (editors) [2001], Mathematical logic, Collected Works of A. M. Turing, Elsevier, Amsterdam.Google Scholar
Hájek, P. and Pudlák, P. [1993], Metamathematics of first-order arithmetic, Springer-Verlag, Berlin, New York.Google Scholar
Kreisel, G., Shoenfield, J., and Wang, H. [1959], Number theoretic concepts andrecursive well-orderings, Archiv fur Mathematische Logik und Grundlagenforschung, vol. 5, pp. 42–64.CrossRefGoogle Scholar
Löb, M. H. [1955], Solution of a problem of Leon Henkin, The Journal of Symbolic Logic, vol. 20, pp. 115–118.CrossRefGoogle Scholar
Mints, G. [1976], The universality of the canonical tree, Soviet Mathematical Doklady, vol. 17, no. 2.Google Scholar
Schmerl, U. R. [1979], A fine structure generated by reflection formulas over primitive recursive arithmetic, Logic colloquium '78 (Boffa, M., van Dalen, D., and McAloon, K., editors), vol. 97, North-Holland, Amsterdam, pp. 335–350.Google Scholar
Shoenfield, J. R. [1959], On a restricted ω-rule, L'Académie Polonaise des Sciences. Bulletin. Série des Sciences Mathématiques, Astronomiques et Physiques, vol. 7, pp. 405–407.Google Scholar
Shoenfield, J. R. [1967], Mathematical logic, Addison-Wesley Publishing Co., Reading, MA., reprinted by the Association for Symbolic Logic, 2001.Google Scholar
Sundholm, G. [1983], Proof theory: A survey of the omega rule, Oxford D. Phil. dissertation.Google Scholar