# Thread: [SOLVED] Proof Help with Naturals

1. ## [SOLVED] Proof Help with Naturals

Suppose
A 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?

2. ## Natural numbers subset

Hello jzellt
Originally Posted by jzellt
Suppose
A 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?
We 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