Least Number Principle

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

Proof

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.

References

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