# All Horses are the Same Colour

## Contents

## 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_{> 0}$, 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 \subseteq S_{k+1}: T_a = \left\{{h_1, h_2, \ldots, h_k}\right\}$
- $T_b \subseteq 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 \subseteq 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 subset:

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

has horses $h_1$ and $h_{k+1}$ removed; this yields a set of cardinality two less than that of $S_{k+1}$.

But if $S_{k+1}$ has only one element, $T_c$ would have $-1$ elements, an absurdity.

So the induction hypothesis can be applied only for $k \ge 2$, not for $k \ge 1$ as claimed.

However, since the basis for the induction dealt only with $k = 1$, the case for $k = 2$ needs to be addressed explicitly.

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.

Defining $T_c$ as the set of horses $T_a$ and $T_b$ have in common, $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$

## Also known as

This paradox is sometimes known as the **horse paradox**.

It is also seen otherwise, less colorfully presented (pun intended), as:

Its argument and resolution are the same.

## History

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

It arose from the popular (at the time: the 1930's) colloquialism: "*That's* a horse of a different color!" meaning: "That's unexpectedly new and different."

## Sources

- 1964: W.E. Deskins:
*Abstract Algebra*... (previous) ... (next): Exercise $2.1: \ 10$