Наиболее частая ошибка в «доказательстве от противного»
Идея «доказательства от противного» базируется на логической операции «следование». Эта операция записывается как
и читается как «из суждения A следует суждение B».
Несмотря на то, что по звучанию оно похоже на «из A можно вывести B», на самом деле это - некоторое описание взаимоотношений неких двух суждений, которое означает «если A истинно, то совершенно точно и B тоже истинно, а если A ложно, то B может быть как истинным, так и ложным».
При этом совершенно не обязательно существование какой-то последовательности промежуточных операций, позволяющих «чисто логически» вывести B из A. Вполне достаточно даже просто каких-то наших наблюдений.
Хотя очень часто следование одного из другого действительно логически выводимо.
Например, «когда идёт дождь, Вася всегда открывает зонт». Из «идёт дождь» в общем случае не следует, что кто-то воспользуется зонтом - у него может вообще не быть зонта, он может пользоваться вместо него плащом и так далее. Но вот конкретно про Васю мы знаем, что с ним всё так: если «идёт дождь», то «Вася открывает зонт».
Однако если дождь не идёт, то из этого не следует, что зонт Вася не откроет: мы точно не знаем, быть может, он и от снега, и от солнца тоже укрывается зонтом. Вот это и есть операция «следование», в данном случае связывающая между собой «идёт дождь» и «Вася открывает зонт».
Предположим, истинность некоторого суждения A. Проделаем с ним и какими-то другими суждениями, полагаемыми нами всегда истинными, то есть «системой аксиом», какие-то логические преобразования и получим
Однако не будем на этом останавливаться. Проделаем какие-то другие преобразования и теперь уже получим, что
Восклицательный знак означает логическое отрицание - «не-A», «не-B».
Например, у Пети есть только синие кубики. Иных кубиков у него в данный момент нет. Он держит в руках кубик. Какого этот кубик цвета?
Предположим, что кубик - не синий (это будет наше суждение A). Сие означает, что «У Пети есть не синие кубики» (суждение B) - ведь один из таких он держит в руках.
Однако из суждения, которое мы объявили «аксиомой»: «у Пети есть только синие кубики», следует, что «у Пети нет не синих кубиков». Это утверждение всегда верно в данной системе аксиом, поскольку является прямым следствием одной из них (в данном случае, единственной).
Суждение
является всегда истинным, поскольку справа от стрелки-следования написано «Истина», а потому и всё выражение тоже истинно, независимо от значения и содержания «X». Поэтому подставим на место «X» всё то же «A».
То есть
Здесь, кстати, проявляется разница между «следованием» как логической операцией и «выводимостью» как свойством. Мы не выводили «у Пети нет синих кубиков» из сделанного предположения «Петя держит не синий кубик», однако эти два суждения всё равно могут быть объединены операцией следования ввиду того, что «у Пети нет синих кубиков» - аксиома, и потому это суждение считается всегда истинным в рамках выбранной нами системы аксиом.
Вообще говоря, в данном случае можно было бы даже не строить второе выражение со следованием в такой форме, а просто сказать, что из данной системы аксиом и добавленного к ней предположения A, одновременно выводятся B и !B (в данном случае, действительно уже выводятся).
Причём это было бы даже точнее и с большей вероятностью уберегло бы нас от распространённой ошибки, о которой пойдёт речь дальше.
Но, как бы то ни было, синие кубики не могут одновременно быть и не быть у Пети. А раз так, то наше предположение A - «Петя держит не синий кубик» - не может быть истинным: ведь если оно было бы истинным, то истинными были бы и его следствия. Оба сразу. Которые взаимно исключающие. Петя в этом случае чудесным образом должен был бы обладать и не обладать синими кубиками одновременно.
А может ли оно быть ложным? О да. Поскольку ложность того, что стоит слева от «стрелочки-следования», позволяет быть тому, что стоит справа, и истинным, и ложным, то вполне возможно, что, например, «у Пети нет не синих кубиков» истинно, а «у Пети есть не синие кубики» - ложно, а потому противоречия уже не возникает.
В результате, всё сошлось: если мы получили противоречивые следствия, то наше предположение A не может быть истинным, но может быть ложным.
Вполне понятно, что тут предпочесть: возможный вариант точно лучше невозможного. Надо выбирать его. Наше предположение A - ложно, а значит !A - истинно. То есть предположение «Петя держит не синий кубик» - ложное, таким образом мы доказали, что «Петя держит синий кубик».
И я вам гарантирую, в 99,99% мест, где используется «доказательство от противного», на этом рассуждения и закончатся. Мы пришли к противоречию, чем доказали ложность нашего предположения и, таким образом, истинность его отрицания. Точка. Доказательство закончено.
Однако, фактически, все такие доказательства оборваны на середине, и потому все они не являются доказательствами чего бы то ни было. Сам доказанный тезис при этом вполне может быть верным (возможно, именно поэтому и закрепилась привычка обрывать доказательство от противного на середине), но при этом полагаемое «доказательством» на самом деле его не доказывает.
Дело тут вот в чём.
Предположенное нами суждение A никогда не используется в отрыве от всего остального, каким бы оно ни было. Кроме него есть ещё какие-то суждения, ещё какие-то операции и так далее, составляющие некоторую систему аксиом и в целом «правил игры». То есть, фактически, мы всегда имеем дело только с «уточнённым вариантом» доказательства от противного
даже если в явном виде и не уточняем, что слева от стрелок находится не только наше предположение A, но и ещё какие-то, которые мы сочли «системой аксиом».
Таким образом, нет никакой гарантии, что к противоречию нас привело именно предположение об истинности A - вполне возможно, что просто именно в случае с A нам открылось скрытое в других суждениях противоречие, которое в других случаях себя не проявляло.
Если мы забудем об этом и будем думать, что достаточно и «короткого» варианта, то может произойти вот что.
Давайте вместо A предположим !A. Сделаем какие-то операции и получим
Потом сделаем какие-то другие и получим
Как и раньше, это должно было бы означать, что предположение !A ложно, и, таким образом, A - истинно.
Наша же уверенность в том, что ложно именно A, базируется лишь на том, что мы его предположили первым и именно для него обнаружили противоречивые следствия. Для !A мы просто не стали проверять отсутствие аналогичного, а потому не можем быть уверены, что для него не получится точно то же самое.
Да, быть может, правда не получится, но ведь мы же не проверяли. Вдруг получилось бы?
Само собой, доказательством истинности A никак не может быть то, что мы его предположили первым - истинность не может зависеть от порядка проверки. А потому, не проверив, что аналогичного не получается с !A, мы ничего не доказали.
Точнее, мы доказали, что в комплекте всех использованных нами предпосылок, включающих в себя предположение A, есть либо ложное суждение, либо минимум два противоречивых. Быть может, нам повезло, и действительно противоречий нет, а единственное ложное суждение - A. Но могло ведь и не повезти, поэтому у нас нет никаких оснований считать, что доказана именно ложность A: его ложность - это лишь возможный вариант, а не единственный.
Может показаться, будто бы существует какой-то логический закон или некоторый их набор, который гарантирует нам, что обнаруженное в рамках доказательства от противного противоречие вытекает строго из предположения об истинности A и никак не может точно так же вытекать из предположения об истинности !A.
Однако таких законов нет. Такой вариант вполне возможен, что я проиллюстрирую примером.
В качестве предпосылок возьмём…
- Любую «традиционную» алгебраическую аксиоматику (грубо говоря, стандартные арифметические и алгебраические операции).
- Добавленную к ним аксиому
Теперь докажем методом «от противного», что в этой системе аксиом
Для этого предположим, что
и начнём преобразования:
Возможно, я расписал это чересчур подробно, однако это было нужно лишь для того, чтобы показать: в данных преобразованиях мы пользовались только простейшими аксиомами арифметики и добавленной к ним «аксиомой номер 2».
Тем не менее, в результате этих преобразований мы получили, что единица в этом случае должна быть равна нулю.
Однако то, что
вписано в саму систему аксиом арифметики, которой мы пользуемся, а потому, будучи по этой причине всегда истинным, следует из абсолютно любого предположения.
То есть, с одной стороны,
но одновременно с тем
Мы получили противоречие в следовании и тем самым доказали, что наше предположение
ложно, и, значит, истинно то, что
Всё как бы отлично, можно успокоиться: это очевидное соотношение действительно оказалось доказуемым в выбранной нами «расширенной системе аксиом арифметики».
Однако если бы мы здесь поставили традиционную в таких случаях точку, то не открыли бы удивительного.
Давайте предположим, что
а потом попробуем преобразовать и этот вариант тоже.
Впрочем, можно было бы остановиться на предыдущем шаге - ведь он уже противоречит «аксиоме номер 2», в которой всегда истинным объявляется, что
Однако в любом случае оказывается, что
как всегда истинная аксиома арифметики, и вместе с тем,
как выведенное нами при помощи набора аксиом из предположения.
То есть
не может быть истинным, и, таким образом, истинно, что
«Расширенная арифметика» оказалась столь мощной, что с её помощью «от противного» можно доказать обе версии про равенство или неравенство единицы с двойкой. При этом любую из них можно выбрать в качестве «первого кандидата» и, вовремя оборвав доказательство, сделать любой из прямо противоположных выводов.
Разумеется, весь фокус тут состоит в том, что «аксиома номер 2» противоречит собранию аксиом из пункта 1, а потому оказывается возможным «доказать» любое предположение. Однако «доказательства» специально построены так, будто бы «всё честно»: в них действительно используется сделанное нами предположение, из которого потом выводятся противоречивые следствия, а потому возникает иллюзия, будто бы эти следствия порождены именно сделанным нами предположением, а не чем-то ещё - например, противоречием, сокрытом в системе выбранных нами аксиом.
Но это сейчас, у меня тут «специально построено так», однако оно вполне может построиться так и неосознанно. Вселив в автора доказательства и в его читателей уверенность в том, что «мы всё строго доказали».
Вдобавок, наличие каких-то частных случаев, якобы подтверждающих корректность «аксиомы номер 2», могло бы до этого момента многократно вводить нас в заблуждение.
Мы бы писали что-то вроде
или
и всё бы вроде как сходилось. В ряде примеров такая операция оказывается непротиворечащей аксиомам арифметики, причём настолько часто, что было предпринято уже немалое количество попыток ввести её в такой форме. То есть примеров, когда оно «срабатывает», весьма много, а вот не сработать оно может в совершенно неожиданном для кого-то месте.
То есть, будучи уверенными, что мы проверяли именно ошибочность нашего предположения, а не противоречивость системы аксиом, мы могли бы весьма долго плодить «доказательства», которые на самом деле ничего не доказывают.
Это усугубляется ещё и тем, что для утверждения о противоречивости надо предъявить любое противоречие, что в ряде случаев довольно просто. Но вот для того, чтобы утверждать, что противоречий никогда не возникает, чего-то там единожды предъявить недостаточно. И даже много раз предъявить - тоже.
Для этого нужны какие-то очень нетривиальные рассуждения, причём универсальный способ доказательства непротиворечивости системы аксиом неизвестен и есть даже предположения о том, что такой универсальный способ вообще невозможен, а осуществимы только частные случаи: перебор всех возможных следствий некоторой системы аксиом и проверка, что среди них нет такой пары, которая утверждает истинность некоторого суждения и истинность его отрицания.
Если система аксиом допускает лишь конечное количество следствий, то такое гипотетически возможно, хотя и может потребовать времени больше времени жизни вселенной.
С потенциально же бесконечным количеством следствий, перебор невозможен вообще, а потому мы в ряде случаев можем лишь надеяться, что противоречий в системе аксиом нет, но не знать об этом наверняка.
Из этого вытекает, что «доказательство от противного» является строгим лишь в ограниченном количестве случаев - для тех систем аксиом, для которых известен некоторый способ доказательства их непротиворечивости. Либо же для столь «компактных», что все их следствия уже были проверены на непротиворечивость полным перебором.
Для всех же остальных систем такое доказательство не строгое. Причём, если система существует уже давно и активно используется, мы имеем право гораздо более сильно надеяться на то, что она действительно непротиворечива, а потому считать доказательство от противного в этой системе достаточно «сильным».
Если же система, напротив, введена недавно и используется редко, либо же редко используются некоторые её фрагменты, то доказательство от противного для этой системы или этих её фрагментов будет весьма слабым: ведь каждый раз, когда получается в противоречие в следствиях некоторого предположение, весьма вероятно, что таким образом обнаружена противоречивость системы, а вовсе не доказано отрицание этого предположения.
Да, эта сложность, конечно, тоже побуждает оборвать доказательство от противного на середине - ведь в общем случае вообще неясно, как реализовать вторую его часть. И потому хочется просто взять и проигнорировать её, понадеявшись, что противоречий в системе нет.
Однако для каждой плохо изученной и/или почти не имеющей проверяемых практических следствий аксиом системы такой подход всегда оставляет возможность случайно «доказать» что-то типа «1 ≠ 2», выбрав именно эту версию в качестве первого кандидата на доказательство от противного, а «1 = 2» уже не проверить, поскольку «и так ведь уже отлично получилось».
doc-файл
публикация на сайте «XX2 Век»