Verifying a Proof for Spivak's Calculus Question (Chapter 2 Problem 9)

Question

It says "Prove that if a set $A$ of natural numbers contains $n_0$ and contains $k+1$ whenever it contains $k$, then A contains all natural numbers $\ge n_0$".

Am I allowed to construct another set $B$ whose elements are $n_0-1$ less than the elements of $A$? Then the set $B$ would have $1$ as one of its elements, and still have the property that $m+1$ is contained whenever $m$ is contained, meaning B will be the set of all natural numbers. Since $B$ is the set of all natural numbers, it will mean that the set $A$ will be the set of all numbers which are greater than or equal to $n_0$. Can someone verify this and give me a hint if my method is faulty?

Answer 1

You can, but it isn't needed?

Let $A$ be a set containing $n_0$. Then, $A$ contains $n_0 + 1$ by hypothesis, since $n_0 + 1\geq n_0$. This is the base case.

Suppose $A$ contains $k$. Then, $k \geq n_0$ or $k \leq n_0$.

Suppose $k \geq n_0$. Then since it contains $k+1$, we have $k+1 \geq k \geq n_0$ so we are done.

If $k \leq n_0$, then it contains $k+1$, and so forth, so there exists some $m$ such that $r = k+m \geq n_0$. But then, it also contains $r + 1 \geq r \geq n_0$ by hypothesis.

So it's proven.

Answer 2

Actually, you don't know that $B$ is the set of natural numbers. It could also contain $0$ or negative numbers, because there is nothing in the assumptions that says that $A$ contains no numbers less than $n_0$. And in fact the conclusion is only that $A$ contains the set of all natural numbers $\ge n_0$, not that it is this set.

This of course can be cleaned up, but you need to be careful of making these assumptions.

An alternative approach to Race's is to note that induction is equivalent to the well-ordering principle: every non-empty set of natural numbers has a least element. So consider the least element of the set of numbers $\ge n_0$ that is not in $A$. It cannot be $n_0$ since we know that $n_0 \in A$, and if it is any higher number $k$, then $k - 1 \in A$, which means that $k = (k - 1) + 1 \in A$, a contradiction. Therefore no such $k$ can exist, and A contains all natural numbers $\ge n_0$.