Passive induction and a solution to a Paris-Wilkie open question
type: Item
instance of: scholarly article
title: Passive induction and a solution to a Paris-Wilkie open question
zbMATH Open document ID: 1115.03083
author: Dan E. Willard
published in: Annals of Pure and Applied Logic
publication date: 2007-05-23T00:00:00Z
review text: The paper is devoted to the question formulated in 1981 by \textit{J. Paris} and \textit{A. Wilkie} in the paper ``\(\Delta_{0}\) sets and induction'' [Jadwisin Conf. Proc. 237--248 (1981)]: whether and to what extent the axiom system I\(\Sigma_{0}\) does satisfy the Second Incompleteness Theorem under Semantic Tableaux deduction. In the paper ``How to extend the semantic tableaux and cut-free versions of the second incompleteness theorem almost to Robinson's arithmetic Q'' [J. Symb. Log. 67, 465--496 (2002; Zbl 1004.03050)], the author showed that the semantic tableaux version of the Second Incompleteness Theorem does generalize for the most common definition of I\(\Sigma_{0}\) appearing in standard textbooks. In the paper under review it is shown that the incompleteness results of the mentioned paper can be generalized in the context of an alternate definition of the axiom system I\(\Sigma_{0}\) given also in the paper by Paris and Wilkie [loc. cit.]. Further, a formal analysis using a new technique called Passive Induction is developed. It is simpler than the formalism used by the author earlier in the paper from 2002.
Mathematics Subject Classification ID: 03F30
zbMATH DE Number: 5156495
zbMATH Keywords: incompleteness theorem
zbMATH Keywords: semantic tableaux
zbMATH Keywords: Herbrand deduction
reviewed by: Roman Murawski
MaRDI profile type: Publication
full work available at URL: j.apal.2007.01.003
OpenAlex ID: W1996215903
cites work: Herbrand consistency and bounded arithmetic
cites work: Existentially closed structures and Gödel's second incompleteness theorem
cites work: Q4339021
cites work: On Herbrand consistency in weak arithmetic
cites work: Derivability conditions on Rosser's provability predicates
cites work: Gödel's Second incompleteness theorem for Q
cites work: Q3794177
cites work: Unprovability of consistency statements in fragments of bounded arithmetic
cites work: Arithmetization of metamathematics in a general setting
cites work: Q4863622
cites work: Q4001935
cites work: On the Herbrand notion of consistency for finitely axiomatizable fragments of bounded arithmetic theories
cites work: A note on proofs of falsehood
cites work: Q4856172
cites work: Solution of a problem of Leon Henkin
cites work: Q4229041
cites work: Q4726219
cites work: A note on the undefinability of cuts
cites work: Q3755452
cites work: Cuts, consistency statements and interpretations
cites work: Q4885911
cites work: Q5560258
cites work: Proof theory. 2nd ed
cites work: Gödel sentences of bounded arithmetic
cites work: Undecidable theories
cites work: An inside view of EXP; or, The closed fragment of the provability logic of IΔ0 + Ω1 with a prepositional constant for EXP
cites work: The unprovability of small inconsistency. A study of local and global interpretability
cites work: Faith \& falsity
cites work: On the scheme of induction for bounded arithmetic formulas
cites work: Q2721211
cites work: Self-verifying axiom systems, the incompleteness theorem and related reflection principles
cites work: How to extend the semantic tableaux and cut-free versions of the second incompleteness theorem almost to Robinson's arithmetic q
cites work: Q3367334
cites work: An exploration of the partial respects in which an axiom system recognizing solely addition as a total function can verify its own consistency
cites work: On the available partial respects in which an axiomatization for real valued arithmetic can recognize its consistency
cites work: A generalization of the second incompleteness theorem and some exceptions to it
cites work: The Axiom System IΣ0 Manages to Simultaneously Obey and Evade the Herbrandized Version of the Second Incompleteness Theorem
DOI: 10.1016/J.APAL.2007.01.003
Recommended article: On axiom schemes for \(T\)-provably \(\Delta_1\) formulas
Recommended article: Q3567855
Recommended article: How to extend the semantic tableaux and cut-free versions of the second incompleteness theorem almost to Robinson's arithmetic q
Recommended article: Q3705449
Recommended article: The Axiom System IΣ0 Manages to Simultaneously Obey and Evade the Herbrandized Version of the Second Incompleteness Theorem
Recommended article: Q3434484
Recommended article: \(\Delta_ 0\)-complexity of the relation \(y= \prod_{i\leq n} F(i)\)
Recommended article: Bounded Induction and Satisfaction Classes
Recommended article: Q3367516
Recommended article: Set-theoretic reflection is equivalent to induction over well-founded classes
description: scientific article; zbMATH DE number 5156495