37
$\begingroup$

What makes induction (over natural numbers) a valid proof technique? Is $$ \dfrac{ P(0) \quad \forall i \in \mathbb{N}. P(i) \Rightarrow P(i+1) }{ \forall n \in \mathbb{N}. P(n)} $$ just taken for granted as a proof rule, or can it be derived from more foundational axioms?

Similarly, can the principle of induction over well-founded sets be derived from something more foundational, or does it have to be assumed to be a valid inference rule?

$\endgroup$
6
  • 4
    $\begingroup$ It follows from well-ordering. $\endgroup$ – user61527 Jul 16 '14 at 18:23
  • 8
    $\begingroup$ In number theory induction is a axiom (or proof rule); in set-theory it can be proved (form set axioms, of course). $\endgroup$ – Mauro ALLEGRANZA Jul 16 '14 at 18:30
  • $\begingroup$ @T.Bongers: small point here, but beside well-ordering, we also need that natural number do not have infinity. If there is, then we will have to use something weaker than induction, namely "strong" induction. $\endgroup$ – Gina Jul 16 '14 at 19:03
  • 4
    $\begingroup$ @MauroALLEGRANZA I'd be more inclined to say that in set theory, induction holds by the definition of $\mathbb N$. I typed that before reading Qiaochu Yuan's answer, so I guess I'm saying I'm more in agreement with his way of viewing it. $\endgroup$ – Dustan Levenstein Aug 19 '14 at 18:37
  • 1
    $\begingroup$ possible duplicate of We all use mathematical induction to prove results, but is there a proof of mathematical induction itself? $\endgroup$ – Alex M. Sep 2 '15 at 10:55
22
$\begingroup$

There is a property of the natural numbers called "well-ordering". It says that any non-empty subset of $\mathbb{N}$ has a smallest element. We can use this to prove induction.

Let $S = \{ n \in \mathbb{N} \mid \lnot P(n) \}$. Assume it is non-empty. Then there is a least element; call it $k$. Since $P(1)$ is true, we know that $k \ne 1$. Therefore*, $k > 1$, so $k - 1 \in \mathbb{N}$. But since $k - 1$ is less than $k$, which was the minimum element of $S$, we know $k - 1 \notin S$. Therefore, $P(k - 1)$ is true. But our other hypothesis tells us that $P(k - 1 + 1) = P(k)$ is also true. This is a contradiction, so our assumption that $S$ was non-empty must be false. This means that $P(n)$ is true for all $n \in \mathbb{N}$.

The proof for transfinite induction on a well-ordered set is nearly identical. The only difference is that once you have $k$, you state all elements less than $k$ satisfy $P$, not just $k - 1$. But that is exactly your inductive hypothesis, so you get the desired contradiction.

*We haven't shown that all natural numbers are $\ge 1$, but that can also be shown with well-ordering. Briefly: Take the set of all $n$ such that ($0 < n < 1$). Assume it's non-empty. We take the smallest element, $k$, and square it to make a smaller one. Since $0 < k^2 < 1$, this contradicts the minimality of $k$. Therefore, that set is empty, and there are no natural numbers less than $1$.

$\endgroup$
8
  • $\begingroup$ And how do you show that $k^2<k$ if $0<k<1$? $\endgroup$ – celtschk Jul 16 '14 at 22:13
  • 1
    $\begingroup$ Let $a > b$ and $c > 0$. Both $a - b$ and $c$ are natural numbers, so their product, $ac - bc$, is as well. But that means $ac > bc$. That lemma lets you show $k < 1 \implies k^2 < k$. The fact that $k^2 > 0$ comes from $\mathbb{N}$ being closed under multiplication. $\endgroup$ – Henry Swanson Jul 16 '14 at 22:35
  • 10
    $\begingroup$ One can, of course, even prove that well-ordering and induction are equivalent. That in some sense doesn't resolve the question because now one can still ask: "what makes well-ordering a valid proof technique?" I guess in practice people find well-ordering more intuitive than induction so maybe the point is moot, but philosophically the issue is unresolved. $\endgroup$ – Qiaochu Yuan Jul 17 '14 at 18:16
  • $\begingroup$ Just want to point out that OP uses P(0) as starting point, not P(1). Doesn't matter, of course. $\endgroup$ – Nikolaj-K Aug 19 '14 at 18:40
  • 2
    $\begingroup$ I'm curious how you prove $k - 1 \in \mathbb N$ without induction (actually rigorous prove, not just "know by intuition") $\endgroup$ – DanielV Aug 21 '14 at 20:52
56
$\begingroup$

One point of view is that "the natural numbers satisfy induction" is part of what we mean when we're talking about the natural numbers; that is, part of the definition of "the natural numbers" should be "those things that satisfy induction." This is just a slightly more sophisticated version of "the natural numbers are what you get when you start with $1$, then add $1$ to it, then add $1$ to it, then..."

If someone tells you that badgers are white, 200 feet tall, and glow in the dark, they're not even wrong about badgers: whatever they mean by badger, it isn't what you mean by badger. Similarly, if someone tells you that the natural numbers don't satisfy induction and also include $-3$ and $\frac{5}{7}$, then they're not even wrong about the natural numbers: whatever they mean by natural number, it isn't what you mean by natural number.

People think of axioms as laws you have to follow or true things you have to assume and I think neither of these perspectives is correct. It's more accurate to think of axioms as a way to agree that we're talking about the same thing.

$\endgroup$
5
  • 31
    $\begingroup$ The last paragraph deserves a medal. +1 $\endgroup$ – goblin GONE Jul 16 '14 at 19:27
  • 3
    $\begingroup$ Hadn't considered this before reading your answer, but proof by induction works not only for natural numbers but also for the set of all natural numbers plus $1/2$. Or plus any arbitrary constant. Natural numbers get special attention, but what really makes it all work is that $+1$ business. Or even more generally, inductive proofs work for all sets defined by iterative application of a successor function. Is that what qualifies, in general, as an inductive set definition? $\endgroup$ – Keen Jul 16 '14 at 20:30
  • 6
    $\begingroup$ @Cory: yes. In the language that I'm happiest with (the language of category theory), the natural numbers have a universal property: they are the universal thing you get by repeatedly applying something like a successor function. $\endgroup$ – Qiaochu Yuan Jul 16 '14 at 20:32
  • $\begingroup$ (One way of making this precise: ncatlab.org/nlab/show/natural+numbers+object) $\endgroup$ – Qiaochu Yuan Jul 17 '14 at 0:32
  • $\begingroup$ This is important. I also like the Model Theoretic view where axioms give rise to structure and in some sense define structures into existence. You say "I want axioms $A$ to hold" and you pull out the Model Existence Theorem and it creates for you a structure in which $A$ holds. $\endgroup$ – Stella Biderman Mar 31 '17 at 15:29
6
$\begingroup$

I'll try to give a "philosophical" answer:

If you take the so-called "Platonic" viewpoint which many mathematicians seem to share more or less, then mathematics is something which exists in some realm outside of us and can be "examined" by our minds. From this point of view the natural numbers are a reality that everybody experiences in the same way and induction is something that's "obviously true" about them. (Or, in other words, you have to "believe" it.)

If, on the other hand, you take a more formalist point of view and adhere to Bertrand Russell's claim that mathematics is essentially a collection of statements of the form $A \Rightarrow B$, then before you start investigating a subject you try to find a couple of axioms that describe your subject as concisely as possible. If you do it this way, then the principle of induction (or something which is equivalent to it) is essentially always an axiom, i.e. something that can't be proved.

One set of axioms that can in principle be used as a basis for almost all of mathematics (and is what you normally use without thinking about it unless you are either an ultrafinitist or working on foundations) is ZFC which includes an "axiom of infinity" from which the existence (!) of the set of natural numbers and then the principle of induction can be derived.

In some areas of mathematical logic you're specifically interested in "weaker" axiom systems to see what you can (and what you can't) prove with them alone. This is were systems like the Dedekind-Peano axioms (also of great historical interest) come into play which also include an axiom (or sometimes a whole schema of axioms) for induction.

Or, to put it more strikingly: The principle of induction says something about infinitely many objects which means that you can neither prove nor "check" it with finite means (and that's all we mere mortals can do). The only way to "prove" it is to fall back to some other proposition about infinitely many objects which again can't be proved.

$\endgroup$
3
$\begingroup$

In Peano arithmetic, induction is an axiom schema: your proof technique is simply $a, (a \implies b) \vdash b$, where the hypothesis of your proof technique is $a$, and $(a \implies b)$ is an instance of the induction schema.

$\endgroup$
3
  • 1
    $\begingroup$ Are you sure you aren't referring to Modus Ponens? $\endgroup$ – DanielV Aug 21 '14 at 20:55
  • $\begingroup$ This is wrong. Yes Modus Ponens holds, however there are sets for which $P(x)$ holds and $P(x)\Rightarrow P(x+1)$ holds and yet it is not the case that $P$ holds for every number. The real numbers are such a set. $\endgroup$ – Stella Biderman Mar 31 '17 at 15:31
  • $\begingroup$ @StellaBiderman: I don't see how it's wrong. The real numbers don't satisfy the Peano axioms, so there's no reason to expect the instance ($\left( P(0) \wedge \forall x: P(x) \implies P(x+1) \right) \implies \left( \forall x: P(x) \right)$) of the induction schema to be an axiom. Without establishing this implication, one cannot use Modus Ponens to infer $\forall x: P(x)$ if you also know $P(0) \wedge \forall x: P(x) \implies P(x+1) $. $\endgroup$ – user14972 Mar 31 '17 at 21:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.