Неконструктивные доказательства
В отличие от конструктивных доказательств, предоставляющих сам объект или дающих метод его построения, неконструктивные доказательства убеждают нас в существовании определённого вида объекта без указания конкретного примера.
Неконструктивно доказываются многие теоремы существования. Неконструктивными являются все рассуждения от противного, например, принцип Дирихле. В простейшей и самой распространённой формулировке этот принцип утверждает, что если кролики рассажены в клетки, причём число кроликов больше числа клеток, то хотя бы в одной из клеток находится более одного кролика.
Доказательство принципа Дирихле основано на предположении, что в каждой клетке сидит менее двух кроликов (один или ни одного). Тогда во всех n клетках в совокупности сидит не более n кроликов. Противоречие.
Приведём ещё несколько примеров неконструктивных доказательств.
Пример 1. Рассмотрим доказательство Евклида бесконечности количества простых чисел.
Предположим, что Р — самое большое простое число. Тогда Р! +1 не делится ни на одно из имеющихся простых чисел, а значит, новое простое число, и оно, очевидно, больше Р. Получили противоречие.
Кстати, приведённое в Википедии конструктивное доказательство бесконечности множества простых чисел является ошибочным:
Легко проверить, что уже a₄ = 7! + 1 = 5041 = 71². Предлагаем читателю самостоятельно разобраться и написать в комментариях, в чём тут ошибка.
Пример 2. Трое играют в настольный теннис на "вылет", то есть игрок, проигравший партию, уступает место игроку, не участвовавшему в ней. В итоге Никанор сыграл 10 партий, Филимон – 15, а Агафон – 17. Кто из них проиграл в восьмой партии?
Решение. Всего была сыграна (10 + 15 + 17) : 2 = 21 партия. Заметим, что никто не мог пропускать две партии подряд. Значит, Никанор играл все партии с чётным номером и только их. Так как он не играл в девятой партии, то восьмую партию он проиграл.
Пример 3. Можно ли, используя только цифру 1, написать число, кратное 2023 (в общем случае, кратное любому натуральному числу d, не делящемуся на 2 и на 5)?
Решение. Рассмотрим числа, в десятичной записи которых содержатся одни единицы: 1, 11, 111, ... . Поскольку таких чисел бесконечно много, то среди них найдутся два числа, имеющие одинаковый остаток при делении на d. Разность этих чисел будет иметь вид a = 1...10...0, т.е. будет записана несколькими единицами, за которыми следуют нули; кроме того, число a делится на d. По условию d взаимно просто с 10, следовательно, число из одних единиц, полученное из a вычёркиванием нулей, также делится на d. Таким образом, доказана возможность построить такое число без указания способа его построения.
Отметим ещё один важный приём неконструктивного доказательства существования объекта с заданными свойствами, получивший название вероятностного метода. Он был предложен венгерским математиком П.Эрдёшем (1943 г.).
Следующий пример взят из лекции замечательного А.М. Райгородского https://vk.com/video-91031095_456244845
Пример 4. В матклассе учатся 30 школьников. Выделено 15 направлений (комбинаторика, теория чисел, геометрия, ...), по каждому из которых определены 5 лучших учеников класса — их распределение среди учеников класса может оказаться произвольным. Требуется разделить класс на две (возможно неравные) группы (например, для их отправки на два турнира, проводимых одновременно в разных городах) таким образом, чтобы в каждой группе присутствовал хотя бы один ученик из каждой пятёрки лучших.
Решение. Будем рассаживать школьников по двум аудиториям случайным образом, подбрасывая монетку: в случае выпадения решки i-й школьник идёт в 1-ю аудиторию, орла — во 2-ю. Пусть Mⱼ — событие, состоящее в том, что j-я пятёрка лучших школьников вся целиком оказалась в одной аудитории.
Для нахождения вероятности события, что все пять школьников соберутся, например, в 1-й аудитории, нужно перемножить вероятности независимых событий попадания каждого школьника в эту аудиторию, получим:
(½)⁵ = ⅟₃₂. Также вероятность попадания во 2-ю аудиторию равна ⅟₃₂.
Тогда вероятность собраться всем школьникам одной j-й пятёрки в одной аудитории равна Р(Mⱼ) = 2 ∙ ⅟₃₂ = ⅟₁₆.
Теперь оценим вероятность события, состоящего в том, что школьники хотя бы одной пятёрки окажутся в одной аудитории — очевидно, вероятность такого события никак не меньше просто суммы вероятностей этих событий:
Р(M₁ U M₂ U ... U M₁₅) < Р(M₁) + Р(M₂) + ... + Р(M₁₅) = ¹⁵⁄₁₆ < 1.
Если вероятность какого-то события меньше единицы, то вероятность его отрицания положительна. А отрицание этого события в точности соответствует тем рассадкам, когда представители каждой пятёрки присутствуют в обеих аудиториях. Это означает, что множество тех исходов, которые благоприятствуют этому событию, не пусто.
Таким образом, показано, что требуемое разбиение множества учеников класса всегда возможно.
Пример 5. Требуется установить, может ли иррациональное число a в степени иррациональное число b быть числом рациональным.
Построить пример, т.е. дать конструктивное доказательство, не составляет труда. Например, годятся a = √2, b = log₂_25.
Но представляет интерес неконструктивное доказательство.
Рассмотрим число
Мы исходим из того, что не знаем, является оно рациональным или иррациональным. Рассмотрим обе эти возможности.
Предположим, что это число рационально. Тогда оно служит примером положительного ответа на поставленный вопрос.
Теперь предположим, что оно иррационально. Тогда возведём его в степень √2:
Видим, что в этом случае мы снова получили положительный ответ на поставленный вопрос. Таким образом, мы сумели ответить на вопрос задачи, не предъявив ни одной такой пары чисел a и b.
В качестве лирического отступления можно отметить, что на самом деле выбранное число иррационально. Это вытекает, например, из теоремы Гельфонда-Шнайдера (доказанной Р.О. Кузьминым), утверждающей, что если a, b — алгебраические числа (a ≠ 0, a ≠ 1) и b иррационально, то aᵇ — трансцендентное число. Упомянутая теорема является решением седьмой проблемы Гильберта, однако она не имеет никакого отношения к справедливости неконструктивного доказательства, приведённого выше. Ведь даже если бы в принципе невозможно было установить, рациональным или иррациональным числом является x, всё равно наше доказательство было бы верным... Или нет?
Неконструктивные способы доказательства основаны на логическом законе исключённого третьего: из двух противоположных суждений об одном и том же предмете одно необходимо истинно, а другое ложно ("либо А, либо не-А, третьего не дано"). Например, если имеется конечное множество, то, очевидно, верно только одно из утверждений: "В данном множестве есть объект с указанным свойством" и "В этом множестве нет такого объекта". Эта очевидность основана на нашей конструктивной, алгоритмической возможности подвергнуть эти утверждения проверке с помощью перебора всех элементов множества. Получается, в основе неконструктивных доказательств скрытым образом лежит возможность их конструктивной проверки.
Когда мы говорим "либо x рационально, либо нет", то возникает вопрос, насколько осмысленно это утверждение в отрыве от возможности описать процедуру, позволяющую решить, какое же оно на самом деле (поскольку невозможно перебрать все элементы бесконечного множества); более того, мы даже допускаем, что этот вопрос в принципе может оказаться нерешаемым!
Возможно, кому-то из читателей сам этот вопрос может показаться праздным, а для кого-то, наоборот, станет поводом серьёзно задуматься. Он имеет отношение не к самой математике, а, скорее, к её логическим и философским основаниям. Впервые на него обратил внимание в начале XX в. голландский математик Л. Брауэр. В то время в теоретико-множественном подходе к обоснованию математики были обнаружены серьёзные противоречия, и математики искали разные пути выхода из создавшегося кризиса. Критика Брауэром закона исключённого третьего и основанного на нём метода неконструктивных доказательств привела к созданию нового направления математики — интуиционизм, а позже — конструктивизм.
Вопрос о том, обладает ли закон исключённого третьего непререкаемым авторитетом или в иных случаях на его использование могут быть наложены определённые ограничения, не имеет окончательного и безоговорочного решения. Хотя большинство современных математиков не подвергают его сомнению.
Вместо заключения приведём цитату из книги В.Пелевина "Бэтман Аполло":
"У китайских даосов, – сказал он, – была близкая мысль, я её своими словами перескажу. Борясь за сердца и умы, работники дискурса постоянно требуют от человека отвечать «да» или «нет». Все мышление человека должно, как электрический ток, протекать между этими двумя полюсами. Но в реальности возможных ответов всегда три – «да», «нет» и «пошел ты наhren». Когда это начинает понимать слишком много людей, это и означает, что в черепах появился люфт".
___________________________
UPD. В телеграм-канале МЭ появились комментарии к статье; в связи с чем возникло желание сделать небольшое дополнение и акцентировать внимание на определённых моментах.
Вот простая мысль: вещественное число по определению либо рационально, либо нет — третьего не дано. Откуда же может возникнуть сомнение в применимости неконструктивного доказательства?
Вопрос здесь не в том, существует ли третий сорт вещественных чисел кроме рациональных и иррациональных, а в том, допустимо ли использовать аксиому исключения в условиях отсутствия алгоритма, позволяющего этот выбор совершить. Речь идёт даже не о принципиальной возможности построить такой алгоритм (машина Тьюринга, например), а о наличии такого алгоритма.
Вы считаете, что это допустимо? Отлично! (Я тоже так считаю — потому что так проще жить.) Но есть принципиальная возможность так не считать! И есть серьёзные математики, которые живут в такой системе аксиом. (А 100 лет назад их вообще было довольно много.)
Ещё раз, это вопрос не самой математики (работы в системе аксиом), а вопрос выбора аксиоматики.
Ответ на вопрос, зачем эти интуиционисты-конструктивисты себя так истязают, отказываясь в определённых случаях от столь "естественной" аксиомы, состоит в том, что в их математике нет парадоксов теории множеств, связанных с актуальной бесконечностью.
Также на эту тему полезно взглянуть с точки зрения теоремы Гёделя (которой интуиционисты ещё не знали — доказана в 1930 г.), суть которой упрощённо можно передать следующим образом: если сложить количество всех верных (доказуемых) утверждений и неверных (их отрицаний), то полученное число будет меньше, чем количество всех утверждений вообще. Опираясь на закон исключённого третьего, мы не застрахованы от ситуации появления невыводимых утверждений (типа пятого постулата Евклида или континуум-гипотезы), истинность которых не может быть установлена в рамках существующих теорий, и которые мы можем добавить в базис, расширив теорию.
Именно поэтому конструктивисты и стремятся придумать такие правила рассуждения, в которых нет рассуждений от противного.