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

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

Первоначальный вариант доказательства содержится в одном из упражнений к Главе 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}$ получаемые множества оставшихся лошадей не будут пересекаться, и утверждение о равенстве цветов всех лошадей сделать нельзя.

Примечания