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

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

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

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

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

В статье не хватает ссылок на источники (см. рекомендации по поиску). Информация должна быть проверяема, иначе она может быть удалена. Вы можете отредактировать статью, добавив ссылки на авторитетные источники в виде сносок. (13 мая 2011)