Monochromatic cows

September 1998


The following is a fallacious proof that "all cows in a field are the same colour". A quick trip out into the countryside will soon provide a counter-example to the Theorem - but where's the flaw in the argument?

Theorem: All cows in a field are the same colour

Proof by induction on the number of cows

Induction hypothesis: n cows in a field are the same colour, for all n=1,2,3,4,...

Initial Step Clearly one cow in a field is the same colour as itself, so the induction hypothesis is true for n=1.

Induction Step Now suppose n is at least 1, we have n cows in a field F, and that the induction hypothesis has been proved for all fields containing at most n cows. By the induction hypothesis all the cows in F are the same colour.

Firstly, remove any cow from F and put it to one side. Now take a cow from some other field and put it in field F. We again have n cows in field F, so by the induction hypothesis they are all the same colour. Finally, put back the first cow you thought of. We already know that it's the same colour as all the other cows in F, and so now we have n+1 cows in field F, and they're all the same colour. This completes the induction step!

Q.E.D.

Solution

Comments

Induction hypothesis is

Induction hypothesis is governed by principle ordering which has been neglected when we remove 1 cow from the set and replace with another random one outside the set.