Peano axioms induction

Question

I am deriving the natural numbers with the Peano Axioms and have a question about the Axiom of mathematical induction. I am having trouble grasping the significance of Peanos formulation of this Axiom. For example I cannot see a difference between Peanos Axiom and the formulation:"If n is a natural number it can be reached by repeated incrementation starting from 0".

Answer 1

"If n is a natural number it can be reached by repeated incrementation starting from 0" is meaningfully different from the Peano Axiom of Induction. The Peano Axiom is not just about "is reachable" but is about any property. For example, "$x\geq 0$" is a property that we can use with the axiom of induction.

Answer 2

The induction axiom can be formally stated as follows:

$\forall P\subset N: [0\in P \land \forall x\in P:[S(x) \in P] \implies P=N]$

Let $M$ be the subset of $N$ comprised of those and only those elements of $N$ that can be reached by repeated incrementation starting from $0$.

$M=\{0, S(0), S(S(0)), \cdots \}$

In other words, $M$ is smallest subset of $N$ such that $0\in M$ and for all $x\in M$, we also have $S(x)\in M$.

More formally:

$\forall a:[a\in M \iff a\in N \land \forall Q\subset N: [0\in Q \land \forall b\in Q: [S(b)\in Q] \implies a\in Q]]$

From the axioms of set theory, we know that this subset of $N$ will exist.

It is then a simple exercise to prove using the induction axiom that, for all $x\in N$ we also have $x\in M$.

---

EDIT 1: The converse is also true, so you are correct. They are indeed equivalent. Formal proof to follow.

---

EDIT 2: See machine-verified, formal proof (136 lines) as promised.

Theorem: Suppose we have a set $n$ (finte or otherwise), a function $s: n \to n$ and $n_0 \in n$. Then induction will hold on set $n$ with successor function $s$ and "first" element $n_0$ if and only if all elements of $n$ are reachable by repeated succession starting at $n_0$, i.e. the set $m = \{n_0, s(n_0), s(s(n_0)), ... \}$ contains every element of $n$.

More formally:

$\forall n,n_0,s:[n_0\in n \land s: n\to n\\\implies[\forall a\subset n:[n_0\in a \land \forall b\in a: [s(b)\in a] \implies n\subset a]\\\iff \exists m:[\forall a: [a\in m \iff a\in n \\\land \forall b\subset n:[n_0\in b \land \forall c\in b:[s(c)\in b]\implies a\in b]]]\\\land n\subset m]]$

Answer 3

One issue is that the statement

A: "If n is a natural number it can be reached by repeated incrementation starting from 0"

seems to be trivially true: if $n>0$ is a natural number, then $n$ should be reachable by adding $1$ to itself $n$ times. This does not tell us about whether other properties are maintained as we move upward through the set of naturals.

When we formalize the induction axioms in Peano arithmetic, the statement

B: "If $n>0$ is a natural number it can be reached by adding $1$ to itself $n-1$ times"

is just one consequence of the induction axioms. It is known that the entire set of induction axioms in Peano Arithmetic is not only infinite, but it is not implied by any of its finite subsets. So there are other, more complicated induction axioms that are not implied by $B$ alone; we need to include the entire set of induction axioms to get the full strength of PA.

On the other hand, the intuition that statement A should be true is one of the motivations for the other induction axioms: it helps us see why we might expect them to be true.

Statements $A$ and $B$ have interesting behavior in the context of nonstandard models. Although a nonstandard model of Peano Arithmetic will think that each nonstandard element $n$ can be reached by repeatedly adding $1$ to itself, the number of times that $1$ must be added to itself will also be nonstandard when $n$ is. Somewhat by definition, there is no way to reach a nonstandard number by adding 1 to itself a standard number of times.