SupposeA is a non-empty subset of N with an upper bound. In other words, suppose there is a b eN such that
every y eA satis es y <= b. Then A has a maximum.
How would I prove this?
Assumption: Assume that has no maximum. Then .
We now show by induction that .
So, define the propositional function as . Then
is true. So by induction is true .
In particular if , where is an upper bound of , . But . Contradiction.
So our original assumption is false, and A therefore has a maximum.