Why induction prevents interlacing in $\mathbb{N}$

Question

A number of works on set theory and the construction of the natural numbers state that the inclusion of the principle of induction in the Peano axioms is necessary to prevent $\mathbb{N}$ from being composed of two disjoint sets, each of which obey the remaining axioms. So in other words if we consider $$0, 1, 2, 3, 4, 5, \ldots$$ induction guarantees that there are no other natural numbers between each of the numbers on the list. Can someone explain why this is true?

Answer 1

Disclaimer: I'm neither logician nor set theorist. This is informal overview of intuition behind Peano's axioms. Feel free to correct any inadequacies or fallacies.

We can go through axioms one by one (skipping the properties of equality):

(1) $\ 0\in\mathbb N$

Ok, we have that $\mathbb N$ is not empty. But, $\mathbb N = \{0\}$ is a model satisfying only axiom 1. Not good enough.

(2) $\exists S\colon\mathbb N\to\mathbb N$

This means that every natural has its successor, again a natural number. Now, not only $0\in\mathbb N$, but also $S(0),\ SS(0),\ SSS(0),\ldots$ Well, not quite, note that $\mathbb N$ might still be singleton, if for example $S$ is constant function, i.e. $$\mathbb N = \{0\},\ S\colon\mathbb N\to\mathbb N,\ S(0) = 0$$ is a model of axioms 1 and 2.

(3) $(\forall n\in\mathbb N)\ S(n)\neq 0$

Great, $\mathbb N$ is not a singleton, there is at least one more element other than $0$, otherwise $S(0) = 0$. Let us define $1 = S(0)$. We know that $0\neq 1$. However, $$\mathbb N=\{0,1\},\ S(0) = 1,\ S(1) = 1$$ is a model of axioms 1 to 3.

(4) $S$ is injection.

Ok, now we finally get that $0,\ S(0),\ SS(0),\ldots$ are all different, so we can give them names $0,1,2,\ldots$ We got what we wanted, so we can stop now, right? Not so fast.

$$\mathbb N = \mathbb R_{\geq 0},\ S\colon\mathbb N\to \mathbb N,\ S(x) = x + 1$$ is a model of axioms 1 to 4.

(5) (Principle of mathematical induction AKA There are no more naturals other than the ones that we constructed so far) Let $X$ be a set such that:

(i) $0\in X,$

(ii) $(\forall n\in\mathbb N)\ n\in X\implies S(n)\in X.$

Then, $\mathbb N\subseteq X$.

Just set $X =\{ 0, S(0), SS(0), \ldots\}$ to get $\mathbb N = X$ from axiom 5.

Answer 2

To understand this properly it may be helpful to point out that there are realistic models that are of the type you mentioned and indeed contain "extra components". Countable models of orders of this type can be described as $\Bbb N \cup \Bbb Q\times \Bbb Z$ and were originally developed by Skolem. These are models of Peano arithmetic and in this sense do satisfy the induction axiom but seen externally they contain the extra components of the type you mentioned.

Answer 3

First of all, any model of the Peano Axioms must contain some infinite sequence of objects $a_0,a_1,a_2,...$, where $a_0$ is the object denoted by the constant symbol $0$, $a_1$ the object denoted by the term $s(0)$, $a_2$ the object denoted by the term $s(s(0))$, etc. In fact, that such an infintie sequence is part of any model is already forced by the axioms $\forall x s(x)\not = 0$ and $\forall x \ \forall y (s(x) = s(y) \rightarrow x= y)$

However, this does not mean that $a_0=0$, $a_1=1$, etc. We could, for example, pick as a domain $0,\frac{1}{2}, 1, \frac{3}{2}, ...$. We would have to pick some non-standard interpretations of $s$, $+$, and $\cdot$ to make this work, but it can be made to work. So really, the best that the Peano Axioms can do is to force our model to have a certain structure, and that structure will have to be isomorph to the natural numbers with addition and multiplication.

That said, the key to making sure that the model will indeed be isomorph to the natural numbers is indeed the axiom of induction. Without the axiom of induction, 'non-standard' models are possible where you have objects in your domain other than the series of objects $a_0,a_1,a_2,...$. But with the axiom of induction, such 'extraneous' elements are rules out.

The technical details are more complex than this, but here is an intuitive way to think about this that is good enough for your purpose:

Induction says that for any arbitrary property $P$: If $0$ has property $P$, and if $s(x)$ has property $P$ whenever $x$ has property $P$, then 'everything' has property $P$. In logic:

$$(P(0) \land \forall x (P(x) \rightarrow P(s(x))))\rightarrow \forall x P(x)$$

Now, what is the 'everything' here? That is of course everything in the domain. So now ask yourself this: why would 'everything in the domain' have property $P$ if $0$ has property $P$, and if $s(x)$ has property $P$ whenever $x$ has property $P$have property $P$? Clearly, all of the objects $a_0,a_1,a_2,...$ (the 'natural numbers') will have to have property $P$, for they are all included in the 'domino-chain'. But what if you had other objects in your domain? Why would they have property $P$ just because we just showed that all of $a_0,a_1,a_2,...$ have property $P$? That would certainly be not at all clear. Indeed, one can presumably find cases where the induction axiom would not be true if one had a domain where there are indeed objects that exists in the domain, but are not part of the $a_0,a_1,a_2,...$ 'natural numbers'. In other words, we have an intuitive argument for:

If there are objects other than the natural numbers in the domain, then the axiom of induction is not true.

So, by assuming the axiom of induction to be true ... then by Modus Tollens ... there cannot be any other objects in the domain other than the ones denoted by $a_0,a_1,a_2,...$ (i.e., the 'natural numbers').

Answer 4

In Peano's axioms, the successor function "connects" each number with another number.

Suppose induction holds on set $M$ (not necessarily the set on natural numbers) as follows:

1. $\space 0 \in M$

2. $\space M: S \to S$

3. $\space \forall P\subset M: [0 \in P \land \forall x\in P: [S(x)\in P] \implies \forall x \in M: x \in P]$

(Note that, unlike the case with Peano's Axioms, $S$ is not necessarily injective, and $0$ may have a pre-image in $M$ under $S$. $M$ may even be finite, e.g. $M=\{0,1\}$ with $S(0)=1$ and $S(1)=0$.)

Then it can be shown that there cannot exist a non-empty, proper subset $A$ of $M$ such that no element of $A$ is "connected" by $S$ to any element of $M-A$. More formally:

$\neg \exists A \subset M: [A\ne \emptyset \land \exists x \in M: [x\notin A]$

$\land \forall x,y: [x\in A \land y \in M \land y\notin A \implies S(x)\ne y \land S(y)\ne x]]$

Hint: The proof is a fairly trivial if somewhat tedious proof by contradiction that considers two cases: $0 \in A$ and $0\notin A$.