# Why does induction have to be an axiom?

I noticed that there is an axiom that says that if $S(n)\implies S(n+1)$, and $S(1)$ is true, then $\forall n \in \Bbb N, S(n).$

My question is why is this an axiom? why can't we derive this from the other axioms?

• Google Search the Peano Postulates – JohnColtraneisJC Jun 12 '18 at 16:20
• Depends on what other axioms you have ... are you thinking of a specific set of 'other axioms'? – Bram28 Jun 12 '18 at 16:23
• We can derive it, if our other axioms include Well Ordering. It's just up to us to decide whether we want to deduce this from that, or that from this. – user1390 Jun 12 '18 at 16:29
• Possible duplicate of Why is induction an axiom? – Bhavin Chirag Jun 13 '18 at 8:16
• Sure, it seems so obvious logically if you already have the naturals. Note that if you're talking about a subset of the Peano axioms, you don't have $\Bbb{N}$ yet to refer to. – Mitch Jun 13 '18 at 14:35

If you're looking at the Peano axioms for Arithmetic, and by 'the other axioms' you mean:

$1. \bf{\forall x \ \neg s(x) = 0}$

$2. \bf{\forall x \forall y (s(x) = s(y) \rightarrow x = y)}$

$3. \bf{\forall x \ x+0=x}$

$4. \bf{\forall x \forall y \ x+s(y)=s(x+y)}$

$5. \bf{\forall x \ x\cdot0=0}$

$6. \bf{\forall x \forall y \ x\cdot s(y)=(x \cdot y) + x}$

then no, we can't derive the axiom of induction, which I'll formalize as:

$\bf{(S(0) \land \forall x (S(x) \rightarrow S(s(x))))\rightarrow \forall x \ S(x)}$ (I include $0$ in $\mathbb{N}$, so base is $\bf{S(0)}$)

Here is a counterexample:

Take $\bf{S(x): s(x) \not = x}$

By axiom $1$, we have $\bf{\neg s(0)=0}$, and hence we have $\bf{S(0)}$

Also, if we have $\bf{S(k)}$, i.e. if we have $\bf{s(k) \not = k}$, then if it would be true $\bf{s(s(k)) = s(k)}$, then by Axiom 2 we have $\bf{s(k)=k}$, which contradicts $\bf{S(k)}$, and so we have $\bf{s(s(k)) \not = s(k)}$, i.e. $\bf{S(s(k))}$

OK, so with this $S(x)$, we have $\bf{S(0) \land \forall x (S(x) \rightarrow S(s(x)))}$ simply by virtue of Axioms 1 and 2 alone.

But, we do not necessarily have $\bf{\forall x \ S(x)}$

Consider a model with domain $\mathbb{N} \cup \{ q \}$, i.e. the natural numbers together with some 'extra' element $q$.

Interpret the $\bf{0}$ constant symbol as $0$

Interpret the $\bf{s}$ function symbol as a function $f$ for which $f(n)=n+1$ for any $n \in \mathbb{N}$, and for which $f(q)=q$

Interpret the $\bf{+}$ function symbol as a function $g$ for which $g(m,n)=m+n$ and $g(m,q)=g(q,n)=g(q,q)=q$ for any $m,n \in \mathbb{N}$

Interpret the $\bf{\cdot}$ function symbol as a function $h$ for which $h(m,n)=m\cdot n$ for any $m,n \in \mathbb{N}$, for which $h(0,q)=h(q,0)=0$, and for which $h(m,q)=h(q,n)=h(q,q)=q$ for any $m, n \in \mathbb{N}\setminus \{ 0 \}$

Then it is easily verified that all $6$ axioms are satisfied, and hence under this interpretation it is true that $\bf{S(0) \land \forall x (S(x) \rightarrow S(s(x)))}$. But, since $f(q)=q$, it is false that $\bf{\forall x \ s(x) \not = x}$. Hence, it is false that $\bf{S(0) \land \forall x (S(x) \rightarrow S(s(x))))\rightarrow \forall x \ S(x)}$, i.e. the axiom of induction would not hold under this interpretation. Therefore, the axiom of Induction does not follow from axioms $1$ through $6$.

• Minor detail: I think you want $h(q,0) = 0$ (as you wrote) but $h(q,\cdot) = h(\cdot ,q) = q$ for any other choice. (And the choice of $h(0,q)$ is actually irrelevant: $h(0,q) = h(0,S(q)) = h(0,q) + 0$ is the only axiom to worry about, and is true regardless of the value of $h(0,q)$.) – Jason DeVito Jun 12 '18 at 19:54
• @JasonDeVito Yes, that was a typo, thanks! And you're right, you can set $h(0,q)$ to anything, so I might as well save some typing by setting it to $0$ (which will save commutation as well) – Bram28 Jun 12 '18 at 20:17
• Nitpick: I think we need to state $h(q,q)=q$, as already done for $g(q,q)=q$. – chi Jun 13 '18 at 16:52
• @chi Quite! I'll add that, thanks! – Bram28 Jun 13 '18 at 17:04

The Peano Postulates describe what we want the natural numbers to look like. One thing we want is for the natural numbers to be one continuous stream

0, 1, 2, 3, ...


and not made up of several infinite sequences like

0, 1, 2, 3, ..., 0', 1', 2', ...


where every number has a successor and arithmetic works fine, but if you start counting somewhere in the first sequence you'll never arrive at any number in the second (primed) sequence.

The induction axiom forbids this situation by saying that for every number N, if you start counting from 0 you'll eventually reach N.

• But nonstandard models of PA exist which contain numbers which can't be so reached. – John Coleman Jun 13 '18 at 13:48
• @JohnColeman Because the axiom of induction is not a first-order axiom, but a second-order one. Nonstandard models of PA are only elementary-equivalent to PA, not isomorphic. In other words - the axiom of induction indeed doesn't hold in nonstandard models. – Itai Jun 19 '18 at 11:08
• @Itai There are two flavors of PA. One has a second order axiom of induction (which quantifies over sets) and the other a first order axiom schema of induction (in terms of predicates). OP isn't sufficiently precise to be sure, but their formulation in terms of $S(n)$ seems closer to the first order formulation than the second order formulation. – John Coleman Jun 19 '18 at 11:47
• As I understand it though, nonstandard models refer to models of all axioms except the axiom (or axiom schema) of induction, so I'm not entirely sure what you meant by the original comment. It seems you are saying the same thing as is said in this answer, namely - "the axiom (or axiom schema) of induction is required so we can tell apart the standard model from nonstandard ones"... – Itai Jun 19 '18 at 11:59
• @Itai Nonstandard models of PA satisfy the axiom schema of induction. Perhaps you are thinking of Robinson Arithmetic. – John Coleman Jun 19 '18 at 16:20

Ultimately the way we prove (usually) that a given axiom $\alpha$ isn't already a consequence of a set of axioms $T$ is by constructing a model (I've linked to a formal definition, but you should skip it at first read - just think of a model informally, as "a thing satisfying the axioms") of $T$ in which $\alpha$ fails. The most famous example of this is the parallel postulate, which was proved to be independent of the remaining postulates of Euclid via the construction of non-Euclidean geometries.$^1$

Now in our case - I presume you're talking about the theory PA - our theory has two parts:

• An "algebraic" part, asserting that the natural numbers form a discrete ordered semiring.

• The induction axioms (a "set-theoretic" part).

It's not trivial to construct a model of the former in which the latter can fail, but they exist; see e.g. here or here.

(Incidentally, once we include induction it becomes very difficult to construct models other than the usual one - we can see this, for example, in Tennenbaum's theorem. With Tennenbaum in mind, we actually have a very easy recipe for cooking up discrete ordered semirings where induction fails: simply pick any "easily describable" discrete ordered semiring not isomorphic to $\mathbb{N}$!)

$^1$I don't want to give the wrong impression here: independence results can be extremely difficult to establish, since the more complicated a theory is the harder its models are to describe in general. For example, at a much more advanced level this is also how we show that the continuum hypothesis is independent of the usual axioms of set theory, assuming the latter are consistent of course. Godel constructed the inner model $L$ and showed that it satisfied CH; later, Cohen developed forcing and showed that it could produce models where CH fails (as well as models where CH holds, but the former is more impressive: besides being the remaining missing piece, one consequence of Godel's work was that establishing the consistency of the failure of CH is in a precise sense harder than establishing the consistency of CH). However, unlike non-Euclidean geometry and slightly unusual discrete ordered semirings, models of set theory are hideously complicated and there's no good way to describe these results without lots of technical work.

It is maybe helpful to think in terms of formal proofs. For each particular $n$, a formal proof of $S(n)$ looks something like this:

\begin{align*} S(1), S(1) &\implies S(2)\\ S(2), S(2) &\implies S(3)\\ &\vdots \\ S(n-1), S(n) &\implies S(n) \end{align*}

which we use modus ponens to go from each line to the next, and $S(i) \implies S(i+1)$ is short-hand for a formal proof of this statement, using the other (non-inductive) axioms in your chosen system.

But although we can give a formal proof of $S(n)$ for each $n \in \mathbb{N}$, there is nothing above that comes close to a formal proof of the formula $(\forall n \in \mathbb{N}) S(n)$.

To put it another way: formal proofs are finite objects, so there is no sense in which we can 'roll-up' the proofs for each particular $n$ into a single formal proof dealing with all $n$ at once. Instead we need the axiom of induction.

The short answer is that without an axiom, there is a difference between

$$\text{You can have as many apples as you want.^*}$$ and $$\text{You can have infinitely many apples.}$$

$^*$$\scriptsize\text{(finite amount implied)}$

• Even with induction, there is a difference between those things. Van der Waerden's theorem is a good example; we can prove (by induction!) that in any finite coloring of the naturals, there are arithmetic progressions as large as you want; but there are not necessarily infinite arithmetic progressions. – Misha Lavrov Jun 13 '18 at 0:37
• @MishaLavrov This is absolutely true, but I wanted a short and intuitive answer. In the end, it is definitely not perfect. I am still thinking of a better way to put it. – Arnaud Mortier Jun 13 '18 at 0:40