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?
Hello jzelltWe can do this with a combination of proof by induction and reductio ad absurdum.
Assumption: Assume that has no maximum. Then .
We now show by induction that .
So, define the propositional function as . Then
So .
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.
Grandad