Does Potential Infinity Rule Out Mathematical Induction?

In an earlier thread David Brightly states that "The position on potential infinity that he [BV] is defending is equivalent to the denial of the principle of mathematical induction."  Well, let's see.

1.  To avoid lupine controversy over 'potential' and 'actual,' let us see if we can avoid these words.  And to keep it simple, let's confine ourselves to the natural numbers (0 plus the positive integers).  The issue is whether or not the naturals form a set.  I hope it is clear that if the naturals form a set, that set will not have a finite cardinality!  Were someone to claim that there are 463 natural numbers, he would not be mistaken so much as completely clueless as to the very sense of 'natural number.'  But from the fact that there is no finite number which is the number of natural numbers, it does not follow that there is a set of natural numbers.

2.  So the dispute is between the Platonists -- to give them a name -- who claim that the naturals form a set and the Aristotelians -- to give them a name -- who claim that the naturals do not form a set.  Both hold of course that the naturals are in some sense infinite since both deny that the number of naturals is finite.  But whereas the Platonists claim that the infinity of naturals is completed, the Aristotelians claim that it is incomplete.  To put it another way, the Platonists -- good Cantorians that they are -- claim that  the naturals, though infinite,  are a definite totality whereas the Aristoteleans claim that the naturals are infinite in the sense of indefinite.  The Platonists are claiming that there are definite infinities, finite infinities -- which has an oxymoronic ring to it.  The Aristotelians stick closer to ordinary language.  To illustrate, consider the odds and evens.  For the Platonists, they are infinite disjoint subsets of the naturals.  Their being disjoint from each other and non-identical to their superset shows that for the Platonists there are definite infinities.

3.  Suppose 0 has a property P.  Suppose further that if some arbitrary natural number n has P, then n + 1 has P.  From these two premises one concludes by mathematical induction that all n have P.  For example, we know that 0 has a successor, and we know that if  arbitrary n has a successor, then n +1 has a successor.  From these premises we conclude by mathematical induction that all n have a successor.

4.  Brightly claims in effect that to champion the Aristotelean position is to deny mathematical induction.  But I don't see it.  Note that 'all' can be taken either distributively or collectively.  It is entirely natural to read 'all n have a successor' as 'each n has a successor' or 'any n has a successor.'  These distributivist readings do not commit us to the existence of a set of naturals.  Thus we needn't take 'all n have a successor' to mean that the set of naturals is such that each member of it has a successor.

5. Brightly writes, "My understanding of 'there is' and 'for all' requires a pre-existing domain of objects, which is why, perhaps, I have to think of the natural numbers as forming a set."  Suppose that the human race will never come to an end.  Then we can say, truly, 'For every generation, there will be a successor generation.'  But it doesn't follow that there is a set of all these generations, most of which have not yet come into existence.  Now if, in this example, the universal quantification does not require an actually infinite set as its domain, why is there a need for an actually infinite set  as the domain for the universal quantification, 'Each n has a successor'?

6.  When we say that each human generation has a successor, we do not mean that each generation now has a successor; so why must we mean by 'every n has a successor' that each n now has a successor?  We could mean that each n is such that a successor for it can be constructed or computed.  And wouldn't that be enough to justify mathematical induction?

Addendum 8/15/2010  11:45 AM.  I see that I forgot to activate Comments before posting last night.  They are on now. 

It occurred to me this morning that  I might be able to turn the tables on Brightly by arguing that actual infinity poses a problem for mathematical induction.  If  the naturals are actually infinite, then each of them enjoys a splendid Platonic preexistence vis-a-vis our computational activities.  They are all 'out there' in Plato's heaven/Cantor's paradise.  Now consider some stretch of the natural number series so far out that it will never be reached by any computational process before the Big Crunch or the Gnab Gib, or whatever brings the whole shootin' match crashing down.  How do we know that the naturals don't get crazy way out there?   How can we be sure that the inductive conclusion For all n, P(n) holds?  Ex hypothesi, no constructive procedure can reach out that far.  So if the numbers exist out there, but we cannot reach them by computation, how do we know they behave themselves, i.e. behave as they behave closer to home?  This won't be a problem for the constructivist, but it appears to be a problem for the Platonist.

Comments

[Bill Vallicella]

Bill,

In your reply to David Brightly on mathematical induction you consider an example for *some specific* property P and show how one can adopt math. induction on an Aristotelian view. The trouble is that this is not proving that an Aristotelian can legitimately adopt mathematical induction for *all* properties. In fact, it is unclear how the Aristotelian you describe can even formulate the principle of mathematical induction along the lines you propose. The reason is as follows. You can state mathematical induction either in first order language or in second order. In second order you explicitly quantify over properties (i.e., for *all* properties P; ....). In first order you only have individual quantifiers, so you do not quantify over properties; but then you either must use a schematic letter or place holder for properties or assume a different formulation of the induction principle for each property. Now, if it so happens that there are infinitely many properties, then in either case you presuppose an actual infinity. In the second order you in fact quantify over an antecedently given infinite set of properties; in the first order you either need an infinite number of induction statements, one for each property, or you assume an infinite number of substitutions for the schematic letter appearing in the first-order formulation of the principle of induction.

In one of my replies to David I have proposed an intuitionistic construal of the principle or a finitist one, both of which are consistent with denying infinity.

peter

[Account Deleted]

Bill,

Was wondering about the com-box. So I e-mailed you the following, which now can be freely posted here.

1) In your reply to David Brightly on mathematical induction above you consider an example of *some specific* property P and show how one can adopt math. induction on an Aristotelian view. The trouble is that this is not proving that an Aristotelian can legitimately adopt mathematical induction for *all* properties. In fact, it is unclear how the Aristotelian you describe can even formulate the principle of mathematical induction along the lines you propose. The reason is as follows. You can state mathematical induction either in first order language or in second order. In second order you explicitly quantify over properties (i.e., for *all* properties P; ....). In first order you only have individual quantifiers, so you do not quantify over properties; but then you either must use a schematic letter or place holder for properties or assume a different formulation of the induction principle for each property. Now, if it so happens that there are infinitely many properties, then in either case you presuppose an actual infinity. In the second order you in fact quantify over an antecedently given infinite set of properties; in the first order you either need an infinite number of induction statements, one for each property, or you assume an infinite number of substitutions for the schematic letter appearing in the first-order formulation of the principle of induction.

2) "How do we know that the naturals don't get crazy way out there? How can we be sure that the inductive conclusion For all n, P(n) holds?"

We know that because we believe the axioms, including math. induction. In the case of NN the problem is not that severe. But, of course, the problem you raise cannot be answered without relying on some version of mathematical induction. However, once math. induction is in place, then at least for the NN one can prove that if one denies the last step of math. induction, then the system is inconsistent. Of course, this will have to rely on math. induction. So another way of raising your question is: what justifies the use of math. induction in the case of infinite magnitudes? I doubt that there is a way of answering this question without relying on math. induction or some equivalent.

On the other hand you say: "This won't be a problem for the constructivist,..." I do not see why. The constructivist must assume quite a lot. For instance, he needs first to formulate math. induction without presupposing any infinity. Second, I assume that you think that the constructivist does not face this problem because he deals only with constructible sets of NN and, therefore, he can always survey this set and insure that math. induction holds throughout. The trouble is that surveyability has its own pithfalls; for instance, the constructivist needs to rely on his memory so that his later inspection matches earlier ones.

[Cammie Novara]

"But from the fact that there is no finite number which is the number of natural numbers, it does not follow that there is a set of natural numbers." I completely agree with that. There's a really interesting debate that I thought would be of interest on evolution vs. intelligent design going on at http://www.intelligentdesignfacts.com

[David Brightly]

Bill,

Can I make a comment on your 'generations' example in para 5? This introduces the added complication of time and the difficulties we may have with the logic of tense, as perhaps here. Does the concept of number necessarily involve time? No doubt we all develop a concept of number through learning to count. Both the counting and the learning are concrete processes in time. But once the concept is in place we perceive that there are geometrical analogues of temporal ordering, an infinite sequence of fenceposts or the 'number line' itself, say, in which 'immediately to the right of' is isomorphic to 'successor of'. So can we abstract away time and see generations atemporally?

Suppose that the human race will never come to an end. Then we can say, truly, 'For every generation, there will be a successor generation.' [P]  But it doesn't follow that there is a set of all these generations, most of which have not yet come into existence. 

Let's refer to the current generation as G0. P tells us that it will have a successor generation. Call this G1. P tells us that G1 will have a successor generation. Call this G2. P grants us the ability to refer to the generations as G0, G1, G2, and so on, without limit. We can make assertions like '95% of the people of Gn will live the whole of their lives between years y1 and y2.' We can picture this geometrically: take the number line to represent time and for every person who ever will live draw a line segment above the time axis spanning from his birth year to his death year and colour code this according to his generation. This, for me, makes it clear which entities we are quantifying over and avoids the ambiguities that Peter highlighted with regard to numbers 'under construction'. If we want to quantify over an initial segment of the generations, those up to Gk, say, then we can make this explicit: for all Gn with n≤k. Geometrically, we erase the subsequent generations from the picture. You will ask: Do the Gs form a set? My reply: Does the answer affect the picture? I don't think we need to bring in talk of sets at this point, but if it's useful to use set language in referring to the Gs then let's do so, provided we are aware of the pitfalls of unrestricted set comprehension.

What I find really interesting about the generation example is that 'generation n' is a hypostatisation from the recursively definable predicate '_ is a descendant of order n'. Is an actual infinity of predicates or properties more acceptable than an actual infinity of objects?

[Bill Vallicella]

David asks, "Is an actual infinity of predicates or properties more acceptable than an actual infinity of objects?" No. Peter too raised this question as an embarrassment for the Aristotelian view. There is no point in eliminating an actual infinity of numbers if the price is an actual infinity of predicates or properties.

What is not clear to me me is the necessity for an actual infinity of predicates or properties. Peter wonders whether math. induction works for ALL properties. He wants to force me to quantify over an infinite set of properties. But why can't I say: For any n accessible to computation, and for any P that you can formulate, P(n)?

[John Cassidy]

I think we understand that numbers don't "go crazy" out there, because of their simplicity. They are a simple conception isolated, by design, from any side effects by the rules of their construction or induction.

But even that points to their "dependence" upon each other. In another sense, though this frames Bill's point as well. If they pre-exist any analysis, how can we be sure that they remain just simple? Induction isn't just the case that something is true for k and k + 1. If that were the case, all numbers are prime because 2 and 3 are. It is precisely the inference that if it is true for k + 1 by being true for k, we have an induction. Thus induction is conducted precisely by a dependency of one number defined in terms of its predecessors.

Also, I find it hard to buy that the goal of induction is to use the word "all" when "any" works just as well. Thus for any number n, if a property P is arrived at through induction for a number m < n, then n has property P. And "any" or "each" is even closer to the induction relationship. Thus all properties possessed by induction are possessed by the existence of that property in predecessors.

"Any" and "all" imply about the same thing, but where as "all" hints at some collective group, "any" just suggests that we have a sample under scrutiny.