[Proof Complexity] paper

Emil Jerabek jerabek at math.cas.cz
Tue Apr 26 18:54:09 CEST 2016

Dear colleagues,

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

Best regards,
Emil Jerabek

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.

More information about the Proof-Complexity mailing list