FOM: Syntactic vs semantic classification of math statements

Martin Davis martind at cs.berkeley.edu
Fri Apr 17 22:08:47 EDT 1998


At 05:03 PM 4/17/98 -0400, JOE SHIPMAN wrote:

>like your opinion on the following: 1)Are any important open problems
outside of
>logic, fom, and set theory not equivalent to statements of 2nd-order
arithmetic?
> 2) What important problems require more than 2 quantifiers in 2nd-order arith-
>metic? More than 3? 3) What important (1st-order) arithmetical problem
needs the
>most quantifiers? 4) What's the most important unsolved pi_0_0 problem? -- Joe
>

Just wanted to remark that whereas the twin prime conjecture is evidently
Pi^0_2, there are Pi^0_1 statements believed (on probabilistic grounds) to
be true that imply it. [Martin Davis, Yuri Matijasevic and Julia Robinson,
"Hilbert's Tenth Problem: Diophantine Equations: Positive Aspects of a
Negative Solution,"
Proceedings of Symposia in Pure Mathematics, vol.28(1976), pp. 323-378.]

Martin




More information about the FOM mailing list