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

You have no rights to post comments