Diophantine induction
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\).
- Bounded existential induction
- Existence and feasibility in arithmetic
- Existential Definability in Arithmetic
- scientific article; zbMATH DE number 4006252 (Why is no real title available?)
- scientific article; zbMATH DE number 3689386 (Why is no real title available?)
- scientific article; zbMATH DE number 3702663 (Why is no real title available?)
- scientific article; zbMATH DE number 3784875 (Why is no real title available?)
- scientific article; zbMATH DE number 3248030 (Why is no real title available?)
- On parameter free induction schemas
- On the complexity of models of arithmetic
- On the structure of models of bounded $E\sb 1$-induction
- Diophantine equations in fragments in arithmetic
- A direct method for simulating partial recursive functions by Diophantine equations
- Toward the limits of the Tennenbaum phenomenon
- Pell equations and exponentiation in fragments of arithmetic
- Algebraic combinatorics in bounded induction
- Induction rules in bounded arithmetic
- Elementary equivalence for Abelian-by-finite and nilpotent groups.
- Division by zero
- Pell Equations and Weak Regularity Principles
- On the structure of models of bounded $E\sb 1$-induction
- scientific article; zbMATH DE number 3931005 (Why is no real title available?)
- scientific article; zbMATH DE number 3961605 (Why is no real title available?)
- scientific article; zbMATH DE number 4027447 (Why is no real title available?)
- Bounded existential induction
- scientific article; zbMATH DE number 4075046 (Why is no real title available?)
- Solving Pell equations locally in models of IΔ0
- Restricted polynomial induction versus ordinary induction
- scientific article; zbMATH DE number 871422 (Why is no real title available?)
- Weak forms of the Regularity Principle in the presence of \documentclass{article}\usepackage{amssymb}\begin{document}\pagestyle{empty}$\bf {\mathsf {I}{\mathrm{E}}_1}$\end{document}
- Restricted polynomial induction versus parameter free ordinary induction
- A note on exponentiation
- Weak arithmetics
- Weak arithmetic
- A sharpened version of McAloon's theorem on initial segments of models of \(I\Delta_ 0\)
- Hilbert's tenth problem for weak theories of arithmetic
- A parameterized halting problem, _0 truth and the MRDP theorem
- The provably total functions of basic arithmetic and its extensions
- The lengths of proofs: Kreisel's conjecture and Gödel's speed-up theorem
This page was built for publication: Diophantine induction
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q584258)
