# Proof that the induction principle excludes “rogue” elements from the natural numbers

My question is related to this other question. I was asking myself exactly the same questions as OP, and I read carefully each answer he got, but even after spending some hours on it I was still not totally convinced that the induction principle allows to exclude all numbers such as $0.5$, $1.3$, etc., from what we want the natural numbers to be.

I visited the Wikipedia article about Peano axioms, on which the induction axiom is stated in the following form:

If $K$ is a set such that:

$0$ is in $K$, and

for every natural number $n$, $n$ being in $K$ implies that $S(n)$ is in $K$,

then $K$ contains every natural number.

and from this, I tried to show that this really means that the set of natural numbers contains no other element than those expected. (Because it was still not obvious to me.) The problem is that I have no idea if my proof means anything at all, so I would be really happy if someone could check if it makes sense or not.

So here it is:

Let $K$ be a set such that $0$ is in $K$ and such that, for every natural number $n$, $n$ being in $K$ implies that $S(n)$ is in $K$.

Let's suppose, for the sake of contradiction, that the final statement of the axiom is wrong, i.e. let's suppose that there exists a natural number $n$ such that $n \notin K$.

Let $m$ be the smallest element of $\mathbb{N}$ such that $m \notin K$. Because of the first hypothesis of the induction axiom (i.e. "$0$ is in $K$"), $m \ne 0$.

Because $m \in \mathbb{N}$ and $m \ne 0$, $m$ is the successor of another natural number, say $m = p{++}$, with $p \in \mathbb{N}$.

Because $m$ is the smallest element in $\mathbb{N}$ such that $m \notin K$, we have that $p \in K$. But, because of the second hypothesis of the induction axiom (i.e. "$n$ being in $K$ implies $S(n)$ is in $K$"), this means that $p{++}=m$ should be in $K$, which is a contradiction. Therefore, the induction axiom holds and any number that satisfies the hypotheses of this axiom have to be a natural number. $\square$

What bothers me the most in this "proof" (if it is one) is that I use the fact that there is a "smallest" element which satisfies a certain property, while at that point of the book, the author didn't have defined an order over the natural numbers yet... so how can we know if there is a smallest element among them?

Anyway, my question is still the same: does this proof make any sense?

• Peano's axioms don't out 0.5 being a natural number, because peano's axioms don't say anything about 0.5. To say "peano's axioms rule out X from being a natural number" you need a theory with axioms about X. – DanielV Apr 5 '17 at 22:05

It seems to me that your proof is proving something different than what you want it to prove.

You want to know why the induction axiom rules out 'rogue' elements like 0.3.

But your proof merely seems to show that if the base case and inductive step of the induction axiom holds relevant to some property in question, that then we can say that all natural numbers have the property in question. In other words, you're basically confirming that induction 'works' for the natural numbers. .... But that does not rule out any rogue numbers at all: it does not tell me that there are not any 'rogue' numbers within the set of natural numbers that should not be there.

Indeed, the Wikipedia article you reference merely describes the inductive axiom; it does not prove that the induction principle excludes such rogue numbers.

The way to do that is as follows: the inductive axiom concludes $\forall x P(x)$ on the basis of $P(0)$ and $\forall x (P(x) \to P(s(x)))$. But $P(0)$ and $\forall x (P(x) \to P(s(x)))$ together only show that $0, s(0), s(s(0)), ...$ all have property $P$; we have not shown anything else to have property $P$. So, it must be that the domain that the $\forall$ quantifier over is exactly $0, s(0), s(s(0)), ...$, (i.e. exactly the natural numbers) for otherwise we could not draw that conclusion of $\forall x P(x)$.

So in sum: your proof shows that $P(0)$ and $\forall x (P(x) \to P(s(x)))$ implies that all the natural numbers have property $P$. But what you are looking for is a proof that shows that if $(P(0) \land \forall x (P(x) \to P(s(x)))) \to \forall x P(x)$, then the domain must contain only the natural numbers.

• Thanks for your answer. I still don't clearly understand the difference between "$P(0)$ and $\forall x (P(x) \rightarrow P(s(x))$ implies that all the natural numbers have property $P$" and "$(P(0)$ and $\forall x (P(x) \rightarrow P(s(x)))) \rightarrow \forall x P(x)$, then the domain must contain only the natural numbers", but it's late here and I'm probably too tired to think properly... I'll watch all this one more time tomorrow. Thanks again anyway! :) – justdoit Apr 5 '17 at 21:17

If we take the first few Peano Axioms.

$0$ is in $\mathbb N$

Every element of $\mathbb N$ has a successor (S(n)).

S(n) is injective. There are not multiple elements with the same successor.

There is no element which has $0$ as its successor.

Lets suppose we take $\mathbb N$ as we traditionally understand it and add a rogue number.

Suppose we have a set $M = \mathbb N \cup \{\infty\}$

With $S(\infty) = \infty$

We might call this the extended natural numbers. Without the principle of induction $M$ meets all of the required criteria.

But bringing in the principle of induction.

$\infty$ is not in $\mathbb N$ because that would require an $n\ne \infty$ such that $S(n) = \infty$ and that would contradict our axiom that $S(n)$ is an injection.

Update.....

Suppose you wanted to define the successor to $9$ as $0.1$

And we will count $0,1,2,3\cdots, 8,9,0.1, 1.1\cdots,8.1,9.1,0.2,1.2\cdots.$

You can do that, and your set will in fact be the natural numbers. Or at least, when put together with the remaining axioms of addition and multiplication, will behave just like the natural numbers. The arithmetic may be confusing because we are expecting that notation to have a different meaning. Doesn't mean it won't be structurally identical.

Perhaps we should say that your set will be isomorphic to $\mathbb N$

• Thanks for your answer. But why would the principle of induction require an $n \ne \infty$ such that $S(n) = \infty$? – justdoit Apr 5 '17 at 21:22
• Somewhere you have to get off the train of numbers that are in succession from 0, onto the circular track that is infinity, and at the place that you make this jump there is an $n$ not equal to infinity who has infinity as its successor element. – Doug M Apr 5 '17 at 21:35
• Ok, I got it now ; thanks! Concerning your update: now the problem is I don't really understand anymore why Terence Tao says: "What we want is some axiom which says that the only numbers in $\mathbb{N}$ are those which can be obtained from $0$ and the increment operation - in order to exclude elements such as $0.5$. But it is difficult to quantify what we mean by "can be obtained from" without already using the natural numbers, which we are trying to define. Fortunately, there is an ingenious solution to try to capture this fact.", and then he exposes the principle of induction. Confusing. – justdoit Apr 6 '17 at 3:59