Direct Proofs regarding Induction

  • #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.
 

Answers and Replies

  • #2
SSequence
517
82
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) ] ##
 
  • Like
Likes mfb and CGandC
  • #3
CGandC
279
23
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.
 
  • #4
TeethWhitener
Science Advisor
Gold Member
2,437
1,981
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.
 
  • #5
SSequence
517
82
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.
 
  • #6
TeethWhitener
Science Advisor
Gold Member
2,437
1,981
Induction is an axiom in Peano arithmetic.
 
  • Like
Likes jim mcnamara, Svein and SSequence

Suggested for: Direct Proofs regarding Induction

  • Last Post
Replies
10
Views
609
Changing the Statement Combinatorial proofs & Contraposition
  • Last Post
Replies
5
Views
471
  • Last Post
Replies
6
Views
767
Replies
8
Views
856
Replies
10
Views
1K
  • Last Post
Replies
1
Views
460
Constructive Proofs Proof of Correspondence theorem
  • Last Post
Replies
1
Views
553
Replies
37
Views
6K
Constructive Proofs (open) Little Fermat Proof
  • Last Post
Replies
2
Views
586
Top