proof of formula with Peano-axioms

Question

For all natural numbers n define $\Delta_n$ as:
$\Delta_0$ is the constant $0$ and $\Delta_{n+1}$ is $S(\Delta_n)$.
Here is S the function for the follower, i.e. $\forall x: S(x) = x+1$.

1)I want to show that if $i+j=n$, then $\Delta_i + \Delta_j = \Delta_n$ ist provable and I have to give an approximation of the length of the formal proof
2)and conclude that for all n the formula $(\Delta_n + \Delta_n) + \Delta_n$ = $\Delta_n + (\Delta_n + \Delta_n) =: \Psi(\Delta_n)$ is provable with only the axioms $\forall x(x+0=x)$ and $\forall x \forall y (x+S(y) = S(x+y))$ and $\Psi(0) \wedge \forall x (\Psi(x) \rightarrow \Psi(Sx)) \rightarrow \forall x(\Psi(x))$.

For 1), all the Peano-axioms may be used, that is:
N1) $\neg(x+1=0)$
N2) $x+1 = y+1 \rightarrow x=y$
A0) $0+1 = 1$
A1) $x+0=x$
A2) $x+(y+1) = (x+y)+1$
M1) $x \ast 0 = 0$
M2) $x \ast (y+1) = (x\ast y) + x$
E1) $x^0 = 1$
E2) $x^{y+1} = x^y \ast x$
O1) $x \leq 0 \leftrightarrow x = 0$
O2) $x \leq y+1 \leftrightarrow (x \leq y \vee x = y +1)$
$IND_A$) $[A(0) \wedge \forall x [A(x) \rightarrow A(x+1)]] \rightarrow [\forall z A(z)]$

I can't figure out how this proof should work and even don't know how and where to start, so I'd appreciate any help on it.

Answer 1

For 1:

Use induction over $j$ that for all $i$ and $j$ where $i+j=n$: $\Delta_i + \Delta_j = \Delta_n$ is provable

Base: $j=0$

So, we need to show that for all $i$: $\Delta_i + \Delta_0 = \Delta_i$ is provable

Well, since $\Delta_0 = 0$, that means we have to show that for all $i$: $\Delta_i + 0 = \Delta_i$ is provable. But for any $i$, that is an immediate instantiation of Axiom $A1$

Step: Let $k$ be some arbitrary number. Suppose that for any $i$ where $i+k=n$: $\Delta_i + \Delta_k = \Delta_n$ is provable.

So now we have to show that for any $i$ where $i+(k+1)=n$: $\Delta_i + \Delta_{k+1} = \Delta_n$ is provable.

Well, start a proof by instantiating $A2$ as follows:

$(1) \Delta_i + (\Delta_k + 1) = (\Delta_i + \Delta_k) +1$

Also instantiate the $\forall x: S(x) = x+1$ with:

$(2) S(\Delta_k) = \Delta_k + 1$

So, we can substitute (using $= \ Elim$) (2) into (1) and get:

$(3) \Delta_i + S(\Delta_k) = (\Delta_i + \Delta_k) +1$

But by definition the term $\Delta_{k+1}$ is just the same term as $S(\Delta_k)$, so right there we have:

$(3) \Delta_i + \Delta_{k+1} = (\Delta_i + \Delta_k) +1$

Now instantiate the $\forall x: S(x) = x+1$ with:

$(4) S(\Delta_i + \Delta_k) = (\Delta_i + \Delta_k) + 1$

and substitute (4) into (3):

$(5) \Delta_i + \Delta_{k+1} = S(\Delta_i + \Delta_k)$

Now, given that $i + (k+1) = n$, that means it is true that $i + k = n-1$, and thus by the inductive hypothesis we can prove:

$(6) \Delta_i + \Delta_k = \Delta_{n-1}$

So, we can substitute (6) into (5) and thus prove that:

$(7) \Delta_i + \Delta_{k+1} = S(\Delta_{n-1})$

But $S(\Delta_{n-1})$ is by definition the same term as $\Delta_n$ and so we have:

$(7) \Delta_i + \Delta_{k+1} = \Delta_n$

as desired.

Now, how many steps did this take? It takes $6$ steps, plus however many steps it takes to prove that $\Delta_i + \Delta_k = \Delta_{n-1}$. So, roughly, for each increase of $j$ by $1$, it takes an additional $6$ steps to prove $\Delta_i + \Delta_j = \Delta_n$. And give that it took exactly $1$ step to prove $\Delta_i + \Delta_0 = \Delta_i$, that means that it takes $1+6\cdot j$ steps to prove $\Delta_i + \Delta_j = \Delta_n$ for any $i$ and $j$ where $i + j = n$

OK, try and follow what I did here, and then try to do something similar for question 2).