Htykuut

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) = (xast 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.

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+6cdot 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).