Strictly Increasing Sequence of Natural Numbers

Theorem

Let $\N_{>0}$ be the set of natural numbers without zero:

$\N_{>0} = \set {1, 2, 3, \ldots}$

Let $\sequence {n_r}$ be a strictly increasing sequence in $\N_{>0}$.

Then:

$\forall r \in \N_{>0}: n_r \ge r$

Proof

This is to be proved by induction on $r$.

For all $r \in \N_{>0}$, let $\map P r$ be the proposition $n_r \ge r$.

Basis for the Induction

When $r = 1$, it follows that $n_1 \ge 1$ as $\N_{>0}$ is bounded below by $1$.

Thus $\map P 1$ is true.

This is our basis for the induction.

Induction Hypothesis

Now we need to show that, if $\map P k$ is true, where $k \ge 1$, then it logically follows that $\map P {k + 1}$ is true.

So our induction hypothesis is that $n_k \ge k$.

Then we need to show that $n_{k + 1} \ge k + 1$.

Induction Step

This is our induction step:

Suppose that $n_k \ge k$.

Then as $\sequence {n_r}$ is strictly increasing:

$n_{k + 1} > n_k \ge k$

From Sum with One is Immediate Successor in Naturally Ordered Semigroup, we have:

$n_{k + 1} > k \implies n_{k + 1} \ge k + 1$

So $\map P k \implies \map P {k + 1}$ and the result follows by the Principle of Mathematical Induction.

Therefore $\forall r \in \N_{>0}: n_r \ge r$.

$\blacksquare$

Although this article appears correct, it's inelegant. There has to be a better way of doing it. In particular: Better link instead of Sum with One is Immediate Successor in Naturally Ordered Semigroup You can help $\mathsf{Pr} \infty \mathsf{fWiki}$ by redesigning it. To discuss this page in more detail, feel free to use the talk page. When this work has been completed, you may remove this instance of {{Improve}} from the code. If you would welcome a second opinion as to whether your work is correct, add a call to {{Proofread}} the page.