Non User
Index: > A B C D E F G H I J K L M N O P Q R S T U V W X Y Z	Business Non User Industries Finance Tax

Home > Proof of mathematical induction

The set of all natural numbers is well-ordered (that is, every non-empty set of natural numbers has a least element).

A simplified version is given here. This proof does not use the standard mathematical symbols for there exists and for all to make it more accessible to less mathematically motivated readers. The key technique is natural deduction logic and proof by contradiction.

Suppose

(1)   P(0)

and

(2)   For all n ≥ 0, P(n) ⇒ P(n + 1)

Consider also the statement

(3)   For all m ≥ 0, P(m)

- in other words P is true for all integer values of m.

Assume this is false, which is equivalent to

(4)   There exists an m such that not P(m)

The proof hinges on showing that if (1) and (2) hold, then (4) is false, hence (3).

Assume (1), (2) and (4).

Using (4), let m′ be the smallest such value such that not P(m′)

Clearly m′ cannot be 0, since this leads to an immediate contradiction (P(0) & not P(0)) with P(0) - rule (1)

Suppose m′ > 0.

From the definition of m′, P(m′ - 1), hence by (2) P(m′). This also gives a contradiction, P(m′) & not P(m′).

It thus follows that (1) and (2) together imply not (4), which we have already established is just (3).

Hence if

(1)   P(0)

and

(2)   P(n) ⇒ P(n + 1)

it follows that (with a trivial change of variable)

(3)   for all n ≥ 0, P(n)

which is the principle of mathematical induction.

Converse

Conversely, the axiom can be proved by the principle of mathematical induction. Indeed, the two are equivalent.

Let S be a set of natural numbers. We want to prove that either S has a smallest element or else that S is empty. Let P(n) be the statement that no element of S is smaller than n. P(0) is certainly true, since there is no natural number smaller than 0. Suppose that P(n) is true for some n. If P(n + 1) were false, then S would have an element smaller than n + 1, but it could not be smaller than n, because P(n) was true, and so S would have a minimal element, namely n, and we would be done. So P(n) implies P(n + 1) for all n, or else S has a minimal element. But if P(n) implies P(n + 1) for all n, then by induction we know that P(n) is true for all n, and therefore for all n, no element of S is smaller than n. But this can only be vacuously true, if S has no elements at all, since every natural number is smaller than some other natural number. Thus we are done.

Politics	Business	Finance

Topics: Proof Of Mathematical Induction P''(''n Natural Element Smaller...

---

ProofThe word proof can mean: originally, a test assessing the validity or quality of something. a rigorous, compelling argument, including: a logical argument or a mathematical proof (see also proof theory). a legal proof. a large accumulation of scientific e Proofs of Fermat's little theoremThis is a collection of proofs of Fermat's little theorem: a p a ( mod p for every prime number p and every integer a''. Note that it is enough to prove a p − 1 1 (mod p for every integer a which is relatively prime to p (i. not a multiple of p . Proof of angular momentumA proof that torque is equal to the time- derivative of angular momentum can be stated as follows: The definition of angular momentum for a single particle is: where "×" indicates the vector cross product. The time-derivative of this is: d L ''dt r × d p Proof (play)Proof is a play by David Auburn which won the 2001 Pulitzer Prize for Drama and the 2001 Tony Award for Best Play. It concerns the daughter of a recently-deceased professor of mathematics at the University of Chicago and her struggle with mathematical gen Proof theoryLogic Proof theory Proof theory studied as a branch of mathematical logic, represents proofs as formal mathematical objects, facilitating their analysis by mathematical techniques. Proofs are typically presented as inductively-defined data structures, suc Proof of mathematical inductionThe principle of mathematical induction can be proved if the following axiom is assumed: :The set of all natural numbers is well-ordered (that is, every non-empty set of natural numbers has a least element). A simplified version is given here. This proof Proofreading Proof that the sum of the reciprocals of the primes diverges Proof of Bertrand's postulate Proof that e is irrational Proof by exhaustion Proof coinage Proof that holomorphic functions are analytic Proof of concept Proofs and Refutations