Author |
Topic: Erroneous induction... or is it? (Read 4472 times) |
|
Pietro K.C.
Full Member
 
Gender: 
Posts: 213
|
 |
Erroneous induction... or is it?
« on: Dec 2nd, 2002, 4:37pm » |
 Quote  Modify
|
In one of your archaeological excavations in the egyptian pyramids, you have come across an inductive proof that all natural numbers are equal. There is every evidence that a very advanced alien race is responsible for the proof, but your little mind is not ready for the consequences. In a desperate attempt to salvage your mathematical beliefs, you must find a mistake in it, thus remaining blind to the TRUTH, but rescuing "sanity". The proof is given below.
CLAIM
For every pair of natural numbers x,y, x = y holds.
PROOF
Let max(x,y) = n (max defined in the usual way). We shall proceed by induction on n.
The base case is clear: if max(x,y) = 0 for natural numbers x,y, then obviously x=y.
Now suppose max(x,y) = k+1, and consider x' = x-1, y' = y-1. It is readily seen that max(x',y') = k. Now, by the induction hypothesis, we must have x' = y', from which follows
x' + 1 = y' + 1
x = y,
as claimed. Therefore, all natural numbers are equal.
COROLLARY
The only rational number is 1. Hence, there exists no such thing as two different Cauchy sequences of rationals, and there can be no such thing as real numbers other than 1.
|
|
 IP Logged |
"I always wondered about the meaning of life. So I looked it up in the dictionary under 'L' and there it was --- the meaning of life. It was not what I expected." (Dogbert)
|
|
|
TimMann
Senior Riddler
Gender:
Posts: 330
|
|
Re: Erroneous induction... or is it?
« Reply #1 on: Dec 2nd, 2002, 6:31pm » |
Quote Modify
|
Here's the flaw: In the induction step, there is no guarantee that x' and y' will both be natural numbers.
|
|
IP Logged |
http://tim-mann.org/
|
|
|
Brett Danaher
Guest
|
|
Re: Erroneous induction... or is it?
« Reply #2 on: Dec 3rd, 2002, 6:48am » |
Quote Modify
 Remove
|
I'm sorry, I just don't get this whole proof. I'm not a mathematician but I have basic training in induction.
I understand up to and including the base case of max(x,y)=0.
I then agree with the statement regarding the max(x,y) and max(x',y') although I don't know how that helps. (also, the above poster made a good point about the fact that x' and y' might not be natural numbers).
I don't understand the following statement "now, by the induction hypothesis, we must have x' = y'." Why must that follow? The form of the induction hypothesis in general is "if it is true for the ancestors, it must be truth for the descendents.....or if it is true for n, then it must be true for n+1" I don't see that in your proof and I don't understand from where you get x'=y'.
Certainly if I could ever prove that all x' are equal to all y', I could easily prove all x=y.
|
|
IP Logged |
|
|
|
Pietro K.C.
Full Member
Gender:
Posts: 213
|
|
Re: Erroneous induction... or is it?
« Reply #3 on: Dec 3rd, 2002, 8:56am » |
Quote Modify
|
The induction is in n = max(x,y). If we suppose max(x,y) = n+1, then max(x',y') = n, which is the "ancestor", and this is where we use the induction hypothesis. In precise terms, the induction hypothesis states, "For any x,y, if max(x,y) = n, then x=y". Since we made x',y' such that max(x',y') = n, it must follow that x' = y'.
|
|
IP Logged |
"I always wondered about the meaning of life. So I looked it up in the dictionary under 'L' and there it was --- the meaning of life. It was not what I expected." (Dogbert)
|
|
|
Brett Danaher
Guest
|
|
Re: Erroneous induction... or is it?
« Reply #4 on: Dec 3rd, 2002, 12:31pm » |
Quote Modify
Remove
|
Took me a little while to brush off the old induction skills, but Pietro your explanation helped a lot.
I appreciate the fact that people here are not impatient and are willing to state things out for those of us who are out of practice. Anyway, I actually love this little proof and the fallacy. The way I now understand it, x-1 and y-1 are not guaranteed to be natural numbers (x or y are natural numbers, but if one of them is zero then x-1 or y-1 goes below the "floor" of zero). And the basis for the induction only works when your numbers cannot go below zero, thus max(x,y)=0 yield x must equal y. As soon as you go beyond natural numbers into integers, the basis fails.
This is correct?
|
|
IP Logged |
|
|
|
TimMann
Senior Riddler
Gender:
Posts: 330
|
|
Re: Erroneous induction... or is it?
« Reply #5 on: Dec 3rd, 2002, 1:47pm » |
Quote Modify
|
Almost correct. Let's get the terminology right first.
The induction step in proving a proposition P(n) by induction is the lemma that if P(k) is true, then P(k+1) is true. In this lemma, the induction hypothesis is that P(k) is true. The usual way of proving "if a then b" statements is to provisionally assume that a is true, then derive b. So in doing the induction step, we get to assume that the induction hypothesis is true.
The base case is the lemma that P(0) is true.
In this pseudo-proof, the base case is correct. The problem is that the proof of the induction step doesn't work, because it needs something stronger than the induction hypothesis. The induction hypothesis here is that if x' and y' are natural numbers and max(x', y') = k, then x' = y'. But since we don't know that x' and y' are natural numbers, the induction hypothesis isn't sufficient to prove what we are trying to prove. So the whole proof falls down.
That's why I said this is the flaw. It's not just a "good point." 
|
| « Last Edit: Dec 3rd, 2002, 1:48pm by TimMann » |
IP Logged |
http://tim-mann.org/
|
|
|
Brett Danaher
Guest
|
|
Re: Erroneous induction... or is it?
« Reply #6 on: Dec 4th, 2002, 6:43am » |
Quote Modify
Remove
|
Ok, let me try to get this straight. I'll reorganize things a bit in my own terms but I don't think it will make a difference.
We're going to try to show that if max(x,y)=n for all x,y,n in the set of Naturals, then x=y. Since the max of two numbers is always some value n, that would imply that all natural numbers are equal.
Base Case - max(x,y)=0, x and y must be 0 therefore x=y.
Induction hypothesis - If max(x,y)=n then x=y
Induction step, prove - If max(x,y) = n+1 then x=y
Since max(x,y) = n+1, max (x-1,y-1) = n+1-1 = n
Induction hypothesis says that therefore x-1 = y-1
Therefore x=y.
Now I proved it for 0, then I "proved" that if it's true for n it's also true for n+1. QED.
Is that correct?
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print