- #1
CGandC
- 326
- 34
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.
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.