Avoiding proof by induction

Solution 1:

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.

• As an aside: the equivalence between non-provability and countermodel-existence is (the contrapositive of) Gödel's completeness theorem; see this old answer of mine for some discussion of what's going on here.

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.

Solution 2:

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.