Principle of Finite Induction
If
\[S\]
is a finite set of positive integers with the properties1.
\[1 \in S\]
2.
\[k \in S \rightarrow k+1 \in S\]
then
\[S = \mathbb{Z}^{{}+{}}\]
.Proof
Proof is by contradiction. Assume the theorem is not true and there is a set
\[S\]
of positive integers satisfying 1 and 2 above which is not the whole of \[\mathbb{Z}^{{}+{}}\]
. Let \[A\]
be the set of positive integers which do not belong to \[S\]
. By the assumption that \[S\]
is not the whole of \[\mathbb{Z}^{{}+{}}\]
A is not the empty set. By The Well Ordering Principle \[A\]
must contain a least member \[a\]
.By 1 above, the integer 1 belongs to
\[S\]
so is not in \[A\]
and \[a \gt 1\]
. Consider \[a-1\]
which is positive since \[a \gt 1\]
. Also \[a-1 \notin A\]
since \[a\]
is the smallest element of \[A\]
so \[a-1 \in S\]
. 2 above now tells us that the number following \[a-1\]
, namely \[a\]
belongs to \[S\]
contradicting that \[a \in A\]
. Hence \[A\]
is empty and \[S= \mathbb{Z}^{{}+{}}\]
. 
