## Second Principle of Induction Derived From the Well Ordering Principle

Second Principle of Mathematical Induction
Let
$P(n)$
be a proposition depending on an integer
$n$
. If
1)
$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 true
then
$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)$
$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$
. 