Proof of mathematical induction: Difference between revisions

Revision as of 21:46, 9 June 2006

Revision as of 21:56, 9 June 2006

Line 29:

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 if ''S'' has no smallest element then ''S'' is empty.

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.

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]]