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