Hostname: page-component-586b7cd67f-dsjbd Total loading time: 0 Render date: 2024-11-29T03:26:43.362Z Has data issue: false hasContentIssue false
  • English
  • Français

Hilbert's program and the omega-rule

Published online by Cambridge University Press:  12 March 2014

Aleksandar Ignjatović
Aleksandar Ignjatović*
Affiliation:
Department of Philosophy, Carnegie Mellon University, Pittsburgh, Pennsylvania 15213-3890, E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

In the first part of this paper we discuss some aspects of Detlefsen's attempt to save Hilbert's Program from the consequences of Gödel's Second Incompleteness Theorem. His arguments are based on his interpretation of the long standing and well-known controversy on what, exactly, finitistic means are. In his paper [1] Detlefsen takes the position that there is a form of the ω-rule which is a finitistically valid means of proof, sufficient to prove the consistency of elementary number theory Z. On the other hand, he claims that Z with its first-order logic is not strong enough to allow a formalization of such an ω-rule. This would explain why the unprovability of Con(Z) in Z does not imply that the consistency of Z cannot be proved by finitistic means. We show that Detlefsen's proposal is unacceptable as originally formulated in [1], but that a reasonable modification of the rule he suggest leads to a partial program already studied for many years. We investigate the scope of such a program in terms of proof-theoretic reducibilities. We also show that this partial program encompasses mathematically important theories studied in the “Reverse Mathematics” program. In order to investigate the provability with such a modified rule, we define new consistency and provability predicates which are weaker than the usual ones. We then investigate their properties, including a few that have no apparent philosophical significance but compare interestingly with the properties of the program based on the iteration of our ω-rule. We determine some of the limitations of such programs, pointing out that these limitations partly explain why partial programs that have been successfully carried out use quite different and substantially more radical extensions of finitistic methods with more general forms of restricted reasoning.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 59 , Issue 1 , March 1994 , pp. 322 - 343
Copyright
Copyright © Association for Symbolic Logic 1994

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]Detlefsen, M., On interpreting Gödel's second theorem, Journal of Philosphieal Logic, vol. 8 (1979), pp. 297–313.Google Scholar
[2]Feferman, S., Transfinite recursive progressions of axiomatic theories, this Journal, vol. 27 (1962), pp. 259–316.Google Scholar
[3]Feferman, S., Introductory note to 1931c, Kurt Gödel: Collected works, vol. I (Feferman, S. editor-in-chief), Oxford University Press, London (1986).Google Scholar
[4]Feferman, S., Hilbert's program relativized: proof-theoretical and foundational reductions, this Journal, vol. 53 (1988), pp. 354–384.Google Scholar
[5]Feferman, S. and Spector, C., Incompleteness along paths in progressions of theories, this Journal, vol. 27 (1962), pp. 383–390.Google Scholar
[6]Friedman, H., Systems of second-order arithmetic with restricted induction. I, II, this Journal, vol. 41 (1976), pp. 557–559 (Abstracts).Google Scholar
[7]Friedman, H., Simpson, S. G., and Smith, R. L., Countable algebra and set existence axioms, Annals of Pure and Applied Logic, vol. 25 (1983), pp. 141–181; addendum, vol. 28 (1985), pp. 319-320.CrossRefGoogle Scholar
[8]Herbrand, Jacques, Logical Writings, (Goldfarb, W., editor), Harvard University Press, Cambridge, Massachusetts, 1971, pp. 288–289.CrossRefGoogle Scholar
[9]Harrington, L., private communication to H. Friedman.Google Scholar
[10]Hilbert, D., Über das Unendliche, Mathematische Annalen, vol. 95; English translation, Philosophy of mathematics, selected readings, (P. Benacerrof and H. Putnam, editors), Cambridge University Press, London, (1983), pp. 161–190.Google Scholar
[11]Hilbert, David, Die Grundlegung der elementaren Zahlenlehre, Mathematische Annalen, vol. 104 (1931), pp. 485–494.CrossRefGoogle Scholar
[12]Ignjatović, A., Hilbert's program and the omega-rule, unpublished manuscript, 12 1988.Google Scholar
[13]Ignjatović, A., Fragments of first- and second-order arithmetic and length of proofs, Ph.D. Thesis, University of California at Berkeley, Berkeley, California (1990).Google Scholar
[14]Rosser, B., Gödel theorems for nonconstructive logics, this Journal, vol. 2 (1937), pp. 129–137.Google Scholar
[15]Schmerl, U., Iterated reflection principles and the ω-rule, this Journal, vol. 47 (1982), pp. 721–733.Google Scholar
[16]Shoenfield, J. R., On a restricted ω-rule, Bulletin De L'Academie Polonaise Des Sciences, vol. VII, No. 7, 1959, pp. 405–407.Google Scholar
[17]Simpson, S. G., Which set existence axioms are needed to prove the Cauchy-Peano theorem for ordinary differential equations?, this Journal, vol. 49 (1984), pp. 783–802.Google Scholar
[18]Simpson, S. G., Partial realization of Hilbert's program, this Journal, vol. 53 (1988), pp. 349–363.Google Scholar
[19]Simpson, S. G., Subsystems of second-order arithmetic (in preparation).Google Scholar
[20]Sieg, W., Foundations for analysis and proof theory, Synthese, vol. 60 (1984), pp. 159–200.CrossRefGoogle Scholar
[21]Sieg, W., Fragments of arithmetic, Annals of Pure and Applied Logic, vol. 28 (1985), pp. 33–71.CrossRefGoogle Scholar
[22]Sieg, W., Hilbert's program sixty years later, this Journal, vol. 53 (1988), pp. 338–348.Google Scholar
[23]Sieg, W., Relative consistency and accessible domains, Synthese, vol. 84 (1990), pp. 259–297.CrossRefGoogle Scholar
[24]Smorynski, C., The incompleteness theorems, Handbook of mathematical logic (Barwise, J., editor), North-Holland, Amsterdam (1977), pp. 821–895.CrossRefGoogle Scholar
[25]Tait, W. W., Finitism, Journal of Philosophy, vol. 78 (1981), pp. 524–546.CrossRefGoogle Scholar