Proof of mathematical induction: Difference between revisions

Revision as of 20:14, 24 July 2006

Latest revision as of 02:21, 5 August 2006

(2 intermediate revisions by 2 users not shown)

Line 1:

#REDIRECT [[Mathematical induction]]

<!-- Please do not remove or change this AfD message until the issue is settled -->{{#if:{{{nosubst|}}}|<div style="display:none;">}} {{#ifeq:{{NAMESPACE}}|| |{{error:not substituted|AFD}}<div style="display:none;">}}{{#if:{{{nosubst|}}}|</div></div>}}

<div class="boilerplate metadata" id="afd" style="margin: 0 5%; padding: 0 7px 7px 7px; background: #EDF1F1; border: 1px solid #999999; text-align: left; font-size:95%;">

'''This article is being considered for deletion in accordance with Wikipedia's [[Wikipedia:Deletion policy|deletion policy]][[Template:Afd|.]]'''<br />

Please share your thoughts on the matter at '''[[Wikipedia:Articles for deletion/{{{1|Proof of mathematical induction}}}|this article's entry]]''' on the Articles for deletion page.<br />

Feel free to edit the article, but the article must not be blanked, and this notice must not be removed, until the discussion is closed. For more information, particularly on merging or moving the article during the discussion, read the [[Wikipedia:Guide to deletion|guide to deletion]].<br/>

''<small>Steps to [[Template:AfD footer|list an article for deletion]]: {{tls|afd}} <nowiki>{{</nowiki>subst:afd2|pg={{PAGENAME}}|text=}} <nowiki>{{</nowiki>subst:afd3|pg={{PAGENAME}}}} [{{SERVER}}{{localurl:Wikipedia:Articles for deletion/Log/{{CURRENTYEAR}}_{{CURRENTMONTHNAMEGEN}}_{{CURRENTDAY}}|action=edit}} log] </small></div>

{{{category|[[Category:Articles for deletion]]}}}

<!-- End of AfD message, feel free to edit beyond this point -->

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'' &gt; 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)&nbsp;&nbsp;&nbsp;''P''(0)

and

:(2)&nbsp;&nbsp;&nbsp;For all ''n'' &ge; 0, ''P''(''n'') &rArr; ''P''(''n'' + 1)

We wish to prove:

:(3)&nbsp;&nbsp;&nbsp; ''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'' &gt; 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:数学归纳法的证明]]