Peano axioms - do we need a specific property to show that the principle of mathematical induction implies the "correct" set of natural numbers?

60 Views Asked by At

From Terence Tao's Analysis I, Axiom 2.5 for the natural numbers reads

enter image description here

My intuition behind this axiom is that every natural number is an element of a "chain" of natural numbers that goes back to $0$ and is built by successively applying the successor function to elements of it. This axiom then prohibits the existence of a "parallel chain" that runs outside of the "main" one, which contains $0$.

My question is: to prove that this axiom does indeed imply the existence of only this, one, correct, "chain" that starts at $0$, must we produce a specific property that shows this to be the case, or is it possible to prove this implication without alluding to any specific property, by directly using the fact that any property must satisfy the axiom? My question isn't whether we can find such a property; it might even be a very immediate one, but whether we must explicitly invoke it to prove the implication.

My mind keeps going back and forth on this one, and I can't pinpoint why.

2

There are 2 best solutions below

3
On

I'm not sure what you mean by a "parallel chain." But I often find it useful to think of induction using the well ordering principle. Suppose you have some property $P$ that satisfies Axiom $2.5$. Let's also assume (toward a contradiction) that there's some natural number $n$ for which $P(n)$ fails. Then the set $C=\{ k \in \Bbb N \mid \lnot P(k) \}$ would be a non-empty set of natural numbers.

Since $C \neq \varnothing$, the well ordering principle tells us that $C$ would therefore have to have a least element $k$. We know that $k$ can't be $0$ because we're told that $P(0)$ holds. Therefore, $k=n+1$ for some $n \in \Bbb N$. But our assumption that $k=n+1$ is the least element of $C$ means that $n \notin C$, which in turn means that $P(n)$ holds. But if $P(n)$ holds, then Axiom $2.5$ tells us that $P(k)$ (which is $P(n+1)$) also holds, so $k=n+1$ isn't a member of $C$ after all. That's a contradiction.

Our initial assumption that $C$ is non-empty must therefore be false, so $P(n)$ must hold for all natural numbers $n$.

2
On

The Peano axioms include the induction axiom but are not sufficient to prove that there are no numbers outside the set you can access from $0$ with the successor function. The induction guarantees that any statement true about all the naturals you can access with the successor function, which we call standard naturals, is true about all the numbers. In fact, the nonstandard naturals, if they exist, are greater than any standard natural, so any statement true about all large enough standard naturals is also true about all the nonstandard ones.