Diophantine induction
type: Item
instance of: scholarly article
title: Diophantine induction
zbMATH Open document ID: 0693.03038
DOI: 10.1016/0168-0072(90)90076-E
published in: Annals of Pure and Applied Logic
publication date: 1990-01-01T00:00:00Z
review text: Let \(I\exists^-_ 1\) be the subsystem of Peano arithmetic obtained by restricting the induction scheme to diophantine formulas without parameters. The main result of the paper says that \(I\exists^-_ 1\vdash IE^-_ 1+E\vdash\) Matijasevič's theorem, where \(IE^-_ 1\) is the scheme of parameter-free bounded existential induction and E is an \(\forall \exists\) axiom expressing the existence of a function of exponential growth. This answers the question of Z. Adamowicz if \(I\exists_ 1\) does prove Matijasevič's theorem. It is also connected with the problem: \(``I\Delta_ 0\vdash\) Matijasevič's theorem?'', which is still unsolved. The theorem is proved by means of a conservation result relating parameter and parameter-free induction schemes, which is of independent interest. The paper is concluded by some consequences of these results to the structure of countable nonstandard models of \(IE^-_ 1\).
reviewed by: Roman Murawski
Mathematics Subject Classification ID: 03F30
Mathematics Subject Classification ID: 03H15
zbMATH DE Number: 4134037
zbMATH Keywords: subsystem of Peano arithmetic
zbMATH Keywords: induction
zbMATH Keywords: diophantine formulas without parameters
zbMATH Keywords: Matijasevič's theorem
zbMATH Keywords: countable nonstandard models
author: Richard Kaye
MaRDI profile type: Publication
cites work: Q3757904
cites work: Q3962995
cites work: On parameter free induction schemas
cites work: On the complexity of models of arithmetic
cites work: On the structure of models of bounded $E\sb 1$-induction
cites work: Q3884109
cites work: Existence and feasibility in arithmetic
cites work: Existential Definability in Arithmetic
cites work: Q5534937
cites work: Bounded existential induction
cites work: Q3895478
full work available at URL: 0168-0072(90)90076-e
OpenAlex ID: W4212773215
description: scientific article; zbMATH DE number 4134037