logic-paradoxes.tex

\section{Парадоксы}

Рассмотрим теперь несколько известных парадоксов классической логики.

\subsection{Парадокс импликации}

Обычно этот парадокс излагается так. Таблица истинности для импликации утверждает, что из ложного высказывания следует любое другое произвольное высказывание: $0 \rightarrow a$ всегда истинно, каким бы ни было $a$. В соответствии с этим определением по идее оказываются справедливы следующие высказывания:

\begin{itemize}
\item Из того, что Луна квадратная, следует, что деревья умеют летать.
\item Из того, что Жанна д’Арк~--- первый космонавт, следует, что Путин~--- краб.
\item Из того, что небо твёрдое, следует, что апельсины оранжевые.
\end{itemize}

Это всё полнейший бред, но он тем не менее идеально соотносится с таблицей истинности для импликации.

Можно привести и другую интерпретацию импликации: легко убедиться, что тавтологией также является высказывание $a \rightarrow (b \rightarrow a)$. Здесь по сути утверждается, что любое истинное высказывание следует из любого другого произвольного высказывания (неважно, верного или нет). Так, например, верно следующее:

\begin{itemize}
\item Вращение Земли вокруг Солнца следует из непогрешимости патриарха.
\item Смертность всех людей следует из того, что в 98-м году был дефолт.
\end{itemize}

Одним словом, бред. А если ввести в поиск по интернету фразу «парадоксы импликации», то можно и не такое найти.

Собственно, никакого особого парадокса тут, конечно, нет. Все высказывания, которые мы привели выше, взяты с потолка. Мы не определили никак интерпретацию нашей логики, с которой мы работаем, а первичный смысл импликации всё же семантическое следование. Если мы рассматриваем импликацию просто по таблице истинности, вырвав из контекста интерпретаций, то она уже представляет собой не более чем арифметическую операцию с ноликом и единичкой, и искать в ней какой-то особый смысл~--- довольно глупое занятие.

С другой стороны, представление о теориях и моделях на самом деле появилось позже, чем понятие импликации. Изначально была придумана импликация с её таблицей истинности, и только потом люди стали рассуждать о парадоксах, следующих из неё, а представление о моделях появилось ещё позже.

Эта историческая последовательность и привела к  <<парадоксу импликации>>. Как мы показали в \S~1.2, таблица истинности для импликации продиктована необходимостью соблюсти свойство транзитивности. Однако до того момента, как математики развили концепцию теорий и моделей, попытки увязать логически формулы с высказываниями на человеческом языке приводили к таким парадоксам.

С современной точки зрения никакого парадокса уже не осталось, поскольку прежде чем наделять смыслом логическую формулу, мы должны представить её интерпретацию в смысле прошлого параграфа. Если заходить с этой  стороны, то никакого парадокса конечно же уже не произойдёт.

Чтобы увидеть, что парадокса не произойдёт, будет уместно вспомнить про понятие выводимости: из противоречивой теории (когда одновременно предполагались верными и $\psi$ и $\neg\psi$, откуда в общем-то по введению конъюнкции следует высказывание $\psi\wedge\neg\psi=0$) мы показали, что возможно вывести любое произвольное высказывание. Другое дело, что как стало понятно в прошлом параграфе, для такой теории не будет никакой модели — подобная теория является противоречивой.

Таким образом импликация из ложной посылки в любом случае никогда не может быть применена и парадокс не возникает. Её таблица истинности — не более чем необходимость, следующая из того, что логические связки должны быть определены для всех значений истинности.

\subsection{Парадокс брадобрея}

В некотором царстве, в некотором государстве, живёт брадобрей~--- такой мужик, который бреет бороды только тем, кто не бреется сам, а тем кто сам бреется, он бороды не бреет. Вопрос: а кто бреет самого брадобрея?

Допустим, брадобрей сам бреется. Но, будучи брадобреем, он не должен брить тех, кто бреется сам, то есть брить себя не должен. Если же допустить, наоборот, что он не бреется сам, то он должен себя брить, как человека, который сам не бреется. Парадокс.

Ситуация становится понятнее, если переформулировать условия задачи на языке логики. Пусть предикат $B(x)$ выражает тот факт, что $x$ является брадобреем, а предикат $S(y, z)$ говорит о том, что $y$ бреет $z$. Тогда условие задачи можно сформулировать следующим образом:

$$\exists x, B(x), \forall y (\neg S(y, y) \leftrightarrow S(x, y))$$

Однако поскольку $y$ снабжён квантором $\forall$, мы в качестве $y$ можем взять любое значение, в том числе и $x$. Тогда в скобках получится такое выражение:

$$\neg S(x, x) \leftrightarrow S(x, x)$$

Это условие всегда ложно, и значит изначальное высказывание тоже всегда ложно. Таким образом само условие задачи оказывается противоречивым и нереализуемым (не имеющим модели) — такого города и такого брадобрея просто не может существовать в принципе, даже в теории.

А значит, что и любые последующие вопросы, какими бы они ни были, в том числе вопрос «Кто бреет брадобрея?», физически не имеют смысла. Мы это строго доказали.

\subsection{Парадокс пьяницы}

{\bfseries Теорема.} В любом баре найдётся такой посетитель, что если он пьёт, то пьют и все остальные посетители.

Теорема кажется абсурдной — пить теоретически может любое количество людей, без каких либо условий. Однако, эту теорему легко доказать.

{\bfseries Доказательство.} Введём предикат $D(x)$, означающий, что $x$ пьёт. Тогда условия теоремы можно сформулировать следующим образом: $\exists x, (D(x) \rightarrow \forall y, D(y))$. Данное выражение оказывается всегда истинным, что легко увидеть, если рассмотреть две ситуации: когда в баре пьют все, и когда кто-то все же не пьёт. Если пьют все, то $\forall y, D(y)$ и доказывать нечего. Если же в баре кто-то не пьёт, то найдётся такой $x$, что выражение $D(x)$ окажется ложным, а из ложного утверждения следует любое утверждение. Следовательно, приведённая нами формула оказывается всегда истинна. \qed

В чем подвох? На первый взгляд может показаться, что подвох в импликации и это только разновидность первого нашего парадокса. Однако это не так — импликация здесь используется вполне законно, придраться к импликации тут негде — рассуждения первого парадокса здесь не пройдут.

Реальная причина парадокса в том, что формулировка теоремы как бы подразумевает, что есть некий один человек, который является причиной всеобщего пьянства, причём это происходит каждый раз. В формулировке же, используемой при доказательстве теоремы, говорится лишь об одном моменте времени и не говорится ни о какой систематичности. Если бы люди собрались выпить в баре в следующий раз, то теорема осталась бы верной, но выбор человека, который «если пьёт, то пьют все», был бы уже другим. Наша теория, доказанная выше, ровным счётом ничего не утверждает про завтрашний или вчерашний день.

Приведённый парадокс является примером частой ошибки, которую допускают люди при трактовке импликации: импликация ни в коем случае не символизирует собой  какое-то физическое следствие, она лишь является логической связкой, которая показывает невозможность истинности одного высказывания без другого в какой-то статичной модели.

\subsection{Парадокс воронов}

Рассмотрим следующее высказывание: «Все вор\'{о}ны чёрные».\footnote{Я не знаю, так это или не так с биологической точки зрения, но для целей математики предположим, что это так.} Легко увидеть, что данное высказывание эквивалентно высказыванию «Если объект не чёрный, то он не может быть вороной». На языке логики это символизируется тавтологией $$a \rightarrow b = \neg b \rightarrow \neg a$$ и в общем-то довольно очевидно.

Представим, однако, себя натуралистами-исследователями, которые путешествуют по свету и пытаются ответить на вопрос: «Являются ли все вороны чёрными, или все же есть цветные?» Увидеть сразу всех ворон у нас не получится, мы можем видеть только какую-то незначительную долю всех живущих ворон. Однако логично, что чем больше чёрных ворон в разных уголках планеты мы видим, тем больше мы убеждаемся в том, что и все вороны вообще — чёрные.

Возьмём теперь наше эквивалентное черноте всех ворон высказывание «Если объект не чёрный, то он не может быть вороной». Оно равнозначно прошлому высказыванию, и из него как бы следует, что чем больше мы видим не чёрных, а цветных объектов, которые не являются воронами, тем больше должна расти в нас уверенность в том, что все вороны чёрные. То есть даже если мы увидели миллионы апельсинов и яблок, то мы должны делать какие-то выводы о цвете ворон.

Выглядит парадоксально, и, действительно, наши рассуждения не совсем верны. Когда мы говорим что-то на языке формальной логики, мы работаем с абсолютной истиной и абсолютной ложью. Когда же мы рассуждаем по индукции и видим лишь часть мира, мы уже говорим о вероятностях, и здесь законы формальной логики не особо работают.

В данной ситуации следовало бы применять теорию вероятностей. Интересно, что даже используя теорию вероятностей, мы можем прийти к тому же самому результату: наблюдение большого числа цветных объектов должно убеждать нас в черноте всех ворон. Другое дело, что степень нашей убеждённости в этом случае будет расти не с той же скоростью. При наблюдении чёрной вороны наша убеждённость будет расти довольно значительно, а вот при наблюдении зелёного яблока убеждённость в черноте ворон должна расти настолько несущественно, что ей можно вообще пренебречь.

Таким образом мы можем сделать наш первый вывод о том, что при рассмотрении каких-либо утверждений мы должны адекватно подбирать математический аппарат для решения задачи. Иначе легко прийти к ложным выводам.

Второй нюанс, тесно связанный с первым, заключается в том, что мы также всегда должны более подробно формулировать постановку задачи и описывать, как именно мы проводим эксперимент. Наши высказывания и сформулированная тавтология слишком поверхностны для того, чтобы применять их в контексте какого-либо эксперимента.

Предположим себе такой сюжет для научно-фантастической книжки: существует два мира, населённых птичками. В одном мире вороны встречаются крайне редко. Например, их всего нес\-коль\-ко штук на всю планету, и все они чёрные. А во втором мире ворон летает миллионы, но среди них есть всё же одна белая.

Предположим теперь, что наш юный натуралист знает о существовании этих двух миров и знает ситуацию с воронами, однако он не знает, в каком именно из этих миров он находится. И вдруг он встречает чёрную ворону. В этом случае подобная встреча с чёрной вороной должна, напротив, убедить его в том, что в этом мире существуют также и белые вороны — если бы он был в том мире, где вороны только чёрные, то ему было бы вообще какую-либо ворону найти крайне сложно.

Таким образом, при некотором уточнении постановки задачи мы вообще смогли вывернуть наизнанку все наши выводы.

\subsection{Парадокс лжеца}

Парадокс заключается в формулировке следующего высказывания: «Данное высказывание ложно». Является ли оно ложным или истинным? Если оно истинно, то оно же само утверждает, что оно ложно, и должно, следовательно, быть ложным. И нао\-бо\-рот.

На первый взгляд сильно похоже на парадокс брадобрея, но только на первый.  Как сформулировать это высказывание на языке математической логики — совершенно непонятно. Можно было бы сослаться на определение высказывания из первого параграфа, где мы чётко указали на то, что мы рассматриваем лишь те высказывания, про которые можно чётко сказать, истинны они нет, и таким образом просто отмазаться от парадокса лжеца.

Проблема тут в том, что если формулировка, как я её привёл выше, кажется слишком надуманной и от неё вроде как можно было бы отмахнуться, то многие распространённые переформулировки задачи нам этого уже не позволят сделать.

Например, популярен парадокс Пиноккио (такой мужик из сказки, у которого вырастал нос, когда он врёт). Заключается он в том, что Пиноккио как-то заявил: «Ой, у меня нос растёт». Тут применимы всё те же рассуждения.

Сам же парадокс происходит ещё из древнего мира. Самая распространённая формулировка называется парадоксом Платона и Сократа:

\begin{quote}
---~Следующее высказывание Сократа будет ложным,~--- сказал Платон.\\
---~То, что только что сказал Платон, истинно,~--- ответил Сократ.
\end{quote}

Придумали его правда не они, а древнегреческий жрец и провидец, «не предсказывающий будущего, но разъясняющий тёмное прошлое», Эпименид, известный двумя фактами биографии: тем, что заснул в зачарованной пещере, и проснулся лишь спустя 57 лет, а также тем, что утверждал, будто все критяне постоянно врут. Сам он при этом тоже был критянином. Учёные, впрочем, сомневаются не только в том, что он проспал 57 лет, но и в том, что он вообще существовал. Если, однако, он существовал, то было это где-то порядка 600 лет до нашей эры.

Этот парадокс был потом многократно обыгран в разных вариациях, в том числе в художественной литературе. На того же Эпименида ссылается апостол Павел в Новом завете, называя его просто «одним из них же самих». Но встречается он не только в древних текстах. Вот, например, фраза из «Автостопом по галактике» Дугласа Адамса: «Старик постоянно говорил, что всё вокруг — неправда. Правда, потом оказалось, что он лгал» (этот парадокс однако при дополнительных допущениях можно легко разрешить, чем я предлагаю заняться читателю).

Над этим парадоксом долгое время думали философы всех мастей. Легенда утверждает, что поэт, грамматик и древний грек Филит Косский даже помер от бессонницы, пытаясь разрешить этот парадокс. В результате возникло много трактовок этого парадокса, а также много новых формулировок.

Распространённый подход — ввести в рассмотрение высказывания о высказываниях. То есть рассматривать отдельно высказывание $s_0$, а также высказывание $s_1$, утверждающее, что высказывание $s_0$ истинно либо ложно, и они совершенно не обязаны быть как-то согласованны. Например, $s_1$ может быть частным суждением некоторого человека. В этом случае парадокс уже как бы пропадает.

Есть направление, называемое нечёткой логикой. В ней высказывания не являются истинными либо ложными достоверно, а лишь только с некоторой степенью вероятности. Высказывания в формулировке парадокса оказываются верными либо ложными с одинаковой вероятностью. Некое подобное решение предлагает направление интуиционистской логики, в котором вероятностей как таковых нет, но есть высказывания, истинность которых не установлена и не может быть установлена.

Многие философы и математики стояли на позиции, что парадокс лжеца возникает из-за того, что сама его формулировка опирается на собственную формулировку. И подобная рекурсия недопустима и не имеет смысла вообще. Однако тогда была предложена переформулировка парадокса в виде такого бесконечного «рассказа»:

«Все последующие предложения данного рассказа являются ложными. Все последующие предложения данного рассказа являются ложными. Все последующие предложения данного рассказа являются ложными. Все последующие предложения данного рассказа являются ложными. Все последующие предложения данного рассказа являются ложными. Все последующие...»

И вот думай теперь какие из этих предложений истинные, а какие ложные. Тут интересно, что ссылки предложений самих на себя (что философы и математики видели причиной парадокса) уже не используются, но парадокс при этом остаётся парадоксом. Здесь, правда, уже используется бесконечность, что также может смутить.

{\bfseries Упражнение.} Объясните, почему бесконечность «рассказа» в данном случае принципиальна.

Мы рассмотрим этот парадокс с точки зрения той логики, которую я излагал. Для того, чтобы сформулировать условия высказывания, сделаем такую придумку: введём помимо самого понятия высказывания, которое может быть истинным или ложным, понятие «название высказывания» (можно интерпретировать это как разграничение между собственно высказыванием и названием переменной для него, которое мы можем подсовывать в предикаты).

Само высказывание «это высказывание ложно» обозначим как $L$, а его «название» как $\bar{L}$. Введём также предикат $Tr$, определённый для «названий» высказываний, который имеет следующий смысл: «Высказывание с данным „названием“ истинно». Данный предикат можно описать следующим образом: $s = Tr(\bar{s})$. Теперь само наше высказывание может быть описано как $L = \neg Tr(\bar{L})$.

В рассуждении ниже мы используем два правила вывода формул, которые мы не использовали ранее, но в справедливости которых довольно легко убедиться:

\begin{enumerate}
\item \term{введение конъюнкции}: $p, q\vdash p\land q$
\item \term{анализ частных}: $(p\to q), (\neg p\to q)\vdash q$
\end{enumerate}

Посмотрим теперь что из этого можно вывести:

\begin{enumerate}
\item  $T\vdash Tr(\bar{L})\vee\neg Tr(\bar{L})$ — закон исключённого третьего;
\item  $T, Tr(\bar{L})\vdash L$ — по определению нашего предиката;
\item  $T, Tr(\bar{L})\vdash \neg Tr(\bar{L})$ — по определению высказывания $L$;
\item  $T, Tr(\bar{L})\vdash Tr(\bar{L})\wedge\neg Tr(\bar{L})$ — введение конъюнкции с уже имеющейся теоремой;
\item  $T\vdash Tr(\bar{L})\rightarrow Tr(\bar{L})\wedge\neg Tr(\bar{L})$ — дедукция;
\item  $T, \neg Tr(\bar{L})\vdash L$ — по определению $L$;
\item  $T, \neg Tr(\bar{L}) \vdash Tr(\bar{L})$ — по определению предиката $Tr$;
\item  $T, \neg Tr(\bar{L})\vdash \neg Tr(\bar{L}) \wedge Tr(\bar{L})$ — введение конъюнкции;
\item  $T\vdash \neg Tr(\bar{L})\rightarrow Tr(\bar{L})\wedge\neg Tr(\bar{L})$ — дедукция;
\item  $T\vdash Tr(\bar{L})\wedge\neg Tr(\bar{L})$ — анализ частных для 5) и 9).
\end{enumerate}

Последняя полученная формула никогда не может быть истинна, следовательно теория противоречива и не может иметь моделей. В нашей логической модели мы пришли к противоречию, и соответственно сама постановка задачи была некорректна.

Здесь у читателя могут возникнуть сомнения: почему в парадоксе брадобрея мы так запросто приняли противоречивость постановки задачи, а в случае с лжецом, философы и математики тысячелетиями придумывали различные логические системы и трактовки? Не считая того, что сам парадокс брадобрея исторически появился намного позже, дело тут также и в том, что парадокс брадобрея довольно элементарно формулируется в терминах классической логики, и из формулировки легко следует, что постановка задачи некорректна. В случае с парадоксом лжеца задача так просто сформулирована быть уже не может, и более того: сформулирована она может быть различными способами.

В этой задаче также интересно заметить, что причина противоречивости формулировки в классической логике кроется вовсе не в ссылке высказывания самого на себя, как можно было бы предположить, а именно в содержании утверждения касательно истинности высказывания. Здесь можно рассмотреть такую нелепую вроде бы теорему:

\begin{thm}Данная теорема не может быть доказана.\end{thm}

Оказывается, что как только мы заменили слово «истинное» на «доказуемое» (более точно, конечно — «выводимое»), то парадокс лжеца перестаёт вести к противоречиям в классической логике, хотя эта теорема действительно невыводима. Но об этом речь у нас пойдёт уже значительно позже и несколько в другом виде, когда у нас появятся инструменты, чтобы подробнее формализовать приведённое утверждение. Более того, мы увидим, что теоремы, подобные этой, могут иметь вполне себе глубокий теоретический и иногда даже прикладной смысл.