The least number principle states that every non-empty set of natural numbers has a least element.
The proof is by contradiction.
X to be an arbitrary non-empty subset of
X has no least element.
Let the property
We will establish the contradiction using strong induction.
Our induction hypothesis is that
E(n) because if
X had a least element: namely
So by using strong induction we have established that
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.