On the scheme of induction for bounded arithmetic formulas
type: Item
instance of: scholarly article
title: On the scheme of induction for bounded arithmetic formulas
zbMATH Open document ID: 0647.03046
DOI: 10.1016/0168-0072(87)90066-2
author: A. J. Wilkie
author: Jeff Paris
published in: Annals of Pure and Applied Logic
publication date: 1987-01-01T00:00:00Z
review text: This work constitutes, in my opinion, a fundamental paper in the metamathematics of weak systems of arithmetic. What the authors do for fragments of arithmetic is, in a sense, similar to what \textit{S. Feferman} did for strong systems like PA in the paper ``Arithmetization of metamathematics in a general setting'' [Fundam. Math. 49, 35-92 (1960; Zbl 0095.243)]. The method used here is, however, model-theoretic where Feferman's results have been proved syntactically. A rather weak theory in which there is a good arithmetization of the syntax is \(I\Delta_ 0+Exp\). The authors, however, work in a weaker system where Exp is replaced by the weaker statement \(\Omega_ 1\equiv \forall x\exists y\) \([y=x^{| x|}]\) (here \(| x|\) denotes the length of the binary expansion of x); in these systems, one can carry out a sufficient part of arithmetization of syntax: even if one cannot prove the principle \(\phi\) (x)\(\to \Pr ov\ulcorner \phi \dot x\urcorner\) for \(\phi x\in \Delta_ 0\), one can prove this principle for a subclass of \(\Delta_ 0\) formulas; there is sufficient to prove the principle Prov\(\ulcorner \phi \urcorner \to \Pr ov\ulcorner \Pr ov\ulcorner \phi \urcorner \urcorner\) and, therefore, Gödel's second incompleteness theorem. A lot of results about relative consistency or unprovability of consistency statements are proved, namely: 1) \(I\Delta_ 0+\Omega_ 1\vdash Con(I\Delta_ 0)\to Con(I\Delta_ 0+\Omega_ n)\) (where \(\Omega_ n\) states the totality of the iterated exponentiation exp(x,\(| x|,...,|...| x|...|_{n\quad times}).\) 2) \(I\Delta_ 0+\Omega_ n\nvdash Con(I\Delta_ 0)\). This is strengthened by the following: \(I\Delta_ 0+\exp \nvdash Con Q\) where Q is Robinson's arithmetic. 3) \(I\Delta_ 0+\exp \nvdash Con(I\Delta_ 0)\to Con(I\Delta_ 0+\exp).\) 4) If \(\phi\) \(x\in R\) \(+\), then \(I\Delta_ 0+\exp \vdash \forall x \neg \phi x\) iff \(I\Delta_ 0+\Omega_ 1+Con(I\Delta_ 0,k)\vdash \forall x \neg \phi x\) (here R \(+\) is a suitable subclass of \(\D…
Mathematics Subject Classification ID: 03F30
zbMATH DE Number: 4055606
zbMATH Keywords: metamathematics of weak systems of arithmetic
zbMATH Keywords: fragments of arithmetic
zbMATH Keywords: relative consistency
zbMATH Keywords: unprovability of consistency
MaRDI profile type: Publication
full work available at URL: 0168-0072(87)90066-2
OpenAlex ID: W2011612028
cites work: Overspill and fragments of arithmetic
cites work: A note on the undefinability of cuts
cites work: Q3962995
cites work: Existence and feasibility in arithmetic
cites work: Q3964542
cites work: Q3895478
cites work: Q3941393
description: scientific article; zbMATH DE number 4055606