Циклопедия скорбит по жертвам террористического акта в Крокус-Сити (Красногорск, МО)

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

Материал из Циклопедии
Перейти к навигации Перейти к поиску
Докажем, что все собаки одной и той же породы // Алексей Покровский [13:05]

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

Утверждение формулируется так: любые N лошадей имеют одинаковый цвет. Доказательство ведется методом математической индукции.

База индукции: докажем, утверждение при N = 1. Действительно, любая одна лошадь имеет один цвет.

Теперь докажем, что если утверждение выполнено для N лошадей, то оно выполнено для N+1 лошади.

Предположим, доказано, что любые N лошадей одного цвета. Добавим к этим лошадям еще одну лошадь. Количество их станет равным N+1. Удалим одну произвольную лошадь. Количество их снова станет равным N. Поскольку уже доказано, что любые N лошадей одного цвета, то и полученное множество лошадей будет одного цвета. Перебирая (удаляя) всех лошадей по одной, снова получим N лошадей одного цвета. Таким образом, доказано, что N+1 лошадей тоже одного цвета. Беря N+2, N+3 и т. д. лошадей (и удаляя соответствующее их количество), доказываем, что все лошади одного цвета.

Данное доказательство содержит ошибку. Ошибка здесь в том, что с помощью вышеприведенных рассуждений нельзя перейти от N = 1 к N = 2, так как удалив одну лошадь из двух и оставив лошадь одного цвета (скажем, белую), а потом удалив вторую лошадь и оставив одну лошадь (скажем, серую), нельзя сделать вывод что эти две оставшиеся в первом и втором случае лошади одного цвета. Вышеописанный переход от N к N+1 сработал бы только при N от 2 и выше: действительно, если бы мы доказали, что любые 2 лошади одного цвета, то и все лошади во Вселенной имели бы один и тот же цвет.

См. также[править]

Литература[править]

  • Пойа Д. Математика и правдоподобные рассуждения. — 2-е изд., испр. — М.: Наука, 1975. — C. 140.