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