# 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 $A$ has no maximum. Then $\forall x \in A, x+1 \in A$.

We now show by induction that $y \in A \Rightarrow (y + n) \in A, \forall n \ge 1$.

So, define the propositional function $P(n)$ as $y \in A \Rightarrow (y + n) \in A$. Then $P(n) \wedge (x \in A \Rightarrow x+1 \in A) \Rightarrow (y + n + 1) \in A$

So $P(n) \Rightarrow P(n+1)$.

$P(1)$ is true. So by induction $P(n)$ is true $\forall n \ge 1$.

In particular if $n = b + 1$, where $b$ is an upper bound of $A$, $y \in A \Rightarrow y + b +1 \in A$. But $y + b +1 > b, \forall y \in \mathbb{N}$. Contradiction.

So our original assumption is false, and A therefore has a maximum.