How does the induction axiom rule out numbers other than the naturals?

Question

The set-theoretic formulation of the axiom of induction is as follows:

Suppose $A \subseteq \mathbf{N}$, such that $0 \in A$ and $k+1 \in A$ whenever $k \in A$. Then $A = \mathbf{N}$

This axiom is supposed to rule out possibilities like $A = \mathbf{Q}$ or $A= [0, \infty)$, which satisfy the other Peano Axioms, but not the axiom of induction.

But I don't understand how it rules out the above cases. Firstly, how do we know that the set $A$ is a subset of $\mathbf{N}$ without first defining what $\mathbf{N}$ is? Something seems circular here, which means I've yet to understand the axiom.

Suppose $B$ includes $0$, $S(0), S(S(0))$, and so on, but it also includes fractions such as $\frac{1}{2}$. Induction supposedly prevents $B$ from being $\mathbf{N}$. But this means that we must know beforehand that $B \nsubseteq \mathbf{N}$, which seems circular.

Note: I've searched for similar questions on this site, and while there is one which pretty much asks the same question, I could not find a satisfactory answer.

Answer 1

Let's show that $\mathbb Q$ does not satisfy

Suppose $A \subseteq \mathbf{Q}$, such that $0 \in A$ and $k+1 \in A$ whenever $k \in A$. Then $A = \mathbf{Q}$

Indeed, $A=\mathbb Q \cap [0,\infty)$ has the property specified, but it is not equal to $\mathbb Q$.

Now let's show that $[0,+\infty)$ does not satisfy

Suppose $A \subseteq [0,+\infty)$, such that $0 \in A$ and $k+1 \in A$ whenever $k \in A$. Then $A = [0,+\infty)$.

This time we can use $\{0\} \cup [1,+\infty)$ as the counterexample.

Now you try it. Think of any $X \supseteq \mathbb N$ other than $\mathbb N$. Show that you can find a subset $A$ contradicting induction formulated for $X$.

Answer 2

If we work with the original version of Peano axioms [see e.g. Edmund Landau, Foundations of analysis: The arithmetic of whole rational irrational and complex numbers (original ed.1930), we have:

We assume the following to be given:

A set of objects called natural numbers, possessing the properties — called axioms — to be listed below. [...]

Axiom 5 (Axiom of Induction) : Let there be given a set $\mathfrak M$ of natural numbers, with the following properties:

I) $0$ belongs to $\mathfrak M$.

II) If $x$ belongs to $\mathfrak M$ then so does $S(x)$.

Then $\mathfrak M$ contains all the natural numbers.

Thus, if we consider a set $B = \{ 0, S(0), \ldots, \frac 1 2 \}$ and we mean that the "dots" stay for condition II) above, applying Axiom 5 to $B$ we must have that:

$\mathfrak M \subseteq B$.

---

In a set-theory approach, we define what is a natural number, then we assume the axiom of infinity, then we define the set $\omega$ of all natural numbers, and finally we prove that:

If

(i) $0 \in A$,

(ii) for every $n$, if $n \in A$ then $S(n) \in A$,

then $\omega \subseteq A$.

So again, regarding the set $B$ above : $\omega \subseteq B$.

---

---

Thus, if we suppose:

$A \subseteq \mathbb N$, such that $0 \in A$ and $k+1 \in A$ whenever $k \in A$,

by Induction we have that $\mathbb N \subseteq A$.

So, from:

$A \subseteq \mathbb N$ and $\mathbb N \subseteq A$

we conclude with :

$A = \mathbb N$.

Answer 3

Let me summarize a few of the other answers and comments in one overall picture.

You must keep in mind that in the foundations of mathematics, any axiomatic system depends on certain "givens", i.e. undefined concepts, and then lists certain axioms that these "givens" must satisfy.

There are several distinct axiomatic approaches to arithmetic, and it helps to compare how the natural numbers and the axiom of induction arise in each of them.

First, one can simply start from Peano's Axioms, in which $\mathbb{N}$ and $0$ and the "$+1$" operation are themselves given, and the axiom of induction is just that, an axiom. From your question this is not particularly satisfying to you, so let's go on to some other approaches.

Second, one can start from the axioms for the real numbers $\mathbb{R}$, which can be found in many analysis books. In brief, $\mathbb{R}$ is a complete ordered field; one proves a theorem saying that $\mathbb{R}$ is unique up to isomorphism. One of the axioms gives us the binary operation of addition. Another gives us the additive identity $0$. Another gives us the binary operation of multiplication. Another gives us the multiplicative identity $1$. One can then define the natural numbers $\mathbb{N}$: it is the intersection of all subsets of $\mathbb{R}$ which contain $0$ and $1$ and are closed under addition. Once that is done, the induction axiom becomes a theorem which you can prove, as a consequence of all the other axioms of the real numbers (try it; the answer of @GEdgar is a hint).

Third, one can start from the ZF axioms for set theory, and within those axioms one can define the natural numbers $\mathbb{N}$ (see the answer of @MauroAllegranza for details). In brief, one defines $0 = \emptyset$, and one proves a theorem on the existence of a unique set $\mathbb{N}$ which is a subset of every infinite set that contains $0$ as an element and that is closed under Von Neumann's successor operation $S(a) = a \cup \{a\}$. This set $\mathbb{N}$ is then defined to be the natural numbers. Again, once that is done, the induction axiom becomes a theorem which one proves, as a consequence of the ZF axioms.

So the big picture is that the natural numbers $\mathbb{N}$ arise in two different ways, depending on what axioms one uses as a foundation: either $\mathbb{N}$ is built into the axioms directly (as in Peano's axioms); or $\mathbb{N}$ is defined and then induction is proved as a theorem.

Answer 4

"Firstly, how do we know that the set A is a subset of N without first defining what N is?"

That's the crux of the matter the axioms are that a set $\mathbb N$ exists that satisfies the following axioms.

"prior" to the axioms $\mathbb N$ might be... anything. It could be $\{\}$. It could be {all the elephants}. I could be $\mathbb Q$. It could be {the spiders of mars} $\cup \mathbb Z$.

Axiom 1) $0 \in \mathbb N$.

Okay that rules out the empty set and it rules out {all the elephants}. But it allows $\mathbb Q$ and {the spiders of mars} $\cup \mathbb Z$.

Axiom 2) If $n \in \mathbb N$ some number $n + 1 \in \mathbb N$.

Okay, that rules out {the spiders of Mars} $\cup \mathbb Z$. But we still have $\mathbb Q$, $\mathbb Z$, $[0,\infty)$ and others.

Axiom 3) $0 \ne n+1 $ for any $n \in \mathbb N$.

Okay... that rules out $\mathbb Q$ and $\mathbb Z$. But it leaves $[0,\infty)$ and $\mathbb Q^{\ge 0}$ and even a bizarre $\mathbb R - ${negative integers}.

Axiom 4) If $x, y \in \mathbb N$ and $x + 1 = y + 1 \implies x = y$.

Okay... I confess in the above examples I've been taking the definition of $n + 1$ for granted and assuming it wasn't an issue of discussion.

But this basically says that $n + 1 \ne n$ and that the set {0, 0+1 = 1, 1+ 1= 2, 2+ 1= 3,....} will be infinite with distinct elements and is the smallest set we can consider. Although the set {0, 1/2, 1, 1 1/2, 2, 2 1/2,...} is still a contender. As are those sets I mentioned above.

Axiom 5) (finally) Any subset of $A \subset N$ that has $0$ and has the property that if $n \in A$ then $n+1 \in A$ then $A$ must be $\mathbb N$. In other words $\mathbb N$ has no proper subsets wit the induction property.

Okay.. this throws a real damper on things. For all those sets I mentioned above " $[0,\infty)$ and $\mathbb Q^{\ge 0}$ and even a bizarre $\mathbb R - ${negative integers}" as well as {0, 1/2, 1, 1 1/2, 2,...}, we can easily find proper subsets with the induction property.

Ex: Let $\mathbb N = \mathbb Q^{\ge 0}$. Let $A = \mathbb Q^{\ge 0}- {1/2}$. That satisfies the induction property. But $A \ne \mathbb Q^{\ge 0}$. So $\mathbb N \ne \mathbb Q^{\ge 0}$.

Or $\mathbb R - ${negative integers}$ -\{\pi \pm k| k \in \mathbb Z\} \subset \mathbb R - ${negative integers} has induction property but is a proper subset so $\mathbb N \ne \mathbb R - ${negative integers}$ -\{\pi \pm k| k \in \mathbb Z\}$

Basically we've got $\mathbb N$ to be boiled down to the "smallest" possible set satisfying axioms 1- 4. Axiom 5) is a formal way of saying "smallest".

It seems to me the natural question to ask is do the axioms require that any possible set satisfying the five axioms must be unique. The answer to that is yes, it does.

If $\mathbb N'$ and $\mathbb N"$ both satisfy axioms 1 - 5 then let $A =\mathbb N' \cap \mathbb N"$. $0 \in A$ and if $n \in A$ then $n + 1 \in A$. So by axiom 5, $A = \mathbb N'$ and $A = \mathbb N"$ so $\mathbb N' = \mathbb N"$.

So the axioms 1- 5 uniquely define $\mathbb N$.