Date: Jan 30, 2013 10:47 AM
Author: Dave L. Renfro
Subject: Re: Proving a definition of multiplication (wrong) by induction

Jonathan Crabtree wrote (in part):

http://mathforum.org/kb/message.jspa?messageID=8185797

> a = a added to a 1 time (the proposition)
> 
> a does NOT equal a + a

I don't see anything of a mathematical concern here. You're
simply arguing over the English-language meaning of the phrase
"a added to a b times". Here are some examples of the statements
you're dealing with:

P(1) represents "a = 1*a"
P(2) represents "a + a = 2*a"
P(3) represents "a + a + a = 3*a"
P(4) represents "a + a + a + a = 4*a"

Each of these can be proved without mathematical induction
(in an appropriate formal setting).

We can also prove (in an appropriate formal setting) things like:

"P(1) and P(2)"

"P(1) and P(2) and P(3)"

"P(1) and P(2) and P(3) and P(4)"

This is simply because, in propositional logic, we have things like:

A,B |- (A and B)

A,B,C |- (A and B and C)

A,B,C,D |- (A and B and C and D)

That is, assuming A, B you can obtain "A and B". I say "obtain" because,
depending on the logical system you're working in, this might be an
axiom. Of course, a 1-line proof consisting of an axiom is technically
a proof of that axiom (in the sense that "proof" is understood in formal
logic), but I think there is less misunderstanding in the present context
if I say "obtain" rather than "prove".

The previous statements can be rewritten as follows:

(for all n in {1, 2})(P(n))

(for all n in {1, 2, 3})(P(n))

(for all n in {1, 2, 3, 4})(P(n))

Each of the statements just above can be proved without mathematical
induction.

To give a more complicated example, we don't need mathematical
induction to prove the following (in an appropriate formal setting,
ultrafinitistic views excepted):

(for all n in {1, 2, 3, ..., 10^10000})(P(n))

However, you do need mathematical induction to prove [*]:

[*] (for all n in {1, 2, 3, ...})(P(n))

Incidentally, being able to prove [*] (in an appropriate formal
setting) is one thing, while proving that one can't prove [*]
without mathematical induction is another thing. The "another
thing" requires a bit of formal logical training just to correctly
understand what it means to prove that something can't be proved
without mathematical induction.

Now part of the problem in proving [*] by mathematical induction
is to assign an unambiguous meaning to the statement P(n) for each
positive integer n (what you seem to be hung up on), but this is a
meta-language issue and not something that lies within the formal
system that the proofs take place in.

Dave L. Renfro


Message was edited by: Dave L. Renfro