FOM: re. mathematical induction

[Michael Detlefsen]

Herwith a few remarks in response to replies to my earlier posting on the
place of logic in mathematical proof.

(I) Colin's and Harvery's remarks:

Colin wrote,

      "I am quite sure of Poincare's point, and I believe it is Detlefsen's
also. They are not saying any single use of induction is inexpressible in
formal logic. They are saying that no formal expression can capture all of
your actual belief in induction.

        Suppose you really believed in the principle of induction only as it
is formalized in ZFC. Then you could not also believe that ZFC proves the
consistency of each of its finitely axiomatized fragments. That claim
involves inductions in the metalanguage that cannot be formalized in ZFC.

        Of course the claim is provable in the extension of ZFC gotten by
taking the claim itself as a new axiom, and even in other more interesting
extensions. But each of those extensions admits exactly the same further
extension.

        No consistent formal, first order, axiomatic theory includes every
case of induction that you yourself will want to accept."

To this, Harvery replied

"
This is not correct.

THEOREM. ZFC proves the consistency of each of its finitely axiomatized
fragments.

Furthermore, this Theorem is provable in Peano Arithmetic, and even in weak
fragements thereof such as EFA = exponential function arithmetic.

>        No consistent formal, first order, axiomatic theory includes every
>case of induction that you yourself will want to accept.

It often does include all cases of induction that are expressible in the
language of that system.

I think that you need to reformulate your point more carefully."

Actually, I think Colin did formulate his point a little uncarefully ...
and Harvey is right about his (Harvey's) reading of the point. It is,
however, possible to read Colin in another way, and it is the difference
between these two readings that I think is important. The difference has to
do with the position of the quantifiers in their respective claims.

Harvey claims, quite correctly, that

(Local Reflexivity for ZFC): For every finitely axiomatizable subsystem
F-zfc of ZFC, Con(F-zfc) is provable in ZFC.

[Note: Mostowski proved this in 1952 in a paper entitled 'On Models of
Axiomatic Systems', FM 39: 133-158. In the same paper, he also proved the
'reflexivity' of PA and a certain first-order system of real arithmetic R.
At the time this was proved, I believe that it was the only means available
for proving the non-finite axiomatizability of PA. Later the same year, and
in the very same volume of FM, however, Ryll-Nardewski published a paper
('The Role of the Axiom of Induction in Elementary Arithmetic', FM 39:
239-263) giving a more 'direct' proof of the non-finite axiomatizability of
PA.]

I take it, however, that Colin's claim is this:

(Meta-reflexivity re. ZFC): It is provable in 'my' mathematical belief
system that for every finitely axiomatizable subsystem F-zfc of ZFC,
Con(F-zfc) is provable in ZFC.

If this is correct, then Colin would seem to be right. Whatever form(s) of
induction you used to prove Meta-reflexivity re. ZFC would not be
codifiable in ZFC ... provided, at any rate, that you select the
description of the various F-zfc and the various Con(F-zfc) in such a way
as to guarantee that

(*) '(F-zfc)Con(F-zfc) --> Con(ZFC)' is provable in ZFC,

and you select Con(ZFC) in such a way that G2 holds of it.

At least this is the way I see it ... Colin and Harvey, have I understood
you correctly?

(2) Next, re. Harvey's other posting re. the usefulness of induction as a
means of shortening proofs, all I can say is that this is very interesting.
I had never seen Harvey's example before, or any other very like it, though
I am familiar with the papers by George Boolos that Harvey alludes to.

[N.B. By the way, in addition to the paper others have mentioned, there are
two others in the same vein. They are 'Zooming down the slippery slope' and
'Don't eliminate cut'. Both are reprinted in the LOGIC, LOGIC, LOGIC
volume.]

(II) Martin's remark:

At 05:01 PM 2/25/99 -0500, simpson at math.psu.edu wrote:

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

Poincare's position needs to be understood in historical context. There was
no first order logic. There was logicism: Frege's that had turned out to be
inconsistent, and Poincare was especially interesteed in Russell's. Russell
proposed to develop arithmetic from "logic", and Poincare was attacking this
program.

There's a lot more than could be said about this, but Poincare's objections
had nothing to do with formalized arithmetic as we understand it today, and
certainly was not directly relevant to the more sophisticated remarks of
Colin McClarty.

I agree with Martin that, at the time that Poincare made his remarks about
induction, there was no first-order logic ... at least not as such. There
were, however, claims like those I quoted from Frege in my posting ...
namely:

"Thought is in its essentials the same everywhere: it is not true that
there are different kinds of laws of thought to suit the different kinds of
objects thought about ...
The present work will make it clear that even an inference like that from n
to n+1, which on the face of it is peculiar to mathematics, is based on the
general laws of logic, and that there is no need of special laws for
aggregative thought."

This was in direct contradiction to what Kant had proposed in the CPR. Like
Frege, Russell and Peano too made such claims. It is important to see that
such claims, by themselves, do NOT yield logicism. They only say that the
INFERENTIAL PART of mathematics is purely logical. They do not assert the
remainder of what needs to be asserted in order to get logicism ... namely,
that the BASIC LAWS of arithmetic (and the basic laws of whatever other
parts of mathematics are to fall under the logicist thesis) are logical in
nature. So, I don't believe that Martin is right to suggest that Poincare's
remarks were directed against logicism simpliciter. They were rather
directed against that subthesis of logicism which states that mathematical
REASONING or INFERENCE (as distinct from the BASIC LAWS of mathematics) is
strictly logical. As Poincare said (and as I quoted in my posting):

"Without doubt, we can go back to the axioms, which are the source of all
these reasonings.  If we decide that these cannot be reduced to the
principle of contradiction, if still less we see in them experimental facts
which could not partake of mathematical necessity, we have yet the resource
of classing them among synthetic a priori judgements. This is not to solve
the difficulty, but to baptize it; and even if the nature of synthetic
judgements were for us no mystery, the contradiction would not have
disappeared, it would only have moved back; syllogistic reasoning remains
incapable of adding anything to the data given it; these data reduce
themselves to a few axioms, and we should find nothing else in the
conclusions." (italics mine)

"Mathematical reasoning has of itself a sort of creative virtue and
consequently differs from the syllogism." (italics mine)

Owing to the work of Boole, Schroder, Peirce, Frege, Russell, Peano and
others, this subthesis had found far wider acceptance in the mathematical
and philosophical communities than the other subthesis of logicism (viz.
that the BASIC LAWS of math are logical in character) ever did. Therefore,
Poincare should be seen not as attacking logicism simpliciter but rather as
attacking the far more popular subthesis of logicism--and, by the way, the
one most often emphasized by Russell himself and one that was embraced not
only by logicists but by many non-logicists as well--that mathematical
REASONING is (or can, in some appropriate sense, be 'reduced to') purely
logical reasoning. This is why

I disagree with Martin, then, when he characterizes Poincare's attack as
simply an attack against logicism. I also disagree with his suggestion (if,
indeed, this is part of what he is suggesting) that Poincare's objections
have nothing to do with formalized arithmetic as we understand it today. I
believe they do ... for reasons I indicated in my previous post and will
revisit in a moment.

(III) Steve's remarks:

This brings us to Steve Simpson's remarks. Steve wants to stir the pot in a
way that I don't want to and never intended to stir it. So, he presents my
view as one of antipathy to logic ... saying that mathematical induction is
'illogical'. Of course, I didn't--and wouldn't--want to say that since use
of the word 'illogical' suggests that there I see something irrational or
incoherent or absurd or nonsensical about mathematical induction. I don't.
Nor was I intending any kind of put-down of logic or logicians.

What I intended is ... well ... what I said--namely:

"There is something carried by reasoning by mathematical
induction that does not seem to be sheerly a product of its 'logical
content'. The sense in which this is true is the sense in which, then, I
want to say that mathematical reasoning is not 'reducible' to logical
reasoning."

Steve says that I give no 'real' example that illustrates my point. I
thought I did ... that is, I thought I gave an example that illustrated MY
point. Of course, my point is not the 'point'--the 'gratuitous slap' at
logic--that Steve sees me as making. Still, I'm willing to develop the
example further, and also make use of Steve's example, in order to make my
point clearer. I'll begin with the former ... and ask you to indulge me the
following 'thought experiment'.

Imagine two 'knowers', K1 and K2, as described below.

K1: (a) K2 has an individual mathematical justification for 'P(1)'. (b) For
each instance 'P(n) --> P(n+1)' of '(x)(P(x) --> P(x+1))', K1 has a
distinct 'mathematical justification' (perhaps something like distinct,
separate, unrelated 'intuitions'). (c) K1 performs the infinitely many
modus ponens inferences from 'P(n)' and 'P(n) --> P(n+1)' (n„1) to
'P(n+1)'. (d) K1 has the ability to logically 'fuse' the contents of her
knowledge of 'P(1)' and the conclusions of the infinitely many modus ponens
inferences referred to in (c) into an infinite conjunction 'P(1)&P(2)& ...
&P(n)& ...'. (e) K1 has mathematical knowledge of the infinitary
proposition '(x)(x=1 v x=2 v...v x=n v ...)'. (f) K1 logically infers
'(x)P(x)' from 'P(1)&P(2)&...&P(n)&...' and '(x)(x=1 v x=2 v...v x=n v
...)' ... an inference which, in his infinitary logic, is valid.

K2: (a) K2 has an individual mathematical justification for 'P(1)'. (b) K2
has a single mathematical justification or 'reason' which justifies each of
the infinitely many different instances of 'P(n)-->P(n+1)'. (c) K2 has
mathematical knowledge (whatever that may be) of '(P(1)&(x)(P(x)
-->P(x+1))) --> (x)P(x)'. (d) K2 logically infers '(x)P(x)' from 'P(1)' and
'(P(1)&(x)(P(x) -->P(x+1))) --> (x)P(x)'.

Query 1: Is K1's knowledge of '(x)P(x)' epistemically equivalent to K2's
knowledge of '(x)P(x)'?

Query 2 (a narrowing of Query 1): For purposes of understanding what is
distinctive about mathematical knowledge, is there any reason to want to
distinguish the type of knowledge that K1 has of '(x)P(x)' from the type of
knowledge that K2 has of '(x)P(x)'?

My thesis: For purposes of understanding what is distinctive about
mathematical knowledge (and, in particular, knowledge obtained by genuinely
mathematical reasoning), there is an important difference between K1's
knowledge of '(x)P(x)' and K2's knowledge of '(x)P(x)'.

What is this difference? For the most part, it reflects the different types
of 'syntheses' expressed in the respective (b) clauses of the descriptions
of K1 and K2. K1's synthesis is made possible by her sheer brute logical
force. She can, as it were, put infinitely many different finite
justifications together into a single infinitary justification whose
content is the conjunction of the contents of the synthesized finite
justifications. K2's synthesis, on the other hand, consists in a bringing
together of infinitely many different singular propositions under a single
finite justification whose content is the universal generalization of those
singular propositions. I believe these syntheses to be importantly
different ... and I think they point to important differences between the
type of knowledge that K1 has of '(x)P(x)' and the type of knowledge that
K2 has of '(x)P(x)'.

It is something like these differences that Poincare was, I believe, trying
to get at in remarks such as the following:

"When the logician shall have broken up each demonstration into a multitude
of elementary operations, all correct, he still will not possess the whole
reality: this I know not what which makes the unity of the demonstration
will completely escape him.

In the edifices built up by our masters, of what use to admire the work of
the mason if we cannot comprehend the plan of the architect? Now pure logic
cannot give us this appreciation of total effect; this we must ask of
intuition."
					SM: 436 (Halsted edition)

Steve (and others too, perhaps) will think that the 'thought experiment'
just  constructed does not yield any 'real' examples. The reason why, I
suspect, is because K1 is a type of knower who seems to be far from human
in her various 'infinitary' cognitive capacities. Therefore, what could the
comparison between her and K2 stand to tell us about human mathematical
knowledge? A great deal, I believe--specifically, that the type of
knowledge of a proposition p that, ideally, mathematical proof of p is
supposed to represent cannot be conceptually reduced to the type of
knowledge that one is guaranteed to obtain when she deduces p by logically
valid means from mathematically known truths. (Note: I got interested in
the 'infinitary' setting while trying to reach a better understanding of
the omega rule and the type of 'completeness', epistemologically speaking,
that adding it to PA would bring about. My conclusion was that an omega
reasoner, though impressive in her 'logical' power, would not generally
reach the level of epistemic achievement of an ordinary 'finite' knower
with the capacity for reasoning via mathematical induction. The reason was
that the omega reasoner would miss the 'pattern' or 'architecture' that the
inductive reasoner makes use of ... and that it was this grasp of pattern
signified a greater epistemic achievement than the infinitary logical
fusion of the omega reasoner.Therefore, the type of power symptomatic of an
omega reasoner is not the same type of power that is wanted for optimal
mathematical development.)

Similar arguments can be given for knowers not having infinitary powers,
but I'll not go into that now.

Mic Detlefsen




**************************
Michael Detlefsen
Department of Philosophy
University of Notre Dame
Notre Dame, Indiana  46556
U.S.A.
e-mail:  Detlefsen.1 at nd.edu
FAX:  219-631-8609
Office phones: 219-631-7534
	           219-631-3024
Home phone: 219-273-2744
**************************