Proof of mathematical induction: Difference between revisions

Revision as of 01:45, 1 August 2006

Latest revision as of 02:21, 5 August 2006

Line 1:

{{merging|mathematical#REDIRECT [[Mathematical induction}}]]

The principle of [[mathematical induction]] can be proved if the following [[axiom]]s are assumed:

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

:(A2) if ''m'' > 0, then there exists ''n'' such that ''m'' = ''n'' + 1

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.

Suppose

:(1)   ''P''(0)

and

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

We wish to prove:

:(3)    ''P'' is '''true''' for all integer values of ''m''.

Let ''S'' be the set of numbers for which ''P'' is '''false'''.

Using (1), we see that ''0'' is not an element of ''S'' and is therefore not the minimal element of ''S''.

Using (A2), if ''m'' > 0, then ''m'' = ''n'' + 1. Now if ''n'' is in ''S'', then ''m'' being bigger cannot be the minimal element of ''S''. But if ''n'' is not in ''S'', ''P''(''n'') and using (2) ''P''(''n'' + 1) and so ''m'' is not in ''S'' and cannot be the minimal element of ''S''.

Thus, ''S'' has no minimal element, and by (A1) must be empty. Thus, ''P'' is '''true''' for all integer values of ''m''

==Converse==

Conversely, the axiom (A1) can be proved by the principle of [[mathematical induction]]. Indeed, given (A2), the two are equivalent.

Let ''S'' be a set of natural numbers. We want to prove that if ''S'' has no smallest element then ''S'' is empty.

Consider a set ''S'' with no smallest element and let ''P''(''n'') be the statement that ''n'' is NOT an element of ''S''.

:(1) Since ''S'' has no smallest element, ''0'' cannot belong to ''S'' and so ''P''(0) is true.

:(2) Suppose that ''P''(''n'') is true for some ''n''. That is, ''n'' does not belong to ''S''. Since ''S'' has no smallest element, ''n'' + 1 cannot belong to ''S'' either and so we have ''P''(''n''+1)

Then by induction, we know that ''P''(''n'') is true for all ''n'', and therefore ''S'' is empty. Thus, we are done.

[[Category:Proofs]]

[[zh:数学归纳法的证明]]