Why does induction have to be an axiom?

wub 06/12/2018. 5 answers, 933 views
induction axioms peano-axioms

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?

5 Answers

Bram28 06/12/2018.

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)=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$.

Noah Schweber 06/12/2018.

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.

I. J. Kennedy 06/12/2018.

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.

Arnaud Mortier 06/12/2018.

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)}$

Mark Wildon 06/12/2018.

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.

HighResolutionMusic.com - Download Hi-Res Songs

1 Martin Garrix

Yottabyte flac

Martin Garrix. 2018. Writer: Martin Garrix.
2 Alan Walker

Diamond Heart flac

Alan Walker. 2018. Writer: Alan Walker;Sophia Somajo;Mood Melodies;James Njie;Thomas Troelsen;Kristoffer Haugan;Edvard Normann;Anders Froen;Gunnar Greve;Yann Bargain;Victor Verpillat;Fredrik Borch Olsen.
3 Sia

I'm Still Here flac

Sia. 2018. Writer: Sia.
4 Blinders

Breach (Walk Alone) flac

Blinders. 2018. Writer: Dewain Whitmore;Ilsey Juber;Blinders;Martin Garrix.
5 Dyro

Latency flac

Dyro. 2018. Writer: Martin Garrix;Dyro.
6 Cardi B

Taki Taki flac

Cardi B. 2018. Writer: Bava;Juan Vasquez;Vicente Saavedra;Jordan Thorpe;DJ Snake;Ozuna;Cardi B;Selena Gomez.
7 Bradley Cooper

Shallow flac

Bradley Cooper. 2018. Writer: Andrew Wyatt;Anthony Rossomando;Mark Ronson;Lady Gaga.
8 Halsey

Without Me flac

Halsey. 2018. Writer: Halsey;Delacey;Louis Bell;Amy Allen;Justin Timberlake;Timbaland;Scott Storch.
9 Lady Gaga

I'll Never Love Again flac

Lady Gaga. 2018. Writer: Benjamin Rice;Lady Gaga.
10 Kelsea Ballerini

This Feeling flac

Kelsea Ballerini. 2018. Writer: Andrew Taggart;Alex Pall;Emily Warren.
11 Mako

Rise flac

Mako. 2018. Writer: Riot Music Team;Mako;Justin Tranter.
12 Dewain Whitmore

Burn Out flac

Dewain Whitmore. 2018. Writer: Dewain Whitmore;Ilsey Juber;Emilio Behr;Martijn Garritsen.
13 Bradley Cooper

Always Remember Us This Way flac

Bradley Cooper. 2018. Writer: Lady Gaga;Dave Cobb.
14 Little Mix

Woman Like Me flac

Little Mix. 2018. Writer: Nicki Minaj;Steve Mac;Ed Sheeran;Jess Glynne.
15 Charli XCX

1999 flac

Charli XCX. 2018. Writer: Charli XCX;Troye Sivan;Leland;Oscar Holter;Noonie Bao.
16 Rita Ora

Let You Love Me flac

Rita Ora. 2018. Writer: Rita Ora.
17 Diplo

Electricity flac

Diplo. 2018. Writer: Diplo;Mark Ronson;Picard Brothers;Wynter Gordon;Romy Madley Croft;Florence Welch.
18 Jonas Blue

Polaroid flac

Jonas Blue. 2018. Writer: Jonas Blue;Liam Payne;Lennon Stella.
19 Lady Gaga

Look What I Found flac

Lady Gaga. 2018. Writer: DJ White Shadow;Nick Monson;Mark Nilan Jr;Lady Gaga.
20 Avril Lavigne

Head Above Water flac

Avril Lavigne. 2018. Writer: Stephan Moccio;Travis Clark;Avril Lavigne.

Related questions

Hot questions


Popular Tags