- #1

CGandC

- 279

- 23

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