Proof of mathematical induction: Difference between revisions

Revision as of 20:09, 5 January 2006

Revision as of 21:46, 9 June 2006

Line 1:

The principle of [[mathematical induction]] can be proved if the following [[axiom]]s isare 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. The key technique is [[natural deduction logic]] and [[proof by contradiction]].

Suppose

Line 13 ⟶ 14:

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

We wish to prove:

Consider also the statement

:(3)   For all ''mP'' ≥ 0,is ''P'true'('' for all integer values of ''m'').

-Let in''S'' otherbe wordsthe set of numbers for which ''P'' is '''true''' for all integer values of 'false'm''.

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

Assume this is '''false''', which is equivalent to

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''.

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

Thus, ''S'' has no minimal element, and by (A1) must be empty. Thus, ''P'' is '''true''' for all integer values of ''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==