Results 1 to 7 of 7

Thread: False proof by induction

  1. #1
    Senior Member
    Joined
    Mar 2017
    From
    Toronto
    Posts
    295
    Thanks
    2

    Question False proof by induction

    There's this classic proof by induction that is FALSE:

    The claim is that cars are all the same colour. This is equivalent to the claim that any set of cars
    must contain cars of the same colour. The claim is trivially true for the base case of n = 1 cars
    since, after all, a car has only one colour. Next, we’ll assume that the claim is true for all sets of
    n cars are we’ll now consider a set of n + 1 cars, {car 1, car 2, ..., car n, car n + 1}. We’ll consider
    two subsets of this set C1 = {car 1, car 2, ..., car n} and C2 = {car 2, ..., car n, car n + 1}, each of
    which is a set of n cars. Therefore, by our induction hypothesis, C1 and C2 only contain cars
    of a single colour. But then again, since there’s overlap in the entries of C1 and C2 the colour
    of each must be the same. Therefore {car 1, car 2, ..., car n, car n + 1} must have only cars of a
    single colour. Thus, cars are all of the same colour

    Apparently to suggest that n = 1 implies n = 2 is false (therefore proving the proof as false) and I want to more clearly understand why that would be the case. Does it have to do with how C1 and C2 are related to each other? Perhaps you can't suggest that car n in C1 is the same colour as car n in C2?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Dec 2013
    From
    Colombia
    Posts
    1,839
    Thanks
    592

    Re: False proof by induction

    I think that there is a confusion over what object has the property "colour". Is it the members of the set or the set itself?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Joined
    Nov 2013
    From
    California
    Posts
    5,919
    Thanks
    2491

    Re: False proof by induction

    The statement "all cars are the same colour" is much more restrictive than "any set of $n$ cars must contain cars of the same colour".

    The second statement allows as few as 2 of the $n$ cars to share a colour. The first statement insists all $n$ are the same colour.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Nov 2010
    Posts
    3,014
    Thanks
    1152

    Re: False proof by induction

    For $n=1$, the sets are {car 1=car n} and {car n+1 = car 2}. There is no overlap of cars between the two sets. It is only when $n>2$ that you get an overlap of cars (namely car 2 is in both sets).
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Joined
    Nov 2010
    Posts
    3,014
    Thanks
    1152

    Re: False proof by induction

    Sorry, I was in a rush and did not finish explaining. According to what you wrote: "But then again, since there’s overlap in the entries of C1 and C2 the colour of each must be the same. " To write that mathematically, it is saying that for the sets $C_1 = \{ \text{car 1}, \text{car 2}, \ldots , \text{car n} \}$ and $C_2 = \{ \text{car 2}, \ldots , \text{car n+1} \}$, you have $C_1 \cap C_2 = \{ \text{car 2}, \ldots, \text{car n} \}$ (this appears to be a non-empty intersection). However, what this notation is saying is that the smallest car number in the intersection of $C_1$ and $C_2$ is $2$ and the largest car number in the intersection of the two sets of cars is $n$. So, when $n=1$, the intersection contains all car numbers at minimum two and at maximum 1. There are no numbers that satisfy those criteria, so the intersection of the two sets is empty, contrary to what is written. That is why the induction fails.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor

    Joined
    Apr 2005
    Posts
    19,454
    Thanks
    2892

    Re: False proof by induction

    That is also famous as the "horse of a different color" proof with horses instead of cars (so very old, I guess). The error is that while the initial case is for a set containing one horse (or car) the method for going from n to n+1 requires that n be at least 2.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Senior Member
    Joined
    Mar 2017
    From
    Toronto
    Posts
    295
    Thanks
    2

    Re: False proof by induction

    Quote Originally Posted by SlipEternal View Post
    There are no numbers that satisfy those criteria, so the intersection of the two sets is empty, contrary to what is written. That is why the induction fails.
    what do you mean by this? for some reason I only understood everything up until that point...
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Is this a false proof?
    Posted in the Calculus Forum
    Replies: 8
    Last Post: Jul 23rd 2010, 03:26 PM
  2. True/False Proof
    Posted in the Calculus Forum
    Replies: 1
    Last Post: Feb 10th 2010, 05:42 PM
  3. Mathemtical Induction Proof (Stuck on induction)
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: Mar 8th 2009, 10:33 PM
  4. False proof 1=2
    Posted in the Math Challenge Problems Forum
    Replies: 12
    Last Post: Dec 28th 2008, 02:49 PM
  5. False Proof: -1 = 2
    Posted in the Pre-Calculus Forum
    Replies: 13
    Last Post: Nov 21st 2007, 10:40 AM

Search Tags


/mathhelpforum @mathhelpforum