principle of mathematical induction

Let SN.
If

  1. 1S
  2. for all kN, kS(k+1)S

then S=N.


Proof

Suppose for the sake of contradiction that NS, i.e. NS.
By the well-ordering principle, NS has a least element m.
Since 1S, m>1.
Since m a least element of NS, (m1)S
However, by 2), (m1)+1S, i.e. mS, a contradiction.

So N=S.

QED

Powered by Forestry.md