2
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ I think you can use the induction axiom to show $\Delta_n=n$. $\endgroup$ – Richard Nov 24 '18 at 14:59
  • 1
    $\begingroup$ @Studentu In 2), you are trying to prove the formula for each specific $n$ (so that your previous comment about models seems irrelevant), you are not trying to prove $\forall n ...$. The point is that at this stage you cannot yet define in the language of PA the function that assigns to each $x$ the number $\Delta_x$. $\endgroup$ – Andrés E. Caicedo Nov 24 '18 at 15:12
  • 1
    $\begingroup$ @Studentu To make sense of $\Delta$ as a total function defined within PA you need to prove first some version of the recursion theorem. You can find some details in questions in this site (look for how to define exponentiation in Peano arithmetic). $\endgroup$ – Andrés E. Caicedo Nov 24 '18 at 15:56
  • 1
    $\begingroup$ @Studentu Yes, but that is not the point: 1) Peano arithmetic PA usually doesn't have an exponentiation symbol as part of its language. 2) In any case, the question I suggested to look for explains a general procedure to formalize within PA definitions by recursion. This is illustrated with exponentiation, but the procedure is meant to be used in many other situations. $\endgroup$ – Andrés E. Caicedo Nov 24 '18 at 17:17
  • 1
    $\begingroup$ Okay, better idea for your proof: I think 1) is possible using induction over $j$. 2) by proving commutativity via induction? $\endgroup$ – Richard Nov 24 '18 at 17:50
1
$\begingroup$

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).

$\endgroup$
  • $\begingroup$ Wow, thank you very much, Bram28! I understand every of your steps and the whole proof, but could you please explain how you figured out how each step had to look? For 2) I tried proving that $\forall x (\Psi(x) \rightarrow \Psi(Sx))$ since then we get with Modus Ponens and the induction axiom that $\forall x (\Psi(x))$ holds (since $\Psi(\Delta_0)$ is obvious.) But I didn't manage to prove this, though I think it should be quite easy to draw the conclusion. $\endgroup$ – Studentu Nov 26 '18 at 20:40
  • 1
    $\begingroup$ @Studentu Hmm, my first reaction was the same as Richard's: prove the commutative property of $+$ in general ... but the problem is that that would require a proper instance of the induction axiom, and they say that you can only use the induction axiom for this specific theorem. OK, so my second reaction is: you probably don't need the induction axiom at all! Because having shown 1), you now know that you can prove each of the statements $\Delta_n + \Delta_n = \Delta_{2n}$ , $\Delta_{2n} + \Delta_n = \Delta_{3n}$, and $\Delta_{n} + \Delta_{2n} = \Delta_{3n}$ for any $n$. That's enough! $\endgroup$ – Bram28 Nov 26 '18 at 20:57
  • $\begingroup$ Okay thanks! I've thought about this, too, but I thought it was wrong since it was so easy. But if you see it the same way, it's probably right. And now I guess we all interpreted the exercise wrong. The axioms with which we shall show that 2) is provable are exactly the ones we used for the prove of 1). And since from 1) we elegantly can conclude 2), to show 2) we need these 3 axioms (the induction axiom is the reason we are allowed to do a proof by induction for 1)). Do you think that's right? $\endgroup$ – Studentu Nov 26 '18 at 21:05
  • 1
    $\begingroup$ @Studentu Careful! Question 1) is asking you to prove that for any $i$ and $j$ you can prove the statement $\Delta_i + \Delta_j = \Delta_{i+j}$ ... there are infinitely many such statements, and using mathematical induction I showed they can all be proven. But I did not use the induction axiom to do this. That is, this inductive proof was a metaproof about what is provable, and I showed that all these statements were provable without using any induction axiom at all (look at the proof ... are any of the formal logic statements instances of the induction axiom? No.) $\endgroup$ – Bram28 Nov 26 '18 at 22:54
  • 1
    $\begingroup$ @Studentu I would use the induction axiom to prove certain universal statements. E.g. if I needed to prove the statement $\forall x \forall y \ x + y = y+x$ (i.e. the commutativity of $+$), then I might use the relevant instance of the induction axiom ... but 1) doesn't ask you to prove a universal statement ... nor does 2 for that matter: all the more reason why for 2) you don't need that induction axiom at all. In fact, for 2) we don't even need a mathematical proof of induction; it is indeed as simple as you initially thought it was. $\endgroup$ – Bram28 Nov 26 '18 at 22:57

Your Answer

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.