Let
\[P(n)\]
be a proposition depending on an integer \[n\]
. If1)
\[P(n_0)\]
is true for some integer \[n_0\]
2) For
\[k \gt n_0\]
\[P(n_0), \; P(n_0+1), \; P(n_0+2),..., \; P(k)\]
are truethen
\[P(n)\]
is true for all \[n \gt n_0\]
.Suppose that
\[S= \{ k \in \mathbb{Z} : k \ge n_0, \; O(k_ \; is \; false \}\]
is non - empty.Consider the set
\[T\]
defined by \[T= \{ s-n_0 : s \in S \}\]
. \[T\]
is a non - empty set of non - negative integers. By 1) \[P(n_0)\]
is true so \[n_0 \notin S\]
and \[0 \notin T\]
and \[T\]
is a non - empty subset of \[\mathbb{Z}^{{}+{}}\]
.By The Well Ordering Principle
\[T\]
has a least element which we can take as \[m-n_0\]
for some integer \[m \in S\]
, and from the definition of \[T\]
, \[m\]
is the least element of \[S\]
.Since
\[n_0 \notin S\]
, \[m \gt n_0\]
. By the definition of \[S\]
it follows that \[P(n_0), \; P(n_0+1),...,P(m-1)\]
must all be true. Then 2) gives that \[P(m)\]
is true, contradicting \[m \in S\]
.Hence the the assumption that
\[S\]
is non - empty must be false. \[S\]
is empty and \[P(k)\]
is true for \[k \gt n_0\]
.