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

Доказательство одноцветности всех лошадей — ошибочное доказательство того, что все лошади одного цвета, придуманное венгерским математиком Пойа^[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 лошадей одного цвета.

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

Опровержение

Противоречие возникает из-за того, что шаг индукции не сообразуется с базой. Он верен лишь при K >= 2. При K = 1 (база индукции) получаемые множества оставшихся лошадей не будут пересекаться, и утверждения о равенстве цветов всех лошадей сделать нельзя.

Вариант «доказательства»

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

База индукции: Очевидно, бывают лошади белого цвета. Выберем одну и с неё начнём цепочку индукции.

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

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

Опровержение

Здесь ошибка возникает уже в базе: происходит подмена квантора всеобщности («все») на квантор существования («существует»).

Ссылки

1. ↑ Pólya George (1954). Mathematics and Plausible Reasoning. Volume 1: Induction and Analogy in Mathematics. — Princeton, New Jersey: Princeton University Press. — p. 120. Русский перевод: Пойа Д. Математика и правдоподобные рассуждения. — 2-е изд., испр. — М.: Наука, 1975. — C. 140.

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