Passive induction and a solution to a Paris–Wilkie open question

Annals of Pure and Applied Logic 146 (2-3):124-149 (2007)
  Copy   BIBTEX

Abstract

In 1981, Paris and Wilkie raised the open question about whether and to what extent the axiom system did satisfy the Second Incompleteness Theorem under Semantic Tableaux deduction. Our prior work showed that the semantic tableaux version of the Second Incompleteness Theorem did generalize for the most common definition of appearing in the standard textbooks.However, there was an alternate interesting definition of this axiom system in the Wilkie–Paris article in the Annals of Pure and Applied Logic 35 , pp. 261–302 which we did not examine in our year-2002 article in the Journal of Symbolic Logic. Our first goal is to show that the incompleteness results of our prior paper can generalize in this alternate context. We will also develop a formal analysis, using a new technique called Passive Induction, that is simpler than the formalism we had used before.A further reason our results are of interest is that we have shown in a companion paper published in Electronic Notes in Theoretical Computer Science 165 , pp. 213–226 that some very unorthodox axiomizations for are anti-thresholds for the Herbrandized version of the Second Incompleteness Theorem. Thus, different axiomizations for have nearly fully opposite incompleteness properties.This paper is self-contained. It will not require a knowledge of our earlier results

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 94,749

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles

Herbrand consistency of some arithmetical theories.Saeed Salehi - 2012 - Journal of Symbolic Logic 77 (3):807-827.
A Mathematical Commitment Without Computational Strength.Anton Freund - 2022 - Review of Symbolic Logic 15 (4):880-906.
Other Proofs of Old Results.Henryk Kotlarski - 1998 - Mathematical Logic Quarterly 44 (4):474-480.

Analytics

Added to PP
2013-12-30

Downloads
15 (#974,092)

6 months
1 (#1,748,431)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

Herbrand consistency of some arithmetical theories.Saeed Salehi - 2012 - Journal of Symbolic Logic 77 (3):807-827.
2007-2008 Winter Meeting of the Association for Symbolic Logic.Jeffrey Remmel - 2008 - Bulletin of Symbolic Logic 14 (3):402-411.

Add more citations

References found in this work

Solution of a problem of Leon Henkin.M. H. Löb - 1955 - Journal of Symbolic Logic 20 (2):115-118.
On the scheme of induction for bounded arithmetic formulas.A. J. Wilkie & J. B. Paris - 1987 - Annals of Pure and Applied Logic 35 (C):261-302.
Extensions of some theorems of gödel and church.Barkley Rosser - 1936 - Journal of Symbolic Logic 1 (3):87-91.
Cuts, consistency statements and interpretations.Pavel Pudlák - 1985 - Journal of Symbolic Logic 50 (2):423-441.

View all 23 references / Add more references