FOM: mathematical induction

[Stephen G Simpson]

Continental philosophers want to say that geometry is illogical.
Poincare and Detlefsen want to say that mathematical induction is
illogical.  What are these people talking about?  What's going on
here?

Detlefsen 24 Feb 1999 13:35:07 expounds Poincare's views on the
question,

 > is all mathematical reasoning rightly seen as being 'reducible' (in
 > some significant sense) to logical reasoning?

He shows that Poincare

 > was led to conclude that not all the inferences belonging to a
 > typical mathematical proof can be of a purely logical character

and proposed mathematical induction as an alleged example of this.
Detlefsen says that, according to Poincare,

 > mathematical induction binds isolated facts into unities and thus
 > combines them into laws

in a non-logical, non-syllogistic way (?!?!).  Detlefsen also expounds
his own variant of this view:

 > there is an important feature of [mathematical induction]--one
 > highly significant to its mathematical-justificatory status--that
 > is not reducible to the logical contents of and/or the logical
 > relationship(s) between its premises and conclusion.

Detlefsen in his posting doesn't give any real example, so it's hard
to know what he and Poincare are getting at.

I of course disagree with Poincare and Detlefsen, but it might be
interesting to consider this in the light of an example.

The first example of mathematical induction in most textbooks is the
familiar inductive proof of

             1 + 2 + ... + n = n(n+1)/2            (*)

by induction on n.  Letting S(n) denote the sum on the left-hand side,
the inductive step is to note that

    S(n+1) = S(n)+(n+1) = (n(n+1)/2)+(n+1) = (n+1)(n+2)/2

where the last equation is by elementary algebra.

Do Poincare and Detlefsen think that this is non-logical?  Why?  It's
straightforwardly formalizable in appropriate systems of predicate
calculus.  Primitive recursive arithmetic comes to mind.

Detlefsen seems to want to say that the above inductive proof gives
additional insight beyond its conclusion (*) [I agree] and that this
somehow makes the proof illogical [I disagree!].

Could Detlefsen please clarify his position in light of the above
example?

As I said above, I agree with part of what I think Poincare and
Detlefsen are trying to say.  Let me recast it in a different way,
using the tools of mathematical logic.  A well known phenomenon in
proof theory is that, if a Pi^0_2 sentence (x)(Ey)Rxy is proved in an
appropriate fragment of, say, the usual predicate calculus formulation
of arithmetic based on mathematical induction, then this implies not
only the truth of (x)(Ey)Rxy but also an appropriately tight
computable or recursive bound on y in terms of x.  It seems to me that
results of this kind capture in precise mathematical/logical terms at
least part of the Poincare-Detlefsen insight, to the effect that an
inductive proof gives some additional information.  But it does so
without the gratuitous Poincare-Detlefsen slap at logic.

Let me also use the above example to make another point.

Mathematicians often rightly regard inductive arguments as
unilluminating, or less illuminating than they should be.  The
following situation frequently arises.  Suppose it has been proved by
some sort of indirect inductive argument (typically via generating
functions) that two finite sets X_n and Y_n have the same cardinality.
There remains the problem of finding an explicit bijection between X_n
and Y_n.  Enumerative combinatorists consider such `bijective' proofs
very desirable.

In the above example, the obvious bijective proof would be to identify
S(n) as the number of x's in a triangular diagram:

        1. x
        2. xx
        3. xxx
           ...
        n. xxxxxx

and then to obtain the formula (*) by computing the area of the
triangle as 1/2 times the base times the height.  This proof of (*) is
also logical (i.e. formalizable in appropriate predicate calculus
systems), but it is more illuminating than the algebraic proof by
induction on n.  Similar bijective proofs have been given for many
combinatorial identities that were first proved by mathematical
induction.

What does this do to the Poincare-Detlefsen claim [which I reject]
that mathematical induction gives insight that is inaccessible to
logic?

-- Steve