Simple Induction Direct Proofs regarding Induction

[CGandC]

Summary:: .

When asked to prove by Induction, I'm asked to prove a statement of the form:
Prove that for all natural numbers $n$, $P(n)$
Which means to prove: $\forall n ( P(n) )$ ( suppose the universe of discourse is all the natural numbers )

Then, I see people translating the above statement to the following statement:

$P(0) \land \forall n ( P(n) \rightarrow P(n+1) ) \rightarrow \forall n ( P(n) )$
And this is what they are proving. And eventually they say " therefore, it was proven that $\forall n ( P(n) )$ by induction "

However, I don't really understand this. This is why:

Let's denote the statement $\forall n ( P(n) )$ as $W$.
To prove $\forall n ( P(n) )$ by induction means to prove $W$ .

Let's denote the statement $P(0) \land \forall n ( P(n) \rightarrow P(n+1) )$ as $Q$.
To prove $P(0) \land \forall n ( P(n) \rightarrow P(n+1) ) \rightarrow \forall n ( P(n) )$ means to prove $Q \rightarrow W$

Now's the problem:

If we prove $Q \rightarrow W$ then we only prove this implication, we are not proving $W$.
Meaning, we are only proving $P(0) \land \forall n ( P(n) \rightarrow P(n+1) ) \rightarrow \forall n ( P(n) )$ .
And not $\forall n ( P(n) )$

So how can it be that the problem of proving $\forall n ( P(n) )$ is translated into the problem $P(0) \land \forall n ( P(n) \rightarrow P(n+1) ) \rightarrow \forall n P(n)$ ? Because they are both different statements and thus proving these are different proofs.

 

[SSequence]

It seems that you are making it more complicated than it is. I think the basic point is that $Q \rightarrow W$ can be seen as "truth" of predicate logic so to speak. When we are doing proof by induction, our reasoning is of this kind:
1-- We have proven $Q$ to be true
2-- $Q \rightarrow W$ is known to be true

3-- Therefore $W$ is true.

=====================

There is one further small point that comes to my mind.

If we are talking about a first-order theory with domain of discourse as $\mathbb{N}$ then we can write the statement of "induction" exactly as you wrote:
$P(0) \land \forall n ( P(n) \rightarrow P(n+1) ) \rightarrow \forall n [ P(n) ]$

But if we are, say, talking about a first-order theory (say with single-sort) with domain of discourse that is bigger than $\mathbb{N}$, then we would have to explicitly write [i.e. if we are being more precise]:
$P(0) \land \forall n \in \mathbb{N} \, ( P(n) \rightarrow P(n+1) ) \rightarrow \forall n \in \mathbb{N} \, [ P(n) ]$

 

[CGandC]

It seems that you are making it more complicated than it is. I think the basic point is that $Q \rightarrow W$ can be seen as "truth" of predicate logic so to speak. When we are doing proof by induction, our reasoning is of this kind:
1-- We have proven $Q$ to be true
2-- $Q \rightarrow W$ is known to be true

3-- Therefore $W$ is true.

Now it makes sense, Thanks. I couldn't have thought that the above 3 statements are interwoven one after another so as to use modus ponens.

 

[TeethWhitener]

With induction, you prove both parts of the conjunction in the antecedent. $P(0)$ is the base step that you prove and $\forall n(P(n)\rightarrow P(n+1))$ is the inductive step that you prove. The statement:
$$[P(0)\wedge \forall n(P(n)\rightarrow P(n+1))]\rightarrow \forall nP(n)$$
is an axiom: the axiom of induction (of which there is one for each predicate). When you prove the base step and the inductive step, the axiom of induction let's you conclude $\forall nP(n)$ by modus ponens.

 

[SSequence]

The statement:
$$[P(0)\wedge \forall n(P(n)\rightarrow P(n+1))]\rightarrow \forall nP(n)$$
is an axiom: the axiom of induction (of which there is one for each predicate). When you prove the base step and the inductive step, the axiom of induction let's you conclude $\forall nP(n)$ by modus ponens.

Essentially, you are right. We can always add a statement like:
$P(0) \land \forall n \in \mathbb{N} \, ( P(n) \rightarrow P(n+1) ) \rightarrow \forall n \in \mathbb{N} \, [ P(n) ]$
as an axiom if we want to.

Though in many number of cases (e.g. in set theory) it would be a theorem [that follows from axioms (or axiom schemas I suppose?) and rules of deduction].

But anyway, I don't think this distinction makes a difference in applying it in actual math. The point being that its truth is what matters.

 

[TeethWhitener]

Induction is an axiom in Peano arithmetic.