Доказательство одноцветности всех лошадей
Доказательство одноцветности всех лошадей — математический софизм, ошибочное доказательство того, что все лошади одного цвета, придуманное венгерским математиком Пойей[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 лошадей одного цвета.
Отсюда следует, что все лошади одного цвета. Утверждение доказано.
Ошибка в доказательстве
Здесь ошибка возникает уже в базе: происходит подмена квантора всеобщности («все») на квантор существования («существует»). Иными словами противоречие возникает из-за того, что шаг индукции верен лишь при [math]\displaystyle{ K\geqslant2 }[/math]. При [math]\displaystyle{ K=1 }[/math] получаемые множества оставшихся лошадей не будут пересекаться, и утверждение о равенстве цветов всех лошадей сделать нельзя.
Примечания
- ↑ 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.
В статье не хватает ссылок на источники (см. также рекомендации по поиску). |