45
$\begingroup$

Proofs that proceed by induction are almost always unsatisfying to me. They do not seem to deepen understanding, I would describe something that is true by induction as being "true by a technicality". Of course, the axiom of induction is required to pin down the Natural numbers and certainly seem to be indispensable in one form or another.

However, I am still interested in the following: Are there any "natural" theorems in mathematics that seem unlikely to fall to any method other than induction for whatever reason? I would not include examples that proceed by breaking down a structure into smaller components that are more easily handled - somehow these proofs satisfy whatever criteria for beauty I have in my mind.

An example of a theorem that does have an inductive proof and a more "superior" proof is Fermat's little theorem. It is perfectly possible to prove it by induction but the proof through group theory seems better - perhaps because it is more easily generalizable. I would like examples where it seems like the "neat" proof is unlikely to exist.

This is probably very philosophical and I do not really have a concrete question but I am sure I am not alone in feeling this way.

$\endgroup$
13
  • 25
    $\begingroup$ Induction is a defining property of integers (it's basically the axiom that says "and there are no more things that are integers"). So any nontrivial proof involving integers is going to either require induction directly, or it will require a (sometimes obvious) theorem that was proven using induction. $\endgroup$
    – DanielV
    Mar 21, 2015 at 20:45
  • 3
    $\begingroup$ Nearly every result in Ramsey Theory seems to be entirely reliant on induction. In particular, when dealing with large collections such as "all colorings of $[n]$ using $k$ colors" where we are unable to look at precisely how the terms are specifically colored. See my homework on Folkman's Theorem here $\endgroup$
    – JMoravitz
    Mar 21, 2015 at 20:50
  • 15
    $\begingroup$ You mention Fermat's little theorem proved with group theory; I'm afraid that the tools needed to prove it this way (the order of an element is a divisor of the order of the group) require induction (for being able to know the subgroups of the integers). Induction can very deeply hidden in what we're using. $\endgroup$
    – egreg
    Mar 21, 2015 at 22:25
  • 2
    $\begingroup$ @Asvin No, it's needed for showing that the subgroups of the integers are of the form $n\mathbb{Z}$ (or to show existence and uniqueness of division with remainder, which is the same). $\endgroup$
    – egreg
    Mar 22, 2015 at 10:30
  • 6
    $\begingroup$ @DanielV: I have to strongly disagree with that. I know of several important papers where the main result is proven by a (very nontrivial) inductive argument. $\endgroup$
    – Martin Argerami
    Mar 23, 2015 at 2:16

4 Answers 4

Reset to default
63
$\begingroup$

Write the axioms of number theory (called "Peano arithmetic," or "PA") as $P^-+\mathrm{Ind}$, where $P^-$ is the ordered semiring axioms (no induction), and $Ind$ is the axiom (scheme) of induction. Then a theorem requires some induction if it is not provable by $P^-$ alone - that is, if we can find a model of $P^-$ in which the theorem is not true.

So that lets us make a precise "Question 1:"

Question 1: Is there a "natural" theorem about natural numbers which requires some induction, in the sense above?

We can refine this. Let's suppose we want to draw a line between "simple" proofs by induction, and "hard" proofs by induction; we allow the former but are skeptical about the latter.

In this case, in the same way that we broke the axioms of number theory up into parts ($P^-$ and $Ind$), we now need to break $Ind$ up into smaller pieces. The usual way of doing this is via the arithmetical hierarchy: every formula in the language of arithmetic can be assigned a "level of complexity," and these levels are indexed by natural numbers. $Ind$ can now be written as $\mathrm{Ind}_1+\mathrm{Ind}_2+ \cdots$, where $Ind_n$ is induction for formulas of complexity $n$. Roughly speaking, a formula has complexity $n$ if it can be written with $n$ alternating blocks of quantifiers: e.g., the formula $$p(a)=\text{“ }\forall x\,\forall y\,\exists z\,\forall w\,(x+y+w<z+a)\text{ ''}$$ has complexity 3, since it has the form "$\forall\forall, \exists, \forall$." (I'm being very vague here, and this is slightly incorrect; but it won't cause any problems.)

So we have question 2:

Question 2: For each $n$, are there "natural" theorems about natural numbers which require $\mathrm{Ind}_n$?

Note that if a theorem requires $\mathrm{Ind}_n$, then it certainly requires some induction; so question 2 is a strengthening of question 1. By the way, this is of course not the only way to break up $\mathrm{Ind}$; there are lots of other ways to measure the complexity of an axiom of induction.

The answers to both questions are, spectacularly, YES; the general question, "How much induction do we need to prove $\varphi$?" is studied - along with similar questions - by the field Reverse Mathematics.

Some examples:

  • The statement "There are infinitely many primes" is not provable in $P^-$ alone; that is, it requires some induction. How much induction exactly? I don't think this is known, but the (very weak) level of induction called open induction is known to also not be enough.

  • Ramsey's theorem for pairs - the statement, "Any time I color pairs of natural numbers 'Red' or 'Blue,' I can find an infinite set of natural numbers, any pair from which is colored the same as any other pair" - requires some induction. Again, exactly how much is not known, but it's at least $\mathrm{Ind}_2$ - a small but substantial amount of induction. EDIT: I'm being somewhat sloppy here. Note that Ramsey's theorem isn't expressible in the language of number theory, so I need to look at a more expressive theory which can talk about such things; the theory used for this purpose is usually $RCA_0$, which corresponds in a particularly nice way to the first level of induction + the ability to talk about sets. See Simpson's book (mentioned below) for details on this.

  • A lot of algebraic statements, like "Every ring which is not a field, has a nontrivial proper ideal", actually require all the induction that $PA$ has to offer.

REFERENCES

Since there's a lot of stuff here, I don't have time to give a complete explanation - but here are some sources:

For basic logic, including Gödel's completeness theorem and what a "model" is, I'm a fan of Enderton's "A Mathematical Introduction to Logic" - but there are lots of books out there on the same subject, and any of them will do.

For the arithmetical hierarchy, this will be covered in any good logic textbook, but can also be found in a lot of books on theoretical computer science - I'm pretty sure it's in Arora/Barak, for example.

For reverse mathematics, this is trickier; there isn't really any readable introduction. The classic text is Simpson's "Subsystems of Second-Order Arithmetic," and chapter I is very nice and readable, but the rest is very hard.

$\endgroup$
11
  • 2
    $\begingroup$ I believe that most people around here (myself included) are non familiar with model theory. I assume that by ordered semiring axioms you mean this? It would be nice if you could expand on what you mean by "induction for formulas of complexity $n$" and if you could provide some references for further reading. $\endgroup$
    – A.P.
    Mar 21, 2015 at 22:18
  • 1
    $\begingroup$ Thanks, this answer exceeded my expectations. I will accept in a little while if no better answers come up. $\endgroup$
    – Asvin
    Mar 21, 2015 at 23:01
  • $\begingroup$ Can "open iduction" be somehow compared with any of the $Ind_n$? (Excellent answer, by the way) $\endgroup$
    – Hagen von Eitzen
    Mar 22, 2015 at 21:53
  • 1
    $\begingroup$ More than the answer, I am impressed at the clear, formal meaning you gave to the question. $\endgroup$
    – Erel Segal-Halevi
    Mar 23, 2015 at 9:43
  • 1
    $\begingroup$ @user21820 Whoops. :P The answer to your question is, you're exactly right! $PA$ can't prove Ramsey's theorem for pairs ($RT^2_2$) because it can't even express it. However, if we look at the first-order consequences of $RT^2_2$ - that is, the set of sentences in the language of arithmetic which are provable in the theory $RCA_0+RT^2_2$ - we find that these are all already consequences of $PA$. That is, $PA$ can't "see" $RT^2_2$, but $RT^2_2$ doesn't give you anything $PA$ can see that $PA$ can't already prove for itself. $\endgroup$
    – Noah Schweber
    Aug 31, 2016 at 13:52
5
$\begingroup$

How about the following: Given collections $\{a_i\}$ and $\{b_i\}$ of real numbers, then for all $n$: $\sum_{i=1}^n a_i + \sum_{i=1}^nb_i=\sum_{i=1}^n(a_i+b_i)$.

If that is what you are looking for then I'm sure you can come up with millions of other such examples.

$\endgroup$
7
  • 3
    $\begingroup$ I don't think this is an example of what the OP wants, although it is admittedly difficult to precisely enunciate why. The above statement is "natural" but not a "natural theorem": it is a manifestly true consequence of the definitions that (like almost any statement that quantifies over the natural numbers) requires induction to formally prove. $\endgroup$
    – Pete L. Clark
    Mar 21, 2015 at 20:57
  • 1
    $\begingroup$ @PeteL.Clark I think this is a natural theorem. I think what the OP means with 'natural theorem' is a result that occurs in standard mathematical practice (as opposed to some weird statement constructed for a specific purpose and which will not be used for anything else). I still agree that this doesn't answer the question because 1) I don't know how to prove it if not by induction, 2) the definition of $\Sigma$ itself requires the recursion theorem. $\endgroup$
    – Git Gud
    Mar 21, 2015 at 21:02
  • $\begingroup$ @Git Gud: The term "natural theorem" is certainly up for grabs, but to me such a thing should imply that I could imagine one experienced student of mathematics asking another "What's the proof?" And: if you treat foundational issues lightly/informally (as is typical in most mathematical practice), there is still something to say. This example does not meet either criterion. $\endgroup$
    – Pete L. Clark
    Mar 21, 2015 at 21:11
  • 1
    $\begingroup$ @PeteL.Clark I would argue on a semantic level that 'a manifestly true consequence of the definitions' is exactly what a theorem is. In this relation, most of what is taught in an introductory linear algebra course would also fall in this category. Surely it is natural material, and I doubt you would get far without arguments based on induction. $\endgroup$
    – Jonas Dahlbæk
    Mar 21, 2015 at 21:18
  • $\begingroup$ @GitGud OP was looking for something that can't be proven other than by induction, so I don't quite understand objection 1. As for objection 2, OP did not specify not to use recursion in defining the problem. It is perhaps a meta-theorem that any result that ultimately depends on induction to establish must rely on a concept defined recursively. $\endgroup$
    – Ittay Weiss
    Mar 21, 2015 at 21:27
3
$\begingroup$

The Baire Category Theorem is equivalent to the Axiom of Dependent Choice, and therefore you would not expect to be able to find what you call a neat proof. It may if course not be exactly what you are looking for, precisely because induction alone is not enough to prove the theorem.

$\endgroup$
0
0
$\begingroup$

It's not an exact answer to your question (I'm nowhere that smart), but if you need to derive something like a closed-form expression, but don't like using an inductive proof, you can try a thing called perturbation method introduced by Graham et al in $Concrete \ Mathematics$ (1995). Here's the simplest example: show the closed-form for $S_n=\sum_{k=1}^{n}a_k = \sum_{k=1}^{n} k$. The first step, denote $V_n=\sum_{k=1}^{n}k^2$: $$ V_{n+1} = V_n + a_{n+1} = V_n + (n+1)^2 = \sum_{k=1}^{n}k^2 + (n+1)^2 = \sum_{k=1}^{n}(k+1)^2 + 1 = V_n+2S_n + n+1 $$ $V_n$ cancel out, and after a bit of algebra you get of course $S_n = \binom{n+1}{2}$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .