Division by zero (Q335000): Difference between revisions

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.