# Validity of mathematical induction

Are there philosophical positions that reject the validity of mathematical proofs by induction? If so, what are the implications?

I know that mathematical intuitionists reject the law of the excluded middle, and therefore proof by contradiction, demanding instead a constructive proof. So I was wondering whether a similar position can be taken with respect to mathematical induction? Since induction in a sense relies on the existence of an infinite number of natural numbers, I can imagine that someone who does not acknowledge the existence of real or potential infinities may also reject mathematical induction.

• Strict finitists and ultrafinitists reject full scale mathematical induction, more recent authors also reject it because it fails for the so-called vague predicates, like “number of grains in a heap”. Tsujishita's Alternative Mathematics without Actual Infinity is a comprehensive recent review. Apr 5 '18 at 18:45
• Induction does not rely on an infinite number of natural numbers, it is completely constructive. It means that when given a number, you can follow the algorithm to directly produce a finite proof. So for any number there is a proof, and so the statement is proven for all numbers. You only need that each number exists, not that we can use the Natural Numbers as a completed infinity.
– user9166
Apr 5 '18 at 22:28
• @jobermark It is not "completely" constructive since it relies on imagined ability to continue an algorithmic process indefinitely. Ultrafinitists object to entertaining such possibilities and reject potential infinity along with the actual one. Since even big enough finite is humanly and physically impossible imagining it may well be wishful thinking. Modal skeptics generally reach similar conclusions. Apr 5 '18 at 23:20
• @JWLM, No, I am coming from intuitionism. I don't really believe in the completed infinity you claim is absolutely necessary, but I still believe in induction. Arbitrary choice and a completed infinity are only related if you insist on an atemporal reality. So your argument insists that Intuitionism as a position does not exist. You are missing a subtlety some of us find very important.
– user9166
Apr 6 '18 at 17:30
• @jobermark It makes no difference whether the loop is ascending or descending. Execution time is not equal to the size of the input, and you can not physically loop 10...0 times because the universe will end sooner. Your belief that the algorithm is still executable (in whatever sense) is just that, a belief that others may not share. Ultrafinitists are "far more constructivist" than intuitionists, and modal skeptics would reject whatever notion of modality you need to explain what "executable" means in such cases. Apr 6 '18 at 23:24

We should distinguish between induction over finite sets and over infinite sets. I'm not aware of any philosophical position that would reject a proof of the statement "For all n less than 100, the sum 1 + 2+ ... + n = n(n+1)/2" using induction on n. Induction only relies on each number n having a successor n+1 that behaves arithmetically the way we expect, and this can be checked explicitly for every number up to 100.

But when you say "For all natural numbers n, the sum 1 + 2 + ... + n = n(n+1)/2," and prove it by induction, you're implicitly making a claim that the natural numbers exist. Certain flavors of Finitism reject the existence of the natural numbers or any infinite sets. More specifically, so-called classical finitists are alright with statements like "every natural number has a successor," because in principle, given any large but finite n, one could write down a proof of finite length that proves the statement for all numbers less than n. So I believe they would have no qualms with inductive proofs. But strict finitism does not accept the existence even of potentially infinite objects, so they would not allow themselves to use induction over the naturals, or even state the theorems that require such a proof. (An example of the difference between classical and strict finitism: classical finitism allows us to talk about the limit of an infinite sequence, because one can phrase this as a statement about finite truncations of the sequence becoming arbitrarily close to the limit, but strict finitists only want to talk about finite sequences in the first place.)

Then there's Ultrafinitism, which goes as far as to deny the existence of sufficiently large natural numbers. For this school of thought, it's not good enough to say "in principle, given enough time, we could write down a finite proof of such and such a statement." One has to be able to write this proof down in practice. This is somewhat like Constructivism, although I believe most constructivists accept the existence of infinite sets.

Finitist positions may seem ridiculous at first glance (and they are decidedly fringe among working mathematicians), but to be fair to them, most people do not have an easy or satisfying answer to the question of what the existence of a mathematical object really means. If you ask me whether the number 5 exists, I will say "it depends what you mean by exist." If you ask me whether the natural numbers exist, I will give you the same answer. When I prove an existence theorem for a differential equation, I am (in my own mind) only making a mathematical statement, not a philosophical one. But if you talk to finitists, they at least have a notion of what they mean, philosophically, when they say that something exists. Most mathematicians (including me) don't even address the question.

Finally, there is also a non-ideological case to be made for more restrictive frameworks: namely, it is interesting to learn what mathematics can still be built with fewer tools at our disposal.

• For my understanding, can you explain the difference between strict finitism and ultrafinitism? I thought they were synonymous: the claim that sufficiently large finite sets are not well-defined. Apr 5 '18 at 19:38
• Thanks, this is a great answer. I appreciate the point about finitist positions and the difficulty of knowing what a mathematical object is. Apr 5 '18 at 19:49
• @user4894 As I understand it, strict finitists are comfortable with any set or number that is finite, no matter how large or how impractical to write down or calculate.
– user32250
Apr 5 '18 at 20:02
• @jobermark To clarify your statement, would you characterize prominent ultrafinitists like Doron Zeilberger and the late Edward Nelson as nuts? Apr 8 '18 at 2:14
• @user4894. I don't think either of them deny the existence of any given number. So by the definition given in this post, neither of them would be Ultrafinitist. If that definition is wrong here too, and I will only get flak for pointing that out, I will just go away.
– user9166
Apr 8 '18 at 18:47

Essentially, the principle of mathematical induction says that you can reach any natural number by repeated succession starting at zero. So, if you want to define the set of natural numbers, then induction must hold on that set.

Note that the principle induction can hold even on finite sets, e.g. on X={0,1} with 0=/=1 and a successor function S such that S(0)=1 and S(1)=0. Induction holds on X since all elements of X can be reach by repeated succession starting at 0. More formally, it would then be trivial to prove:

For all subsets P of X, if 0 in P and for all x in P, we also have S(x) in P, then P = X.

My understanding is that most flavours of mathematical induction and co-induction can be obtained as as theorems about least and greatest fixed-points of monotonic functions on lattices. Specifically, they can be obtained as corollaries of the Knaster-Tarski Fixed-point theorem. Section 21.1 of Pierce's Types and Programming Languages gives a great summary of this.

So while there may be legitimate reasons to reject mathematical induction philosophically, one has to reject the premises/axioms that allow for it to be proven. This is similar to how one who rejects Banach-Tarski's method of turning one ball into two should reject the premise that allowed for the result to be provde (the axiom of choice), as opposed to the result itself.

The main 'problem' with (non-transfinite) induction is that the proof itself that would cover all the numbers is not completed in a finite length unless one includes a rule that is implicitly infinitely long.

The proof via induction sets up a program that reduces each step to a previous one, which means that the actual proof for any given case n is roughly n times the length of the stated proof. The total proof, to cover all cases is then implicitly infinite in length. But for any case that comes to hand, we could do the scutwork and spit out a proof that is still finite. So does a collection of infinitely many finite proofs count as a proof? Well, that depends on why on earth you think there is an infinite set of proofs to begin with. Either you think there is a complete, infinite set of integers, or you don't. Either way, induction it true, but it is true for a different reason in each case.

In Classical mathematics, the question seems very stark: you either need the 'induction schema' which is either second-order, and thus potentially self-referential, or has infinitely many entries. But this is because classical mathematics is not 'constructive', it always models time by taking up space, by creating copies of objects, rather than by taking up time.

If you need something to be true of any integer, but your statement systematically differs from integer to integer, so that there is not a single closed form that captures it, then you have to make infinitely many copies of it, and modify each copy. This makes induction seem strange. But it all takes care of itself. If you think the set of numbers exist, there is no reason why your infinite set of axioms should not exist, one for each number.

From a constructivist point of view, mathematics should be represented not by true statements but by iterative constructions. A proof should be a program that runs on inputs and verifies that an assertion can be reduced to agreed principles. Then every proof shares that form with an induction. We very seldom ever write out a proof proceeding entirely from axioms one step at a time. Instead, we invoke principles and forms that indirectly indicate how the 'real underlying' proof would be assembled.

And selecting a number does not require embodying the set of all numbers so that you can then choose one. It just means what it says, if I counted up to someplace and just stopped anywhere, I would have chosen an arbitrary integer without vouching for the existence of a set of all integers. Our notions of infinite sets are just tricks of language, not depictions of infinite objects.

So issues of infinities do not have to enter into the consideration here. You only need to accept that iteration is a reasonable thing to do. You can do that within your definition of what a construction is, and therefore within the definition of what it means to prove something. In that case, you do not need an infinite axiom base to support proofs with loops.

For Kleene, a proof is a recursive function that computes a truth value, for Bishop it is an iterative process that validates an assertion. Both of these automatically include induction as a natural form of proof.

Beyond this, there are extreme forms of objection to repetition. The idea that there is a natural limit on the human ability to keep track of things and that we should not allow arbitrarily long processes into our plans. This reaction arises quite naturally in the proof of the 4-color theorem, where there are over a thousand separate cases, and each case is an algorithm that reduces a complex structure to one of the earlier cases. It is a proof that no human could ever possibly comprehend, and our faith in it relies upon our understanding of the engineering process that selected those cases and automatically wrote those algorithms through brute force enumeration. It makes one worry.

But in such a framework no general mathematical truth is ever really true. A notion like the idea of induction is impossible to state, and so is a simple theorem like the idea all maps can be painted in four colors. There are surely maps too complex for a human to paint them, so surely there is no way of knowing about that. To me, this is nonsense. We have invented computers, and they collectively manage exobytes of information. We have more than enough power to handle mathematical truths far beyond any individual's or group's ability to fully comprehend them, and yet we don't doubt that we can enforce the rules that handle that information. This philosophy has to just crumble under observed reality.

Mathematical induction is a powerful method to prove properties of natural numbers. If you prove a property for the first natural number 1 and if you prove that the natural number n + 1 has this property whenever the natural number n has this property (of course without fixing n) then every natural number has this property. Because you can put n = 1 and get the property for n + 1 = 2, then you can put n = 2, and so on.

This powerful method is a basic tool of mathematics. Nevertheless there is a philosophical position not accepting this, namely that of Cantor's set theory. The reader may be surprised to find set theory differing from mathematics, but the refusal of mathematical induction and Cantor's own words prove this case: Cantor said (on more than one occasion, for more see https://www.hs-augsburg.de/~mueckenh/Transfinity/Transfinity/pdf)

"The general set theory [...] definitely belongs to metaphysics. [...] and the fact that my presently written work is issued in mathematical journals does not modify the metaphysical contents and character of this work. [...] By me Christian philosophy is for the first time confronted with the true teachings of the infinite in its beginnings." [G. Cantor, letter to T. Esser (15 Feb 1896)]

Cantor assumes that infinity can be finished. For instance in a letter to Lipschitz he said (more can be found loc cit) "The erroneous in Gauss' letter consists in his sentence that the finished infinite could not become an object of mathematical consideration. [...] The finished infinite can be found, in a sense, in the numbers ..." [G. Cantor, letter to R. Lipschitz (19 Nov 1883)] (my italics)

How can the infinite be finished? For instance, how can the equinumerousity of natural and rational numbers be proved? Only by refusing mathematical induction. There we prove the important property of every natural number n: n belongs to a finite initial sequence which is followed by an infinity of natural numbers. There is never an end and there is never a finish that would allow anybody to claim equinumerousity with another infinite set. Set theory however does not accept this proof by mathematical induction but claims that somehow simultaneously the infinite can be finished. "Simultaneously" in order to neglect the fact that the sequence of natural numbers has an order and mathematics allows (and in doubt demands) to interrupt the sequence at every position.

There are other philosophies like ultrafinitism not accepting mathematical induction but that is based on arguments about reality and is certainly less severe than Cantor's metaphysics.

• Comments are not for extended discussion; this conversation has been moved to chat.
– user2953
Apr 9 '18 at 18:23