The *least number principle* states that every non-empty set of natural numbers has a least element.

The proof is by contradiction.
Take `X`

to be an arbitrary non-empty subset of `N`

, `X≠Ø⊂N`

,
such that `X`

has no least element.
Let the property `E(n)`

mean `n∈N-X`

.
We will establish the contradiction using strong induction.
Our induction hypothesis is that `∀m,n∈N m<n:E(m)`

.
We know `E(n)`

because if `n∈X`

would mean `X`

had a least element: namely `x`

.
So by using strong induction we have established that `∀n∈N E(n)`

.
This means that `X=Ø`

which is a contradiction.

Doets, Kees. *From Logic to Logic Programming.* MIT Press, 1994.

Copyright © 2014 Barry Watson. All rights reserved.