Subsystems of Peano arithmetic and incompleteness theorem - MathOverflow

Subsystems of Peano arithmetic and incompleteness theorem

2011-02-13T12:43:05Z

I think everyone is familiar with Goedel's incompleteness theorems. In particular they imply that PA (Peano arithmetic) can not prove its own consistency. Now my question is what is the largest subsystem of PA that "can" prove its own consistency? You definitely can't have the induction axiom but is that enough?

Answer by none for Subsystems of Peano arithmetic and incompleteness theorem

2011-02-13T12:59:00Z

See refs at: http://en.wikipedia.org/wiki/Self-verifying_theories

Answer by PA for Subsystems of Peano arithmetic and incompleteness theorem

2011-06-18T08:31:52Z

This answers to this question may be of use - http://mathoverflow.net/questions/65626/can-any-formal-system-prove-its-own-consistency

In short, it states that $PA$ is too strong to prove its own consistency, Presburger arithmetic (see Neel Krishnaswami's answer in the link) is too weak (although it is consistent). Other sub-systems like $I\Sigma_1$ can't prove their own consistency. $PA^-$ (PA without induction) I'm not sure about, but I wouldn't expect it to prove its own consistency.

But Paseman's comment is probably most accurate!

An inconsistent sub-system could, but I don't think that's what you're after... ;)

http://mathoverflow.net/questions/9864/presburger-arithmetic http://www.cs.albany.edu/~dew/m/jsl1.pdf http://en.wikipedia.org/wiki/Presburger_arithmetic

Answer by Emil Jeřábek for Subsystems of Peano arithmetic and incompleteness theorem

2011-06-18T11:48:41Z

As proved by Pudlák, Gödel's theorem holds in the strong form that no consistent r.e. extension of Robinson's arithmetic $Q$ can prove its own consistency. (Moreover, as shown by Paris and Wilkie, the consistency of $Q$ is not provable even in $I\Delta_0+\exp$.)

Answer by abo for Subsystems of Peano arithmetic and incompleteness theorem

2012-02-12T12:59:04Z

First, it's not clear whether you are talking about first-order PA or second-order PA. It seems, because you are mentioning induction as an axiom rather than a schema, that you are talking about second-order PA, but I will answer for a special form of first-order Peano Arithmetic, denoted PA1. The answer for PA2 is similar.

Secondly, it is incorrect to ask what is "the" largest. The answer to your question is: there exists sub-systems of PA which prove their own consistency but there is no largest such sub-system.

Let PA have the language with a constant 0, a one-place predicate N, and a 2-place predicate Sx,y. Usually the axioms of PA1 include axioms for addition and multiplication. I will present a system which has axioms for sequences rather than addition and multiplication; addition and multiplication can then be defined using the notion of sequences. The axioms of PA1 are:

(1) N0

(2) (n)(m)(Nn & Sn,m => Nm)

(3) (n)(Nn => (there exists m) Sn,m)

(4) (n)(m)(m')(Nn & Sn,m & Sn,m' => m = m')

(5) (n)(m)(n')(Nn & Nn' & Sn,m & Sn',m => n = n')

(6) (n)(Nn => not Sn,0)

(7) Induction schema, phi[0\n] & (n)(m)(Nn & Sn,m & phi => phi[m\n]) => (n)(Nn => phi)

(8) For every natural number x, there exists a sequence <(0,x)>

(9) For every sequence f, if Nn & Sn,m & <(m,x)> belongs to f, then <(n,y)> belongs to f for some y

(10) For every sequence f, if Nn & Nm & Ny & Sn,m & <(n,x)> belongs to f, there there exists a sequence g exactly like f except that it may differ at the mth place where <(m,y)> belongs to g

Apologies for the imprecision of (8), (9), and (10), but it's the quickest way for me to write them down here.

Call fpa the system made up of axioms (4) through (10). Then fpa proves its own consistency. It also proves the consistency of fpa + (1) (call this X). So a fortiori X proves its own consistency. fpa also proves the consistency of fpa + (N0 => (2) & (3)), so this latter (call it Y) also proves its own consistency. But any system stronger than both X and Y contains PA1, which can't prove its own consistency. Hence there is no strongest sub-system of PA1 which proves its own consistency.

Please see http://www.andrewboucher.com/papers/fpa.pdf for details.