Let
Show
satisfies the Well-Ordering Principle. Clearly
is a set of integers, and by definition, every element is greater than or equal to 0. So we just need to show that
If
let
Then
But
and
Thus,
Hence
Thus,
is nonempty and satisfies the conditions of the Well-Ordering Principle. Hence,
has a least element. Call it
Since
for some
Let
Then
and so
We just need to show that
Well,
since
We will use contradiction to show Assume Then
But then and This contradicts that was the smallest element of Therefore,