Hostname: page-component-586b7cd67f-rcrh6 Total loading time: 0 Render date: 2024-11-22T06:32:12.018Z Has data issue: false hasContentIssue false
  • English
  • Français

On the available partial respects in which an axiomatization for real valued arithmetic can recognize its consistency

Published online by Cambridge University Press:  12 March 2014

Dan E. Willard
Dan E. Willard*
Affiliation:
Departments of Computer Science and Mathematics, University of Albany, Albany, NY 12222, USA, E-mail: [email protected], URL: http://www.cs.albany.edu/~dew
Get access Rights & Permissions [Opens in a new window]

Abstract

Gödel's Second Incompleteness Theorem states axiom systems of sufficient strength are unable to verify their own consistency. We will show that axiomatizations for a computer's floating point arithmetic can recognize their cut-free consistency in a stronger respect than is feasible under integer arithmetics. This paper will include both new generalizations of the Second Incompleteness Theorem and techniques for evading it.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 71 , Issue 4 , December 2006 , pp. 1189 - 1199
Copyright
Copyright © Association for Symbolic Logic 2006

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]Adamowicz, Z., Herbrand consistency and bounded arithmetic, Fundamenta Mathematicae, vol. 171 (2002), pp. 279–292.CrossRefGoogle Scholar
[2]Adamowicz, Z. and Zbierski, P., On Herbrand consistency in weak theories, Archive for Mathematical Logic, vol. 40 (2001), pp. 399–413.CrossRefGoogle Scholar
[3]Atkinson, K., Elementary numerical analysis, Wiley Press, 1993.Google Scholar
[4]Bennett, J., On spectra, Ph.D. thesis, Princeton University, 1962.Google Scholar
[5]Bezboruah, A. and Shepherdson, J. C., Gödel's second incompleteness theorem for Q, this Journal, vol. 41 (1976), pp. 503–512.Google Scholar
[6]Burden, R. and Faires, J., Numerical methods, Brookes-Cole, 2003.Google Scholar
[7]Gödel, K., Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme, Monatshefte für Mathematik und Physik, vol. 38 (1931), pp. 173–198.CrossRefGoogle Scholar
[8]Hájek, P. and Pudlák, P., Metamathematics of first order arithmetic, Springer Verlag, 1991.Google Scholar
[9]Kleene, S. C., On the notation of ordinal numbers, this Journal, vol. 3 (1938), pp. 150–156.Google Scholar
[10]Nelson, E., Predicative arithmetic, Princeton Math Notes Press, 1986.CrossRefGoogle Scholar
[11]Paris, J. B. and Dimitracopoulos, C., Truth definitions for Δ0 formulae, Logic and algorithmic, Monographic de L'Enseignement Mathematique, vol. 30, 1982, pp. 317–329.Google Scholar
[12]Paris, J. B. and Dimitracopoulos, C., A note on the undefinability of cuts, this Journal, vol. 48 (1983), pp. 564–569.Google Scholar
[13]Pudlák, P., Cuts, consistency statements and interpretations, this Journal, vol. 50(1985), pp. 423–442.Google Scholar
[14]Pudlák, P., On the lengths of proofs of consistency, Collegium Logicum: Annals of the Kurt Goedel Society, vol. 2 (1996), pp. 65–86, Springer-Wien.CrossRefGoogle Scholar
[15]Solovay, R. M., Several telephone conversations (during 1994) discussing how to modify Theorem 2.3 from Pudlák's article [13] with the methods of Nelson, and Wilki-Paris [10, 16]. (The Appendix A of [17] offers a 4-page interpretation of the underlying idea behind Solovay's unpublished observation.).Google Scholar
[16]Wilkie, A. J. and Paris, J. B., On the scheme of induction for bounded arithmetic, Annals on Pure and Applied Logic, vol. 35 (1987), pp. 261–302.CrossRefGoogle Scholar
[17]Willard, D., Self-verifying systems, the incompleteness theorem and the tangibility reflection principle, this Journal, vol. 66 (2001), pp. 536–596.Google Scholar
[18]Willard, D., How to extend the semantic tableaux and cut-free versions of the second incompleteness theorem almost to Robinson's arithmetic Q, this Journal, vol. 67 (2002), pp. 465–496.Google Scholar
[19]Willard, D., A version of the second incompleteness theorem for axiom systems that recognize addition as a total function, First order logic revisited (Hendricks, V.et.al., editor), Logos Verlag, 2004, pp. 337–368.Google Scholar
[20]Willard, D., An exploration of the partial respects in which an axiom system recognizing solely addition as a total function can verify its own consistency, this Journal, vol. 70 (2005), pp. 1171–1209.Google Scholar
[21]Willard, D., A new variant of Hilbert styled generalization of the second incompleteness theorem and some exceptions to it, Annals on Pure and Applied Logic, vol. 141 (2006), pp. 472–496.CrossRefGoogle Scholar
[22]Wrathall, C., Rudimentary predicates and relative computation, Siam Journal on Computing, vol. 7 (1978), pp. 194–209.CrossRefGoogle Scholar