Principio di induzione

[flosfloris]

ciao a tutti ragazzi qualcuno puo postarmi la dimostrazione del principio di induzione????
ce l ho anche sul libro ma è indecifrabile... attendo un vostro aiuto ciaooo

[giuseppe87x]

Riporto questa dimostrazione che fa vedere come il principio di induzione sia equivalente al principio del minimo intero.

Theorem:
If a set S of non-negative integers contains the integer 0, and also contains
the integer n+1 whenever it contains the integer n, then S=N.

Proof:
Assume this is not the case and so, by the Well-Ordering Principle there exists a least positive integer k
not in S. Observe that k>0, since 0∈S and there is no positive integer smaller than 0. As k−1 k−1∈S. But by assumption k−1+1 is also in S, since the successor of each element in the set is also in the
set. Hence k=k−1+1 is also in the set, a contradiction. Thus S=N.