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 $\displaystyle A$ has no maximum. Then $\displaystyle \forall x \in A, x+1 \in A$.
We now show by induction that $\displaystyle y \in A \Rightarrow (y + n) \in A, \forall n \ge 1$.
So, define the propositional function $\displaystyle P(n)$ as $\displaystyle y \in A \Rightarrow (y + n) \in A$. Then $\displaystyle P(n) \wedge (x \in A \Rightarrow x+1 \in A) \Rightarrow (y + n + 1) \in A$
So $\displaystyle P(n) \Rightarrow P(n+1)$.
$\displaystyle P(1)$ is true. So by induction $\displaystyle P(n)$ is true $\displaystyle \forall n \ge 1$.
In particular if $\displaystyle n = b + 1$, where $\displaystyle b$ is an upper bound of $\displaystyle A$, $\displaystyle y \in A \Rightarrow y + b +1 \in A$. But $\displaystyle y + b +1 > b, \forall y \in \mathbb{N}$. Contradiction.
So our original assumption is false, and A therefore has a maximum.
Grandad