Completeness for pure arithmetical sentences?

34 Views Asked by At

Is it possible the define an effectively generated first order axiomatic system that is complete for pure arithmetical sentences defined in its language?

A pure arithmetical sentences is a sentence using the traditional arithmetical operators (including $\neq, <, > $) but that doesn't use any logical connective!

1

There are 1 best solutions below

4
On

In fact we can do much better: Robinson's $\mathsf{Q}$ proves every true $\Sigma^0_1$ sentence (this is called $\Sigma^0_1$-completeness - see the discussion here) and so a fortiori decides every quantifier-free sentence. It seems to me that your "purely arithmetical" sentences are in particular all quantifier-free, so this is more than enough.

If we try to go much beyond the quantifier-free sentences, however, things quickly break down: by the internal MRDP theorem (see Hajek/Pudlak section I.3(d)), no consistent computably axiomatizable extension of $I\Sigma_1$ can decide every sentence of the form "Such-and-such Diophantine equation has no solutions." Note that we don't even need any Booleans here - universally quantified equations are enough to be problematic.