Skip Navigation



Journal of Logic and Computation Advance Access published online on August 12, 2009
Journal of Logic and Computation, doi:10.1093/logcom/exp048
This Article
Right arrow Abstract Freely available
Right arrow Full Text (PDF)
Right arrow Alert me when this article is cited
Right arrow Alert me if a correction is posted
Services
Right arrow Email this article to a friend
Right arrow Similar articles in this journal
Right arrow Alert me to new issues of the journal
Right arrow Add to My Personal Archive
Right arrow Download to citation manager
Right arrowRequest Permissions
Google Scholar
Right arrow Articles by Visser, A.
Social Bookmarking
Add to CiteULike   Add to Connotea   Add to Del.icio.us  
What's this?

© The Author, 2009. Published by Oxford University Press. All rights reserved. For Permissions, please email: journals.permissions@oxfordjournals.org

Original Papers

Can we make the Second Incompleteness Theorem Coordinate Free?

Albert Visser

Department of Philosophy, Utrecht University, Heidelberglaan 8, 3584 CS Utrecht, The Netherlands.
E-mail: albert.visser{at}phil.uu.nl

Received 9 August 2008.

Is it possible to give a coordinate-free formulation of the Second Incompleteness Theorem? We pursue one possible approach to this question. We show that (i) cutfree consistency for finitely axiomatized theories can be uniquely characterized modulo EA-provable equivalence and (ii) consistency for finitely axiomatized sequential theories can be uniquely characterized modulo EA-provable equivalence. The case of infinitely axiomatized RE theories is more delicate. We carefully discuss this in the article.

Keywords: Second Incompleteness Theorem; interpretability



References

  1. Beklemishev LD. Induction rules, reflection principles, and provably recursive functions. Annals of Pure and Applied Logic (1997) 85:193–242.[CrossRef][Web of Science]
  2. Buss S. Bounded Arithmetic (1986) Bibliopolis.
  3. Cégielski P, Richard D. Decidability of the natural integers equipped with the Cantor pairing function and successor. Theoretical Computer Science (2001) 257:51–77.[CrossRef][Web of Science]
  4. Feferman S. Arithmetization of metamathematics in a general setting. Fundamenta Mathematicae (1960) 49:35–92.
  5. Ferrante J, Rackoff CW. The Computational Complexity of Logical Theories (1979) Springer. Vol. 718 of Lecture Notes in Mathematics.
  6. Hájek P, Pudlák P. Metamathematics of First-Order Arithmetic. Perspectives in Mathematical Logic (1991) Springer.
  7. Kalsbeek MB. An orey sentence for predicative arithmetic. In: Technical Report X-89-01 (1989) ITLI, University of Amsterdam.
  8. Kreisel G, Lévy A. Reflection principles and their use for establishing the complexity of axiomatic systems. Zeitschrift für Mathematische Logik und Grundlagen der Mathematik (1968) 14:97–142.[CrossRef][Web of Science]
  9. Mycielski J, Pudlák P, Stern AS. A Lattice of Chapters of Mathematics (Interpretations between Theorems) (1990) AMS, Providence. Vol. 426 of Memoirs of the American Mathematical Society.
  10. Pudlák P. Some prime elements in the lattice of interpretability types. Transactions of the American Mathematical Society (1983) 280:255–275.[CrossRef][Web of Science]
  11. Pudlák P. Cuts, consistency statements and interpretations. The Journal of Symbolic Logic (1985) 50:423–441.[CrossRef]
  12. Smorynski C. Nonstandard models and related developments. In: Harvey Friedman's Research on the Foundations of Mathematics—Harrington LA, Morley MD, Scedrov A, Simpson SG, eds. (1985) North Holland. 179–229.
  13. Svejdar V. An interpretation of Robinson's Arithmetic in Grzegorczyk's weaker variant. Fundamenta Informaticae (2007) 81:347–354.[Web of Science]
  14. Tarski A, Mostowski A, Robinson RM. Undecidable Theories (1953) North–Holland.
  15. Tenney RL. Decidable pairing functions, unpublished.
  16. Vaught RA. Axiomatizability by a schema. The Journal of Symbolic Logic (1967) 32:473–479.[CrossRef]
  17. Visser A. An inside view of exp. The Journal of Symbolic Logic (1992) 57:131–165.[CrossRef]
  18. Visser A. The unprovability of small inconsistency. Archive for Mathematical Logic (1993) 32:275–298.[CrossRef][Web of Science]
  19. Visser A. Cardinal arithmetic in the style of Baron von Münchhausen. Review of Symbolic Logic (2009) 2. To appear.
  20. Visser A. Pairs, sets and sequences in first order theories. Archive for Mathematical Logic (2008) 47:299–326.[CrossRef][Web of Science]
  21. Visser A. The predicative Frege hierarchy. Annals of Pure and Applied Logic (2009) 160:129–153.[CrossRef]
  22. Wilkie A, Paris JB. On the scheme of of induction for bounded arithmetic formulas. Annals of Pure and Applied Logic (1987) 35:261–302.[CrossRef][Web of Science]

Add to CiteULike CiteULike   Add to Connotea Connotea   Add to Del.icio.us Del.icio.us    What's this?



This Article
Right arrow Abstract Freely available
Right arrow Full Text (PDF)
Right arrow Alert me when this article is cited
Right arrow Alert me if a correction is posted
Services
Right arrow Email this article to a friend
Right arrow Similar articles in this journal
Right arrow Alert me to new issues of the journal
Right arrow Add to My Personal Archive
Right arrow Download to citation manager
Right arrowRequest Permissions
Google Scholar
Right arrow Articles by Visser, A.
Social Bookmarking
Add to CiteULike   Add to Connotea   Add to Del.icio.us  
What's this?