Hilbert's tenth problem for weak theories of arithmetic

DOI10.1016/0168-0072(93)90198-MMaRDI QIDQ685070zbMATH OpenFDO

Authors Richard Kaye

Publication date 22 September 1993

Published in Annals of Pure and Applied Logic (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0168-0072(93)90198-M

zbMATH Keywords

bounded existential inductionHilbert's tenth problemparameter- free bounded universal inductionweak theories of arithmetic

Mathematics Subject Classification ID

Decidability of theories and sets of sentences (03B25) First-order arithmetic and fragments (03F30)

Review text

Hilbert's tenth problem for a theory \(T\) asks if there is an algorithm which decides for a given polynomial \(p(x)\) from \(\mathbb{Z}[x]\) whether \(p(x)\) has a root in some model of \(T\). The author examines some of the model-theoretic consequences that an affirmative answer would have in cases such as \(T=\) Open Induction and others, and applies these methods by providing a negative answer in the cases when \(T\) is some particular finite fragment of the weak theories \(IE_ 1\) (bounded existential induction) or \(IU^ -_ 1\) (parameter-free bounded universal induction).

Recommendations

• Undecidability in number theory
• scientific article; zbMATH DE number 1261118
• scientific article; zbMATH DE number 1531933
• Hilbert's tenth problem for fixed d and n
• Hilbert's Tenth Problem over number fields, a survey

Cites work

• Bounded existential induction
• Diophantine induction
• scientific article; zbMATH DE number 3702663 (Why is no real title available?)
• scientific article; zbMATH DE number 3710174 (Why is no real title available?)
• scientific article; zbMATH DE number 3784875 (Why is no real title available?)
• scientific article; zbMATH DE number 51556 (Why is no real title available?)
• scientific article; zbMATH DE number 3214534 (Why is no real title available?)
• scientific article; zbMATH DE number 3248030 (Why is no real title available?)
• scientific article; zbMATH DE number 3336816 (Why is no real title available?)
• On Diophantine equations solvable in models of open induction
• Parameter-Free Universal Induction
• Representability of recursively enumerable sets in formal theories
• Which Curves Over Z have Points with Coordinates in a Discrete Ordered Ring?

Cited in

(6)

• On the bounded version of Hilbert's tenth problem
• Hilbert's Second Problem (the consistency of arithmetic)
• Division by zero
• Nonstandard Models for a Fragment of the Arithmetic and Their Decision Problem
• Restricted polynomial induction versus parameter free ordinary induction
• scientific article; zbMATH DE number 7566048 (Why is no real title available?)

This page was built for publication: Hilbert's tenth problem for weak theories of arithmetic

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q685070)