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

Question

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?

Thanks in advance and sorry for the n-th question about this topic.

Answer 1

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.

Answer 2

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$