Доказательство одноцветности всех лошадей

Доказательство одноцветности всех лошадей — математический софизм, ошибочное доказательство того, что все лошади одного цвета, придуманное венгерским математиком Пойей. Доказательство призвано продемонстрировать ошибки, возникающие при неправильном использовании метода математической индукции.

Первоначальный вариант доказательства

Первоначальный вариант доказательства содержится в одном из упражнений к Главе VII «Математическая индукция» первого тома работы Пойи «Математика и правдоподобные рассуждения». В первоначальном доказательстве речь идёт не об одноцветности лошадей, а об одноцветности глаз девушек:

17. Равны ли любые n чисел? Вы сказали бы «Нет». Всё же мы можем попытаться с помощью математической индукции доказать обратное. Более заманчиво, однако, доказать утверждение: «у любых n девушек глаза одинакового цвета».
Для n = 1 утверждение, очевидно, верно (или «бессодержательно»). Остаётся перейти от n к n + 1. Для определённости я перейду от 3 к 4, а общий случай оставлю вам. Позвольте представить вас четырём девушкам: Анне, Белле, Вере и Галине, или, для краткости, А, Б, В и Г. Предполагается (n = 3), что глаза девушек А, Б и В одинакового цвета. Точно так же, по предположению, и глаза девушек Б, В и Г одинакового цвета (n = 3). Следовательно, глаза всех четырёх девушек А, Б, В и Г должны быть одинакового цвета. Для полной ясности можно взглянуть на диаграмму

|-------| А, Б, В и Г. |--------|

Это доказывает утверждение для n + 1 = 4, а переход, например, от 4 к 5, очевидно, не более труден.

Объясните парадокс. Можете испытать экспериментальный подход, посмотрите в глаза нескольким девушкам.

— Пойа Д. Математика и правдоподобные рассуждения. — 2-е изд., испр. — М.: Наука, 1975. — C. 140.

«Доказательство»

Доказательство одноцветности всех лошадей, шаг индукции не работает для K = 1

Доказываемое утверждение: Все лошади одного цвета. Проведём доказательство по индукции.

База индукции: Одна лошадь, очевидно, одного (одинакового) цвета.

Шаг индукции: Пусть доказано, что любые K лошадей всегда одного цвета. Рассмотрим K + 1 каких-то лошадей. Уберём одну лошадь. Оставшиеся K лошадей одного цвета по предположению индукции. Возвратим убранную лошадь и уберём какую-то другую. Оставшиеся K лошадей снова будут одного цвета. Значит, все K + 1 лошадей одного цвета.

Отсюда следует, что все лошади одного цвета. Утверждение доказано.

Ошибка в доказательстве

Здесь ошибка возникает уже в базе: происходит подмена квантора всеобщности («все») на квантор существования («существует»). Иными словами противоречие возникает из-за того, что шаг индукции верен лишь при $K\geqslant 2$. При $K=1$ получаемые множества оставшихся лошадей не будут пересекаться, и утверждение о равенстве цветов всех лошадей сделать нельзя.