[Proof Complexity] paper

[Emil Jerabek]

Dear colleagues,

A new paper, "Division by zero", is available on my web page http://math.cas.cz/~jerabek/

Best regards,
Emil Jerabek


Abstract:
As a consequence of the MRDP theorem, the set of Diophantine equations
provably unsolvable in any sufficiently strong theory of arithmetic is
algorithmically undecidable. In contrast, we show the 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.