Direct Proofs regarding Induction

In summary: This means that induction is assumed to be true in this system, and from that assumption, we can prove other things. It is not a theorem that needs to be proven, it is taken as a given.In summary, proof by induction involves proving a base case and an inductive step, and then using the axiom of induction to conclude the desired statement. The statement ## P(0) \land \forall n ( P(n) \rightarrow P(n+1) ) \rightarrow \forall n ( P(n) ) ## is an axiom, not a theorem, and it allows us to use modus ponens to conclude the desired statement.
  • #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.
 
Physics news on Phys.org
  • #2
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
SSequence said:
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
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
TeethWhitener said:
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
Induction is an axiom in Peano arithmetic.
 
  • Like
Likes jim mcnamara, Svein and SSequence

Related to Direct Proofs regarding Induction

What is a direct proof?

A direct proof is a method of mathematical proof in which the conclusion is directly derived from the given premises using logical reasoning and previously established theorems or axioms.

What is mathematical induction?

Mathematical induction is a method of mathematical proof used to prove statements that are dependent on a natural number n. It involves proving that the statement is true for the first value of n, and then showing that if it is true for any value of n, it must also be true for the next value of n.

How is mathematical induction used in direct proofs?

Mathematical induction can be used in direct proofs to prove statements about natural numbers by breaking them down into smaller, simpler cases and proving them one by one. This allows for a more systematic and organized approach to proving statements.

What is the principle of mathematical induction?

The principle of mathematical induction states that if a statement is true for the first natural number n=1, and if it is true for any arbitrary natural number k, then it must also be true for the next natural number k+1. This allows for the proof of statements about natural numbers to be extended to all natural numbers.

What are some common mistakes to avoid in direct proofs using mathematical induction?

Some common mistakes to avoid in direct proofs using mathematical induction include assuming that the statement is true for all natural numbers without proving it for the base case, using incorrect or invalid logical reasoning, and not clearly stating the inductive hypothesis and the steps in the proof. It is important to carefully follow the steps of mathematical induction and to check for errors in the logic and reasoning of the proof.

Similar threads

  • Math Proof Training and Practice
Replies
10
Views
1K
  • Math Proof Training and Practice
Replies
1
Views
1K
  • Math Proof Training and Practice
Replies
4
Views
1K
  • Precalculus Mathematics Homework Help
Replies
10
Views
381
  • Calculus and Beyond Homework Help
Replies
7
Views
574
  • Math Proof Training and Practice
Replies
7
Views
1K
  • Math Proof Training and Practice
Replies
19
Views
2K
  • Math Proof Training and Practice
2
Replies
61
Views
6K
Replies
5
Views
783
  • Math Proof Training and Practice
Replies
6
Views
1K
Back
Top