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

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

.