FOM: Correction on Diophantine Polynomials etc.

[JOE SHIPMAN, BLOOMBERG/ SKILLMAN]

Oops!  Thanks for the clarification, Martin!  I knew that degree and number of
variables could be bounded simultaneously, and remembered Jones's "Universal
Diophantine Equation", but forgot that one of the exponents was huge, and
temporarily did not have my copy of Matiyasevich's book at my desk as I usually
do so didn't check.  So you can only get logical simplicity (a small number of
terms) for exponential diophantine equations, not for pure diophantine
equations.  Does this still suffice to make Franzen's point?  To formulate
theorems about trees and insertion rules in arithmetic with only + and * is
also very cumbersome and if you allow exponentiation to get easy coding of
finite sets you must also allow it for the diophantine equations.  Here the
coding needed to represent ZFC-provability by a diophantine equation is still
quite large compared to the Godel-type coding needed to represent exponentiation
(though with the advantage that there are no quantifier alternations).  So on
the grounds of intelligibility Friedman's statement wins, but the situation
with numerical or information-theoretic complexity is less clear. -- Joe Shipman