Why does induction only allow numbers connected to $0$ to be natural?

Question

When learning Peano axioms normally we use induction to suggest that if a property $P(0)$ is true, and if $P(k)$ being true implies $P(k + 1)$ being true (for natural number $k$), then if $P$ is the property of being a natural number, we start with $0$ being a natural number by definition, then by induction $1$ is a natural number, $2$ is a natural number, $3$ is a natural number, etc.

This is done to prohibit things like $5.3$ or $\pi$ from being natural since they are not reachable when applying the successor function from $0$.

But what I don't understand:

1. Just because we can point to the $0, 1, 2, 3, ...$ chain as being natural numbers, what stops us from making some other chain and calling them natural numbers?

2. If your answer to #1 is "Well we never provided a mechanism for saying that they were natural numbers to begin with" then what was the "risk" or issue if they posed no threat? Why do we have to specifically label the stuff connected to $0$ as natural numbers when it's more or less implied that the rules we're setting up are specifically for defining what rules natural numbers follow?

Answer 1

Just because we can point to the 0,1,2,3,... chain as being natural numbers, what stops us from making some other chain and calling them natural numbers?

Absolutely nothing stops you from doing this, and indeed you can. This is the idea of non-standard models of arithmetic.

Peano arithmetic can prove, for instance, that the numbers 0,1,2,3,... exist, and for instance, that the only numbers less than 3 are 0, 1, 2. So if you want the Peano axioms to hold, your "chain" has to start out with 0,1,2,3,... without any other numbers in between.

(When I write something like "2" here, I just mean "the number that is the successor of the successor of 0". You can give these numbers different symbols if you like, and think of the chain as starting out $0, q, \text{fish}, \dots$ but that won't really make it a different chain.)

However, there might possibly be additional numbers that come after this initial chain; Peano arithmetic can't prove that there aren't (assuming it's consistent), and so tacking on such numbers will not introduce any inconsistencies, so long as it's done in a careful way to make sure the additional "infinitely large" numbers still satisfy the Peano axioms.

Answer 2

Induction does not specifically "prohibit" you from using $\pi$. It's pretty flexible.

For example, I could do an induction proof which goes like this.

First, I prove that $P(\pi)$ is true.

Next, I prove that if $P(x)$ is true then $P(x+1)$ is true.

From this, I can conclude that all of the statements $P(\pi)$, $P(\pi+1)$, $P(\pi+2)$, $P(\pi+3)$,... are true. In other words, $P(\pi+n)$ is true for every natural number $n$.

The proof is easy: just prove the statement $Q(x)=P(x-\pi)$ using ordinary induction on the natural numbers.

Answer 3

You can use induction on any chain that has the same structure as $\mathbb N$ has; for example this silly example is perfectly valid:

Suppose some set $A\subseteq \mathbb C$ has the properties that

• $\frac12+\frac12i\in A$

• $\forall z\in\mathbb C: z\in A \to (z+1+i)\in A$

Then $A$ contains all complex numbers that have the same real and imaginary part, when that common real imaginary part is a positive half-integer.

The natural numbers (with or without $0$ is your choice) is the prototypical example of this -- the one we think we understand intuitively well enough to accept the principle as true. And it's reasonably easy to prove (in mainstream set theory) that every set where a principle is valid must be in bijective correspondence with $\mathbb N$ in a way that preserves the base case ($0$ or $1$, as appropriate, in the case of $\mathbb N$) and the successor relation -- so they do have the same structure.

You could, if you wanted, declare that the set of complex numbers with identical positive half-integer real and imaginary part are your "new $\mathbb N$" and develop the rest of mathematics on top of that (if you can live with ignoring how arithmetic on your original complex numbers worked, and defining a "new $\mathbb C$" later in the process). But you wouldn't get very much out of it, so people generally don't go around doing that.

Less flippantly, you could also decide to use different natural numbers than the ones the common set theory textbooks use. For example, Zermelo originally used $$ \{\}, \{\{\}\}, \{\{\{\}\}\}, \{\{\{\{\}\}\}\}, \ldots $$ as his natural numbers -- and that still works fine if you want to, except that the usual Von Neumann representation works even better (in the sense that some further definitions become easier to state).

Answer 4

What stops us from making some other chain and calling them natural numbers?

One answer to this question is... nothing! You can take any set you like, call any element you like zero, and take any function from that set to itself to be the successor function, and as long as it obeys all the Peano axioms (using the stronger form of induction where it works on any subset and not just those properties we can write down) you're well within your rights to use that as your natural numbers.

Of course, requiring them to obey all the Peano axioms does restrict your choice quite a lot.

In fact, it's enough of a restriction that it forces the set you've constructed to be isomorphic to the natural numbers. This is because we can construct a function $f$ from $\mathbb{N}$ to your set by setting $f(0)$ as the zero you picked for your set and setting $f(n+1)$ to be the successor to $f(n)$ and then show that $f$ is bijective. (This is quite a good exercise, actually. You need to show that the function is defined on all of $\mathbb{N}$ and that it is injective and surjective, each time using a carefully chosen induction argument.)

This bijection $f$ means that we can take any question about your set, translate it into a question about $\mathbb{N}$, and answer it in the standard natural numbers. Therefore, both sets will work the exact same way.

In particular, suppose you've chosen to label some element of your set of naturals with the label $\pi$. It isn't going to have the properties that we normally think of the number $\pi$ as having: for instance, it's not going to be between $3$ and $4$ (or rather, $S(S(S(0)))$ and $S(S(S(S(0))))$) because in the natural numbers no elements are between $3$ and $4$. Instead, the element you've labelled $\pi$ is going to be $S(S(.....S(0)$ for some finite number of applications of the successor function, and it will have all the properties of that natural number.

That's the sense in which numbers like $\pi$ aren't natural numbers.

Answer 5

What stops us from making some other chain and calling them natural numbers?

Indeed, nothing stops us. Let's consider it from an algebraic perspective. Define a Peano algebra to be a free $\rm P$-algebra on zero generators, where $\rm\,P\,$ is an algebra class comprised of one nullary operation (the constant $0)$ and one unary operation (the successor $\rm S),\,$ and no axioms. Thus a Peano algebra consists of terms $\rm 0,\, S\:\!0, S^2\:\!0,\ldots$ and freeness implies that no two terms are equal.

One advantage of this viewpoint is we can apply general results from the theory of free algebras, e.g. definition by induction (recursion) is available; Peano algebras are unique up to isomorphism, etc. Many algebra textbooks present this viewpoint, e.g. Paul Cohn's Universal Algebra, Ch. VII.1.

Answer 6

From any any Dedekind-infinite set set, you extract a subset that satisfies Peano's Axioms.

Proof sketch: Let $X$ be any Dedekind-infinite set, i.e. there exists a function $f: X \to X$ that is injective, but not surjective. Since $f$ is not surjective, we must have $x_0 \in X$ such that for all $y \in X$, we have $f(y)\neq x_0$.

Then there exists $N\subset X$ such that

$$N=\{x_0, f(x_0), f(f(x_0)), \cdots \}$$

and the algebraic structure $(N,f,x_0)$ will satisfy each of the Peano Axioms where $f$ is the successor function, and $x_0$ in the first element of $N$.