Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

This question is prompted by a remark from Bill Dubuque in his answer to this question on proving a particular sum without using mathematical induction.

From Bill's answer:

A proof that a statement is true for all integers must - at some point or another - employ mathematical induction. The use of induction may not be obvious - it may be hidden (far) down the inference chain in some other theorem or lemma invoked, as in said uniqueness theorem for recurrences (difference equations).

My question is, is this always true? (I have no particular reason to doubt its veracity, but am curious if it is always true). And if so, why is this the only tenable strategy for proving a statement about all integers? If not, what are the alternative strategies?

It seems like we have to prove things for all integers with some frequency (in some areas of mathematics), so realizing that every single one of these proofs will somehow rest on inducting narrows one's search space for a proof quite substantially. I'd just like to know how strong a statement this really is.

share|improve this question
1  
I think that if you're trying to prove something that's ONLY true for the integers (or some subset of them), there'll be induction involved, simply because it's induction that makes the integers what they are (that is, the positive integers is the smallest set $S$ such that $1\in S$ and ( $k\in S$ implies $k+1 \in S$ )). However, if you're looking at a statement that happens to be true for a larger set (such as Q or R), and you're only asked to prove it for the integers; well, in that case, you won't need induction. Most of the counterexamples given in answers here fall into that category. –  user22805 Mar 16 '12 at 10:54

7 Answers 7

up vote 17 down vote accepted

Several answers take the view that if one result is proved by induction, then all proofs which invoke that result must also be considered to have been proved "using induction". Since the definition of $\mathbb{N}$ fundamentally includes induction, virtually everything you can say about $\mathbb{N}$ is proved "using induction" in this sense. I suppose that's what Bill Dubuque was saying.

This "contamination" attitude has plenty of precedent: it's an attitude we sometimes take for things like "using the axiom of choice" (because some of us care about set theories that don't have that axiom, and so we'd like to be alert to its use) or "using the parallel postulate" (because some of us care about non-Euclidean geometries). I'm not sure why people want to take this attitude for induction, though; I'm not aware of any alternative theories of $\mathbb{N}$ that don't use induction.

Moreover, when implemented zealously, this attitude requires us to say that a proof which invokes only, say, the axioms of commutative semirings must be considered to "use induction" if it begins "Let $x\in\mathbb{N}$" but not if it begins "Let $R$ be a commutative semiring and let $x\in R$". In such cases it is better to say that the proof is "really" a proof about commutative semirings (even if it claims to be about $\mathbb{N}$) and that the application to $\mathbb{N}$ requires a lemma that $\mathbb{N}$ is a commutative semiring, and that lemma requires induction. Similarly for lots of proofs of identities involving gcd and lcm which are "really" about boolean lattices, and so on. (Definitions like those of commutative semirings and boolean lattices serve here as junctions in a modular system of knowledge; the contamination attitude disregards that modularity, to our detriment.)

Finally [and here I deviate somewhat from the question at hand], all of this ignores the reason people ask for proofs that are not by induction in the first place. Sometimes it's because they're a novice and are not yet able to see through the mechanics of the inductive proof to the underlying telescoping (as in some of the answers to the linked question) or accumulation (as in, say, the proof that there are $n!$ permutations of $n$ objects). Sometimes it's that the proof by induction sheds no light on how anybody came up with the statement being proved (as in, say, the inductive proof of Binet's formula for the Fibonacci numbers, which is an amusing exercise in high-school algebra but has no other merits). Sometimes we just want some other angle on the phenomenon to broaden our understanding or tickle our aesthetic feelings (as in the semi-proof that the sum of the first $n$ odd natural numbers is $n^2$, by presenting a square cut up into gnomons). It's virtually never because they want some proof-theoretically noninductive development of the theory of $\mathbb{N}$, and it's pretty unhelpful to pretend that that's what they're really asking for.

share|improve this answer

Well, technically it is not true. For a trivial example, look at the sentence $\forall x(x=x)$. We do not need induction to prove this is true for all the natural numbers.

Unfortunately, the knowledge that in principle most results require induction does not offer significant help in producing proofs. As Bill Dubuque pointed out, the induction may be hidden deep in the inference chain, in the proofs of other theorems that are used in our proof. One knows that in principle we need to put one foot in front of the other repeatedly in order to run. That knowledge is not really of much help in running a marathon.

share|improve this answer
    
Thanks. Sadly, this does not seem like nearly as powerful a statement for guiding a proof strategy as I had been thinking. –  user23784 Mar 15 '12 at 23:13
1  
@rar It was never meant as a "guide for proof strategy" but, rather, to emphasize that one cannot eliminate induction by inserting ellipses - as some had done in that thread. To make this more precise would require a course in the branch of logic known as proof theory. –  Bill Dubuque Mar 15 '12 at 23:27
    
@BillDubuque Of course, I did not mean to imply you were promising it as such. I just thought it was a very interesting sounding statement and my question was really trying to figure out how profound it was. The answers suggest that it is a testament to how pervasive induction is (even if it is tucked away out of sight much of the time). –  user23784 Mar 15 '12 at 23:39

Technical answer

In Peano arithmetic, even $+$ and $\cdot$ are defined using induction, and their properties - commutativity, associativity, distributivity etc. are proved using induction. Therefore, if your proof uses one of these properties, and you were to inline the proofs to bare axioms (like you look at generated assembly from a computer program written in a high level language), induction will be somewhere.

Subjective opinion

I prefer to classify a proof as inductive only if has a novel inductive argument - not if it only relies on established properties such as $\sum_{i=1}^{n} x_i = \sum_{i=1}^{n} x_{n+1-i}$ or $a+b=b+a$. Although those properties are proved inductively, once you proved them, you do not need to repeat their proof again. In the programming terminology, such proofs are like routines which do not call induction directly, but indirectly via subroutines.

Therefore almost all proofs with natural numbers use induction, but I do not think you need to unpack complex proofs to see how induction is used. Abstraction is a good thing.

share|improve this answer

You either define the natural numbers axiomatically using Peano's axioms or you define them as the smallest inductive subset of the real numbers or something equivalent in set theory. So, yes, you need induction somewhere when talking about the natural numbers, except of course in trivial cases that hold for simpler theories, such as the example given by André Nicolas.

share|improve this answer

You can understand the question in two different ways:

  • (strong) Can the given statement be proved without involving induction at any step or any level of reasoning
  • (weak) Given all the inductive definitions and trivial well-known properties, can we prove the statement without involving any additional induction, related to this problem only

It seems to me that what was asked in that question is the weak form of the question, and what Bill tends to think about is the strong one. But still, in that question, I agree with Bill, that answers involving arguments such as, for example, $a_1-a_0+a_2-a_1+...+a_n-a_{n-1}=a_n-a_0$ do require induction (it is just rewritten in another form).

As for the Bill's remark, I think, it is not exactly correct (even for the strong form of the question).

I would say that one needs (at some level) induction when dealing with a statement that is correct or even meaningful for integer numbers only. For instance, an example given by Beni Bogosel, obviously, does require induction at some point, at least because it is meaningless to talk about "5 divides x" or "-1 to the power of x" if x is not an integer number. Therefore, to define when it is true, one must use the induction at some point. His first proof requires the induction explicitly, and the second one -- implicitly.

At the same time, a statement might be of a more general nature that just happened to be stated for integers only. A trivial example is given by André Nicolas: $\forall n:n=n$ (well, it is trivial given the reflexivity axiom). But another example might be a statement that is true for all real numbers, and, hence, for all integers. For example, $(n\neq 0\wedge m\neq 0)\Rightarrow n\cdot m\neq 0$. Neither the definition of the operator, nor a proof of the statement for reals requires induction. And, now, if we think of (or define) integers as a subset of reals, then we don't even need the exact definition of integers... all we need to know is that it is a subset of a set such that the statement has already been proved.

share|improve this answer
    
You don't define the natural numbers to be a subset of the reals. They are the smallest set containing $0$ and closed under successor. That every number produced this way is a real number requires - you guessed it - induction. –  Mario Carneiro Mar 27 at 13:34

I strongly suspect I am missing the point here, so be gentle. And my ability to write proofs in $\LaTeX$ has faded in the last 20 years, so forgive any informality.

Proof of $\forall x(x\neq x+1)$ without induction:

Suppose that $\exists x$($x=x+1$).

Subtracting $x$ from both sides, we get $0=1$, which is a contradiction.

$\therefore$ by contradiction, $\not \exists x$($x=x+1$).

$\therefore \forall x(x\neq x+1)$, because $\neg (\exists x\in X : P(x)) \equiv \forall x\in X, \neg P(x)$

I can't see any induction here. What did I miss?

share|improve this answer
    
Subtracting $x$ from both sides requires that you know that addition is cancellative, and that proof needs induction. –  Mario Carneiro Mar 27 at 13:37

Forgive me for the subtleness and vagueness of my answer but let me sideline a bit and say that there are two different types of knowledge, those being 'a priori' and 'empirical'.

To be brief, a priori knowledge is analytical and doesn't require previous experience, and empirical knowledge in layman's terms is knowledge built from previous knowledge/experience.

After laying the ground work i.e stating axioms, Mathematics can be thought of as a priori knowledge. We can build theorems and proofs on top of eachother and the knowledge then can be thought of as empirical (moving up the 'inference chain'). We know Induction is used at the bottom of the chain where our building blocks are - so any proof we make from there onward should actually rely on induction some where.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.