Thread: Proof Of Mathematical Induction

The manner in which mathematical induction is introduced in my textbook has me wondering about its proof:

Theorem: The Principle of Mathematical Induction

Suppose that the following two conditions are satisfied with regard to a statement about natural numbers:

CONDITION I: The statement is true for the natural number 1.
CONDITION II: If the statement is true for some natural number k, it is also true for the next natural number k + 1.

Then the statement is true for all natural numbers.

The text then goes on to say that this principle will not be proven, and then provides an analogy of falling dominos.

What does the proof of this theorem look like?

The proof of the validity of mathematical induction is by contradiction and depends upon the axiom of well ordering. That axiom states: Every subset of positive integers contain a first or a least integer. Using that axiom, suppose that the statement fails for some positive integer then it fails for sum first J. We know that J is not 1 because it is true for 1. Therefore, J-1 is positive integer and the statement is true for J-1 because J is the first for which it is not true. However if it is true for J-1 it must be true for (J-1)+1 =J. Thus there is a contradiction.

Originally Posted by spiritualfields

What does the proof of this theorem look like?

The formal proof of this is based on Peano Axioms.

Thanks. It looks like the proof involves first supposing that the two conditions are true, then denying the second condition and using it to produce the contradiction of the condition being true and not true at the same time. After which there is the image of the mathematician in a tophat and tap shoes, clicking his heels with a flourishing "ta da!"

Originally Posted by spiritualfields

Thanks. It looks like the proof involves first supposing that the two conditions are true, then denying the second condition and using it to produce the contradiction of the condition being true and not true at the same time. After which there is the image of the mathematician in a tophat and tap shoes, clicking his heels with a flourishing "ta da!"

In at least some developments of arithmetic the principle of mathematical
induction is an axiom.

RonL

In at least some developments of arithmetic the principle of mathematical induction is an axiom.

Yes, that's what I thought makes more sense after seeing the proof.