# Thread: False proof by induction

1. ## 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?

2. ## 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?

3. ## 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.

4. ## 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).

5. ## 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.

6. ## 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.

7. ## Re: False proof by induction

Originally Posted by SlipEternal
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...