Идеи с границы познания. Эйнштейн, Гёдель и философия науки

Здесь, пожалуй, уместно сказать несколько слов о том, как математики вообще относятся к доказательствам утверждений, особенно таких, которые, подобно проблеме четырех красок, охватывают бесконечное множество случаев. Один из методов доказательства называется математической индукцией. Иногда его сравнивают с тем, как падает бесконечный ряд косточек домино. Главное в методе математической индукции – показать, что если такое-то и такое-то утверждение верно для числа n, то тогда оно верно и для n+1. Аналогия с домино означает, что каждая падающая косточка сбивает следующую в очереди, и в конце концов упадут все. Чтобы применить математическую индукцию к проблеме четырех красок, нужно показать, что если каждая карта, на которой обозначено n областей, может быть раскрашена четырьмя красками, это возможно и для карты, на которой n+1 областей. Как выяснилось, это чудовищно трудно. Когда добавляешь на данную карту «эн-плюс-первую» область, иногда приходится перекрасить некоторые или все n остальных областей, чтобы новая область вписалась в четырехцветную схему. Общее правило такой перекраски никому сформулировать не удалось. Так что никакого падения доминошек.

К счастью, есть и другой подход к доказательству утверждения, охватывающего бесконечно много случаев: доказательство от противного. Берешь утверждение, противоположное тому, которое хочешь доказать, и доводишь его до абсурда. В случае проблемы четырех красок это означает, что мы предполагаем, что существуют контрпримеры, то есть карты, для которых нужно пять и более красок, а затем выводим из этого предположения противоречие. Поскольку подобные контрпримеры нарушают принцип четырех красок, их принято в обиходе называть «криминальными». Если криминальные карты существуют, в них может быть любое количество областей, но полезно сосредоточиться на тех, где областей абсолютный минимум. Такие карты называют «минимальными» криминальными картами. (Очевидно, чтобы потребовалось пять цветов, на минимальной криминальной карте должно быть не меньше пяти областей.) Любая карта с меньшим числом областей, чем минимальная криминальная, по определению законопослушна, то есть ее можно раскрасить в четыре цвета.

Мы оказались в занятном положении. Возьмем карту, которая может оказаться минимальной криминальной. Выберем любую область и сожмем ее в точку. Это уменьшит количество областей на одну. Теперь у редуцированной карты не хватает областей, чтобы считаться криминальной, поскольку у нее на одну область меньше, чем у минимальной криминальной карты, с которой мы начали. Следовательно, редуцированная карта законопослушна, а значит, ее можно раскрасить четырьмя красками. Раскрасим ее.

Теперь обратим процесс. Вернем на карту область, которую мы сжали в точку – раздуем эту область обратно. Теперь у нас есть первоначальная карта, на которой как следует раскрашены все области, кроме той, которую мы сжали, а потом восстановили. Зададимся вопросом: есть ли способ раскрасить восстановленную область так, чтобы она вписалась в четырехцветовую схему, которую мы применили к редуцированной карты? Это, конечно, зависит от того, какую область мы выбрали для сжатия и восстановления. Если, например, была выбрана область, граничащая только с тремя другими, вам повезло: когда вы ее восстановите, из четырехцветной схемы останется один цвет, который отличит восстановленную область от трех соседок. Но тогда вы смогли раскрасить исходную карту четырьмя красками. Значит, предполагаемая минимальная криминальная карта вовсе не была криминальной!

Тогда очевидно, что карта, претендующая на звание минимальной криминальной, не должна содержать областей, граничащих только с тремя другими областями. Иначе (1) можно сжать такую область в точку, таким образом снизив число областей на одну и сделав так, чтобы карта оказалась ниже минимально-криминального порога и, следовательно, оказалась законопослушной, (2) раскрасить редуцированную законопослушную карту четырьмя красками, (3) затем восстановить сжатую область, раздув ее снова, и (4) раскрасить восстановленную область одним из четырех цветов, не совпадающим с цветами ее трех соседок, тем самым включив восстановленную область в четырехцветную схему. И тогда исходная карта в конце концов оказывается законопослушной.