Division by zero

DOI10.1007/S00153-016-0508-5MaRDI QIDQ335000zbMATH OpenOpenAlexFDO

Publication date 1 November 2016

Published in Archive for Mathematical Logic (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1604.07309

decidability Diophantine equation Robinson arithmetic universal theory

Complexity of computation (including implicit computational complexity) (03D15) First-order arithmetic and fragments (03F30) Nonstandard models of arithmetic (03H15)

Abstract: For any sufficiently strong theory of arithmetic, the set of Diophantine equations provably unsolvable in the theory is algorithmically undecidable, as a consequence of the MRDP theorem. In contrast, we show decidability of Diophantine equations provably unsolvable in Robinson's arithmetic Q. The argument hinges on an analysis of a particular class of equations, hitherto unexplored in Diophantine literature. We also axiomatize the universal fragment of Q in the process.

Review text

For an arithmetic theory \(T\), the Diophantine problem for \(T\), \(D_T\), is to algorithmically decide whether a given Diophantine equation has a solution in a model of \(T\). By classical results, \(D_T\) is unsolvable for all theories \(T\) extending \(I\Delta_0+\exp\) and, by a result of \textit{R. Kaye} [Ann. Pure Appl. Logic 61, No. 1--2, 63--73 (1993; Zbl 0790.03056)], for all theories extending parameter-free bounded universal induction. In the present paper, the author shows that the Diophantine problem is solvable for Robinson's arithmetic \(Q\). The proof involves an axiomatization of the universal consequences of \(Q\) and a reduction of \(D_Q\) to the decision problem for equations of a particularly simple type. The reduction uses a ``black-hole model of \(Q\). In a black-hole model, there is a nonstandard element \(\infty\), such that \(\infty +x=x+\infty=x\cdot \infty\) for all \(x\), \(\infty\cdot x= \infty\) for all \(x\neq 0\) and \(0\cdot\infty =\infty\) (justifying the title of the paper). Furthermore, it is shown that \(D_Q\) is NP-complete. The proof uses a result of \textit{K. L. Manders} and \textit{L. Adleman} [J. Comput. Syst. Sci. 16, 168--184 (1978; Zbl 0369.68030)], who have shown that the decision problem for solvability in natural numbers of \(x^2+ay-b=0\), for binary \(a\) and \(b\), is NP-complete.

Recommendations

Cites work

Cited in

(9)

Describes a project that uses

Uses Software

MathOverflow

This page was built for publication: Division by zero

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