Infinite statements from finite axioms

139 Views Asked by At

I want to know if a given finite subset of axioms of PA1 ( 1st order peano arithmetic ) can prove infinite sentences in PA1 such that those proofs need no other axioms except those in the given finite set ?
edit- from infinite sentences, i mean ' infinite number of sentences ' and not sentences of infinite length.

Since PA1 can prove the consistency of every given finite set of its axioms, so I think there should be only finite statements provable from a given finite set of axioms in PA1.

Also, for a given finite set of axioms of PA1, can PA1 itself prove that there are only finite number of statements provable from them ?

1

There are 1 best solutions below

5
On BEST ANSWER

The answer is yes. Even ignoring silly examples like $$0=0, \quad 0=0\wedge 0=0,\quad (0=0\wedge 0=0)\wedge 0=0,\quad ...,$$ this can be done. A tiny fragment of $\mathsf{}$, for example, is all that's needed to prove each of the following statements: "2 is prime," "3 is prime," "5 is prime," etc. Moreover, $\mathsf{PA}$ proves that for each prime $p$, the theory $I\Sigma_1$ (a particular finite subtheory of $\mathsf{PA}$) proves "$p$ is prime."

In fact, $\mathsf{PA}$ proves that $I\Sigma_1$ is $\Sigma_1$-complete, so that the $\Pi_1$-incompleteness established by Godel's incompleteness theorem is optimal in terms of complexity.