wu :: forums
« wu :: forums - Erroneous induction... or is it? »

Welcome, Guest. Please Login or Register.
Sep 18th, 2024, 9:33pm

RIDDLES SITE WRITE MATH! Home Home Help Help Search Search Members Members Login Login Register Register
   wu :: forums
   riddles
   easy
(Moderators: william wu, towr, SMQ, Eigenray, Grimbal, ThudnBlunder, Icarus)
   Erroneous induction... or is it?
« Previous topic | Next topic »
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: Erroneous induction... or is it?  (Read 4472 times)
Pietro K.C.
Full Member
***





115936899 115936899    
WWW

Gender: male
Posts: 213
Erroneous induction... or is it?  
« on: Dec 2nd, 2002, 4:37pm »
Quote Quote Modify 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
****






   
WWW

Gender: male
Posts: 330
Re: Erroneous induction... or is it?  
« Reply #1 on: Dec 2nd, 2002, 6:31pm »
Quote Quote Modify 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

Email

Re: Erroneous induction... or is it?  
« Reply #2 on: Dec 3rd, 2002, 6:48am »
Quote Quote Modify Modify Remove 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
***





115936899 115936899    
WWW

Gender: male
Posts: 213
Re: Erroneous induction... or is it?  
« Reply #3 on: Dec 3rd, 2002, 8:56am »
Quote Quote Modify 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

Email

Re: Erroneous induction... or is it?  
« Reply #4 on: Dec 3rd, 2002, 12:31pm »
Quote Quote Modify Modify Remove 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
****






   
WWW

Gender: male
Posts: 330
Re: Erroneous induction... or is it?  
« Reply #5 on: Dec 3rd, 2002, 1:47pm »
Quote Quote Modify 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." Smiley
« Last Edit: Dec 3rd, 2002, 1:48pm by TimMann » IP Logged

http://tim-mann.org/
Brett Danaher
Guest

Email

Re: Erroneous induction... or is it?  
« Reply #6 on: Dec 4th, 2002, 6:43am »
Quote Quote Modify Modify Remove 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
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print

« Previous topic | Next topic »

Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board