How to use nonlogical axioms of Peano Arithmetic

Question

In studying the Incompleteness Theorems, there's an axiom that I'm trying to look into to extract a formula. Say that we are given $PA$ $\vdash$ $\forall x_1 \forall x_2 \forall x_3((x_1+x_2)+x_3=x_1+(x_2+x_3))$, find a formula which is needed to prove it in PA.

All help is greatly appreciated. Thanks for looking!

Answer 1

In order to prove :

$∀x_1 \ ∀x_2 \ ∀x_3 \ ((x_1+x_2)+x_3=x_1+(x_2+x_3))$

we have to use induction on $x_3$, i.e. to use as $P(n)$ the formula:

$∀x_1 \ ∀x_2 \ ((x_1+x_2)+n=x_1+(x_2+n))$.

The suitable instance of the axiom schema will be:

$(P(0) \land \forall n \ (P(n) \to P(sn))) \to \forall n \ P(n)$.

Base step :

We can use : $b+0=b$ and by subst for equality: $a+(b+0)=a+b$.

Then $a+(b+0)=(a+b)+0$ and re-arranging it by properties of equality.

Finally, we have to "generalize" it to get :

$P(0)$.

Answer 2

Here is a small issue you need to address:

You are asked to prove $PA \vdash \forall x_1 \forall x_2 \forall x_3((x_1+x_2)+x_3=x_1+(x_2+x_3))$ by induction on $x_3$

However, if you choose to use the induction scheme using $P(x_3,x_1,x_2) = \forall x_1 \forall x_2((x_1+x_2)+x_3=x_1+(x_2+x_3))$

then you'll end up with:

$\forall x_3 \forall x_1 \forall x_2 ((x_1+x_2)+x_3=x_1+(x_2+x_3))$

i.e. the quantifiers are not in the right place.

So, what to do? You can do two things:

• You can indeed just prove $\forall x_3 \forall x_1 \forall x_2 ((x_1+x_2)+x_3=x_1+(x_2+x_3))$, and then do a fairly little proof after that to swap the quantifiers:

$\forall x_3 \forall x_1 \forall x_2 ((x_1+x_2)+x_3=x_1+(x_2+x_3))$

$\quad a,b,c$ (that is, start a univeral proof by assuming $a,b,c$ to be arbitrary objects)

$\quad ((a+b)+c=a+(b+c))$ ($\forall \: Elim$)

$\forall x_1 \forall x_2 \forall x_3 ((x_1+x_2)+x_3=x_1+(x_2+x_3))$ ($\forall \: Intro$)

• You can start a universal proof for $x_1$ and $x_2$, and do the inductive step inside that universal proof:

$\quad a,b$ (that is, start a univeral proof by assuming $a,b$ to be arbitrary objects)

Use inductive scheme with:

$P(x_3) = ((a+b)+x_3=a+(b+x_3))$

to prove:

$\forall x_3 ((a+b)+x_3=a+(b+x_3))$

And complete the universal proof:

$\forall x_1 \forall x_2 \forall x_3 ((x_1+x_2)+x_3=x_1+(x_2+x_3))$ ($\forall \: Intro$)