All Horses are the Same Colour

Paradox

All horses are the same colour.

Reasoning

We prove this by induction on the number of horses in any given set of horses.

For all $n \in \N^*$, let $P \left({n}\right)$ be the proposition:

"For all sets of horses of size $n$, all $n$ horses are the same colour."

Basis for the Induction

$P(1)$ is true, as this just says:

"In every set which consist of $1$ horse, each horse in that set is the same colour."

Every horse is the same colour as itself, so this is trivially true.

This is our basis for the induction.

Induction Hypothesis

Now we need to show that, if $P \left({k}\right)$ is true, where $k \ge 1$, then it logically follows that $P \left({k+1}\right)$ is true.

So this is our induction hypothesis:

"For all sets of horses of size $k$, all $k$ horses are the same colour."

Then we need to show:

"For all sets of horses of size $k+1$, all $k+1$ horses are the same colour."

Induction Step

This is our induction step:

Let $S_{k+1}$ be a set of $k+1$ horses.

Let us number the horses $h_1, h_2, \ldots, h_{k+1}$.

We define the subsets:

• $T_a \subset S_{k+1}: T_a = \left\{{h_1, h_2, \ldots, h_k}\right\}$
• $T_b \subset S_{k+1}: T_b = \left\{{h_2, h_3, \ldots, h_{k+1}}\right\}$

Clearly, each of $T_a$ and $T_b$ have $k$ horses in them.

By the induction hypothesis, all the horses in $T_a$ are the same colour, and all the horses in $T_b$ are also all the same colour.

Now we consider the set $T_c$:

$T_c \subset S_{k+1}: T_c = \left\{{h_2, h_3, \ldots, h_k}\right\}$

We see that $T_c$ contains horses in $T_a$ and also horses in $T_b$, and all the horses in $T_c$ are the same colour.

Now horses can't just change colour, so we are forced to the conclusion that all the horses in $T_a$ and all the horses in $T_b$ are all the same colour.

That must mean that all the horses in $S_{k+1}$ are the same colour as well.

So $P \left({k}\right) \implies P \left({k+1}\right)$ and the result follows by the Principle of Mathematical Induction.

Therefore:

For all $n \in \N$, for every set containing $n$ horses, all the horses in that set are the same colour.

That is, all horses are the same colour.

$\blacksquare$

Resolution

This is a falsidical paradox.

The error in the reasoning arises from the fact that the argument does not hold when $k = 2$.

If it were the case that all sets of $2$ horses were one-coloured, then the proof would hold.

But consider $T_a = \left\{{h_1}\right\}, T_b = \left\{{h_2}\right\}$.

Sure enough, all the horses in $T_a$ are all the same colour, and so are all the horses in $T_b$ all the same colour.

But $T_c = \left\{{}\right\}$.

So there is nothing to suggest that all the horses in $T_a$ are the same colour as those in $T_b$.

$\blacksquare$

History

This paradox was originally raised by George Pólya, and appears in his 1954 work Induction and Analogy in Mathematics.