Что такое математическая логика

Краткое содержание

Этот урок очерчивает предмет математической логики: не истинность отдельных утверждений, которая относится к ведению каждой науки, а форму рассуждений и их правильность, то есть такое отношение между посылками и заключением, которое гарантирует, что истинность первых переходит на второе. Урок определяет высказывание, рассуждение, посылку, заключение, форму и контрпример; отличает правильность от истинности на примерах правильных рассуждений с ложным заключением и неправильных рассуждений с истинным заключением; показывает, почему естественного языка, многозначного и способного говорить о самом себе, недостаточно для строгого изучения правильности, и устанавливает различие между языком-объектом и метаязыком, которое направляет весь курс. Затем он излагает, с явно сформулированными допущениями и с доказательствами, парадоксы лжеца, Берри и брадобрея, а также парадокс Рассела, который брадобрей предвосхищает, и объясняет, как формальный язык их избегает или превращает в теоремы. Завершают урок четыре основания математической логики и карта курса.

Цели обучения

Отличать правильность рассуждения от истинности его посылок и заключения и опровергать неправильную форму, строя контрпример.
Распознавать многозначность естественного языка и уточнять каждое прочтение многозначного утверждения.
Различать язык-объект и метаязык, а также употребление выражения и его упоминание.
Анализировать парадокс: выделять его допущения, выводить противоречие и решать, от какого допущения следует отказаться.

Что изучает логика

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

Чтобы точно сказать, что она изучает, сначала нужно закрепить словарь. Высказывание есть повествовательное предложение, о котором имеет смысл говорить, что оно истинно или что оно ложно: « $7$ есть простое число» есть истинное высказывание; «всякое чётное число больше $5$ », ложное высказывание. Высказываниями не являются, напротив, вопросы («который час?»), приказы («закрой дверь») и выражения со свободными переменными, такие как « $x$ чётно», значение которых зависит от того, что обозначает $x$ .

Рассуждение есть список высказываний, посылок, вместе с ещё одним высказыванием, заключением, которое предъявляется как их следствие. Посылками могут быть любые высказывания: истинные, ложные, известные или просто предположения; отличает их лишь место, которое они занимают в рассуждении. Мы будем записывать рассуждения так: посылки на последовательных строках, а перед заключением слово «следовательно»:

ПримерРассуждение

Если число кратно $4$ , то оно чётно. Число $28$ кратно $4$ . Следовательно, $28$ чётно.

Его посылки: «если число кратно $4$ , то оно чётно» и « $28$ кратно $4$ »; его заключение: « $28$ чётно».

Логика не есть теория истины

Если это так, то задача логики не в том, чтобы выяснять, истинны ли посылки рассуждения. Кратно ли $28$ числу $4$ , решает арифметика; есть ли у человека жар, решает термометр; произошла ли битва в таком-то году, решает история. Не ей принадлежит и определение того, что такое истина: этот вопрос относится к философии. Логика принимает, что у высказываний есть истинностное значение, каким бы оно ни было, и изучает, как эти значения связаны между собой: в частности, когда истинность одних высказываний вынуждает истинность другого. Иначе говоря, логика есть теория не истины, а передачи истины.

Однако то, что передаёт истину, зависит не от темы рассуждения, а от его строения. Сравним предыдущее рассуждение с таким: «если животное есть млекопитающее, то оно дышит воздухом; кит есть млекопитающее; следовательно, кит дышит воздухом». У обоих одна и та же форма: «если нечто есть $A$ , то оно есть $B$ ; $c$ есть $A$ ; следовательно, $c$ есть $B$ ». Форма рассуждения есть то, что остаётся, когда его нелогические термины (числа, животных, свойства) заменяют буквами, сохраняя логические слова: «не», «и», «или», «если… то», «всякий», «некоторый». Каждое рассуждение, получающееся из формы, когда её буквам придают содержание, есть частный случай этой формы.

Форма правильна, когда ни один из её частных случаев не имеет всех посылок истинными и заключения ложным; рассуждение правильно, когда правильна его форма. Частный случай с истинными посылками и ложным заключением называется контрпримером к форме: откуда форма неправильна в точности тогда, когда у неё есть контрпример.

В доказательствах этого урока мы будем пользоваться стенографией русского языка: $V(A)$ сокращает « $A$ истинно», а $F(A)$ , « $A$ ложно»; $\neg$ сокращает «не», $\wedge$ сокращает «и», $\vee$ сокращает «или», $\Rightarrow$ сокращает «если… то», а $\Leftrightarrow$ сокращает «тогда и только тогда, когда»; $\forall$ читается «для всякого», а $\exists$ , «существует». Эти знаки здесь лишь сокращения слов метаязыка, и двойные стрелки во всём курсе оставлены для этого употребления. В следующем уроке появятся знаки с одной чертой, $\rightarrow$ и $\leftrightarrow$ , вместе с $\neg$ , $\wedge$ и $\vee$ , как сокращения формального языка, со смыслом, который курс точно установит; различие в начертании стрелок будет напоминать, на каком уровне идёт речь.

УтверждениеЧто гарантирует правильность

Если рассуждение правильно и все его посылки истинны, то его заключение истинно. Следовательно, если правильное рассуждение имеет ложное заключение, то какая-то из его посылок ложна.

Доказательство

$\dato{p}{V(A_1) \wedge \cdots \wedge V(A_n)}$
Пусть дано правильное рассуждение с посылками $A_1, \ldots, A_n$ и заключением $C$ , и предположим, что все посылки истинны.
$\resaltar{A_1, \ldots, A_n, C}$
Всякое рассуждение есть частный случай своей собственной формы: достаточно придать буквам формы то содержание, которое они имели в рассуждении.
$\dato{v}{\neg\left( V(A_1) \wedge \cdots \wedge V(A_n) \wedge \resaltar{\neg V(C)} \right)}$
По определению правильности ни один частный случай этой формы не имеет посылок истинными и заключения ложным; в частности, этого нет и у самого рассуждения.
$\resaltar{V(C)}$
Поскольку посылки истинны, единственное, что может не выполняться в отрицаемой конъюнкции, это ложность заключения: заключение истинно.
$\neg V(C) \Rightarrow \neg\left( V(A_1) \wedge \cdots \wedge V(A_n) \right)$
Если же, напротив, заключение ложно, то не все посылки могут быть истинны, потому что тогда истинным было бы и заключение.

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

ПримерПравильное, с ложным заключением

Всякое простое число нечётно. Число $2$ простое. Следовательно, $2$ нечётно.

Форма та же, что у первого рассуждения урока, так что рассуждение правильно; тем не менее его заключение ложно. Предыдущее утверждение указывает, где изъян: какая-то посылка ложна, и действительно ложна первая, потому что $2$ простое и чётное. Правильное рассуждение не производит истин; оно лишь сохраняет те, которые получает.

ПримерНеправильное, с истинным заключением

Если число кратно $4$ , то оно чётно. Число $8$ чётно. Следовательно, $8$ кратно $4$ .

Посылки и заключение истинны, и всё же рассуждение неправильно. Его форма, «если нечто есть $A$ , то оно есть $B$ ; $c$ есть $B$ ; следовательно, $c$ есть $A$ », имеет контрпример: с числом $6$ вместо $8$ посылки остаются истинными («если число кратно $4$ , то оно чётно»; « $6$ чётно»), а заключение, « $6$ кратно $4$ », ложно. Истинность исходного заключения происходит не из посылок, а из арифметики: $8 = 4 \cdot 2$ . Эта неправильная форма, частая в повседневных рассуждениях, называется утверждением консеквента.

Отсюда следует практическое правило, которое будет отрабатывать урок: чтобы показать, что рассуждение неправильно, недостаточно указать, что ложна какая-то посылка или заключение, а чтобы показать, что оно правильно, недостаточно, чтобы всё в нём было истинно; первое требует предъявить контрпример к его форме, а второе, рассуждение, годное для всех частных случаев.

Естественный язык и формальный язык

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

Лексическая многозначность: слово имеет несколько значений. «Она долго рассматривала замок» может относиться к крепости или к запорному устройству.
Синтаксическая многозначность: предложение допускает несколько строений. «Дважды три плюс четыре» может означать $2 \cdot 3 + 4 = 10$ или $2 \cdot (3 + 4) = 14$ .
Многозначность области действия: неясно, на какую часть предложения действует логическое слово. «Все студенты не сдали экзамен» может означать, что никто не сдал, или что сдали не все.
Неточные связки: «или» иногда допускает, что выполняются обе альтернативы («требуется диплом или опыт работы»), а иногда это исключает («чай или кофе»); «если… то» иногда выражает причину, иногда правило, иногда простое следование во времени.

К многозначности добавляется более глубокая черта: естественный язык может говорить о самом себе. В нём есть слова «предложение», «истинный» и «определять», и с их помощью он может строить предложения, которые говорят о самих себе, например «в этом предложении пять слов». Такая самореференция в общем безобидна; но, как мы увидим, в сочетании с понятием истины она порождает предложения, которые не могут быть ни истинными, ни ложными.

Формальный язык строится так, чтобы устранить оба источника трудностей. Фиксируется алфавит, набор символов, и правила образования, которые, не оставляя места для толкования, говорят, какие последовательности символов являются правильно построенными выражениями; значение каждого выражения затем фиксируется столь же точными определениями. Так, вопрос о том, принадлежит ли последовательность символов языку, решается механически, проверкой правил, и каждое выражение читается единственным образом. Язык этого курса, который строит урок о языке логики высказываний, имеет алфавит всего из двух символов, кружка $\sigO$ и диска $\sigI$ , и единственное правило образования.

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

Язык-объект и метаязык

Чтобы изучать язык, нужно говорить о нём, а чтобы говорить о нём, нужен другой язык. Язык-объект есть изучаемый язык; метаязык есть язык, на котором его изучают. В латинской грамматике, написанной по-русски, латынь есть язык-объект, а русский язык, метаязык. В этом курсе языком-объектом будет формальный язык кружков и дисков, а метаязыком, русский язык, обогащённый математическими знаками и греческими буквами $\varphi$ , $\psi$ , которые будут обозначать произвольные формулы языка-объекта, не принадлежа ему.

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

Элементарная форма этого различия отделяет употребление выражения от его упоминания. В предложении «Рим является городом» слово употреблено, чтобы говорить о городе; в предложении «„Рим“ состоит из трёх букв» слово упомянуто, и на это указывают кавычки: предложение говорит о слове, а не о городе. Смешение того и другого порождает нелепые утверждения, такие как «Рим состоит из трёх букв», или ошибочные рассуждения, такие как «Рим является городом; „Рим“ есть слово из трёх букв; следовательно, город есть слово из трёх букв».

ПримерТри уровня

Возьмём в качестве языка-объекта латынь. Предложение «Roma aeterna est» принадлежит языку-объекту. Предложение «„Roma aeterna est“ состоит из трёх слов» принадлежит метаязыку, русскому, и истинно. Предложение «предыдущее предложение написано по-русски» говорит о предложении метаязыка: оно принадлежит третьему уровню, метаязыку метаязыка, хотя и написано на том же языке. Ничто не мешает одному и тому же языку служить на нескольких уровнях; важно не терять из виду, о чём идёт речь.

Парадоксы языка

Противоречие есть утверждение вместе с его отрицанием, например $V(A) \wedge \neg V(A)$ . Парадокс есть рассуждение, которое, исходя из допущений, кажущихся приемлемыми, и продвигаясь шагами, кажущимися правильными, приходит к противоречию. По утверждению «Что гарантирует правильность», если шаги действительно правильны, то какое-то допущение ложно: разрешить парадокс значит найти, какое именно. Не следует смешивать парадокс с многозначностью, которая есть лишь множественность прочтений, или с тем, что просто удивительно.

Лжец

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

Двузначность (B): всякое высказывание истинно или ложно, и не то и другое вместе; быть ложным равносильно тому, чтобы не быть истинным.
Схема истинности (T): предложение истинно тогда и только тогда, когда то, что оно говорит, имеет место. Например, «снег бел» истинно тогда и только тогда, когда снег бел.

ТеоремаПарадокс лжеца

Допущения двузначности и схемы истинности, применённые к предложению $m$ , приводят к противоречию: нет способа приписать $m$ истинностное значение, которое их соблюдало бы. На рисунке предложение $m$ указывает на само себя, а стрелки обходят обе возможности.

Доказательство

$\dato{B}{F(m) \Leftrightarrow \neg V(m)}$
По двузначности $m$ истинно или ложно, и не то и другое вместе: быть ложным значит не быть истинным.
$\dato{T}{V(m) \Leftrightarrow \resaltar{F(m)}}$
То, что говорит $m$ , состоит в том, что $m$ ложно. По схеме истинности $m$ истинно в точности тогда, когда то, что оно говорит, имеет место.
$V(m) \Leftrightarrow \resaltar{\neg V(m)}$
Соединяя обе равносильности, получаем, что истинность $m$ равносильна её собственному отрицанию.
$V(m) \Rightarrow \neg V(m), \quad \resaltar{\neg V(m)}$
Если бы $m$ было истинно, то по равносильности, прочитанной слева направо, оно не было бы истинным: предположение опровергает само себя, и $m$ не истинно.
$\resaltar{V(m) \wedge \neg V(m)}$
Но тогда по равносильности, прочитанной справа налево, $m$ истинно: имеются одновременно утверждение и его отрицание.

Теорема говорит не о том, что логика противоречива, а о том, что оба допущения не могут одновременно соблюдаться для языка, содержащего предложение $m$ . Поэтому есть три выхода: отказаться от двузначности и допустить предложения без истинностного значения; ограничить схему истинности; или не позволить языку образовать предложение $m$ . Третий выход предложил Альфред Тарский в 1933 году: предикат «истинно» некоторого языка принадлежит не этому языку, а его метаязыку. В таком языке $m$ не есть правильно построенное предложение, и парадокс нельзя даже сформулировать.

Парадокс Берри

Этот парадокс, опубликованный Бертраном Расселом в 1906 году, который приписал его Джорджу Берри, библиотекарю из Оксфорда, использует не слово «истинный», а слово «определять». Говорят, что словосочетание русского языка определяет натуральное число, когда описывает его так, что его можно опознать без многозначности: «наименьшее простое число, большее десяти» определяет $11$ . Рассмотрим словосочетание «наименьшее натуральное число, которое не может быть определено посредством менее чем двадцати слов», которое следует читать в точности так, как оно написано, и назовём $b$ число, которое оно претендует определить. Натуральные числа в этом курсе суть $1, 2, 3, \ldots$

ТеоремаПарадокс Берри

Если словарь русского языка конечен и отношение «словосочетание определяет число» вполне определено, то получается противоречие: число $b$ существует и одновременно может и не может быть определено посредством менее чем двадцати слов. На рисунке короткие словосочетания отправляются к числам, которые они определяют и которых немного; первое число, оставшееся свободным, есть $b$ .

Доказательство

$\dato{N}{N \leq k + k^2 + \cdots + k^{19}}$
Пусть $k$ есть число слов словаря. Словосочетаний из одного слова не более $k$ ; из двух, не более $k^2$ ; и так далее до словосочетаний из девятнадцати слов. Словосочетаний менее чем из двадцати слов, следовательно, конечное число $N$ .
$\dato{D}{D = \{ d_1, \ldots, d_r \}, \quad r \leq N}$
Каждое словосочетание определяет не более одного числа. Пусть $D$ есть множество натуральных чисел, которые определяет какое-нибудь словосочетание менее чем из двадцати слов: в нём не более $N$ элементов.
$(\exists n \leq N + 1)\,(n \notin D), \quad \resaltar{b \notin D}$
Среди $N + 1$ чисел $1, 2, \ldots, N + 1$ есть такое, которое не лежит в $D$ . Если перебирать их по порядку, то первое, не лежащее в $D$ , есть наименьшее натуральное число, которое не может быть определено посредством менее чем двадцати слов: все предыдущие лежат в $D$ .
$13 < 20, \quad \resaltar{b \in D}$
Но словосочетание «наименьшее натуральное число, которое не может быть определено посредством менее чем двадцати слов» состоит из тринадцати слов и определяет как раз $b$ .
$\resaltar{b \in D \wedge b \notin D}$
Имеются одновременно утверждение и его отрицание.

Обычное изложение, которое ограничивается замечанием, что в словосочетании меньше двадцати слов, опускает половину рассуждения: то, что число $b$ существует, а это требует конечности словаря и выбора первого недостающего числа. Ложным оказывается второе допущение: «определять» не есть точное отношение русского языка, потому что словосочетание, определяющее $b$ , использует само слово «определять», и его смысл зависит от того, какие словосочетания считаются определениями. В формальном языке $L$ можно уточнить, что значит «определимо в $L$ », но это понятие выражается только в метаязыке; словосочетание, определяющее $b$ , не принадлежит $L$ , и противоречие исчезает: $b$ не определимо в $L$ малым числом символов, хотя и определимо в метаязыке.

Брадобрей и множество Рассела

Парадокс брадобрея обычно рассказывают так: в деревне есть брадобрей, мужчина из этой деревни, который бреет всех мужчин деревни, не бреющихся самостоятельно, и только их. Бреет ли брадобрей самого себя? Слова «и только их» существенны: брадобрей, который брил бы всех, кто не бреется сам, без этого ограничения, мог бы брить и самого себя без всякого противоречия. Парадокс есть частный случай общей леммы диагонального вида, которую стоит доказать один раз.

ЛеммаДиагональная лемма

Пусть $D$ есть совокупность объектов и $R$ есть отношение между ними, такое что для каждой пары $x$ , $y$ объектов из $D$ утверждение $R(x, y)$ истинно или ложно. Тогда не существует объекта $b$ из $D$ такого, что для всякого $x$ из $D$ выполняется $R(b, x)$ тогда и только тогда, когда не выполняется $R(x, x)$ . На рисунке каждая строка есть объект $x$ , а каждый столбец, объект $y$ , и клетка закрашена, когда выполняется $R(x, y)$ ; строка, которую мы ищем для $b$ , должна была бы обращать диагональ и потому отличается от каждой строки в диагональной клетке этой строки.

Доказательство

$\dato{b}{(\forall x \in D)\,\left( R(b, x) \Leftrightarrow \neg R(x, x) \right)}$
Предположим, что такой $b$ в $D$ существует.
$R(b, \resaltar{b}) \Leftrightarrow \neg R(\resaltar{b}, \resaltar{b})$
Условие выполняется для всякого $x$ из $D$ , а $b$ есть один из них: можно взять $x = b$ .
$R(b, b) \Rightarrow \resaltar{\neg R(b, b)}$
Если $R(b, b)$ выполняется, то по равносильности оно не выполняется: противоречие.
$\neg R(b, b) \Rightarrow \resaltar{R(b, b)}$
Если $R(b, b)$ не выполняется, то по равносильности оно выполняется: тоже противоречие.
$\neg (\exists b \in D)\,(\forall x \in D)\,\left( R(b, x) \Leftrightarrow \neg R(x, x) \right)$
Поскольку один из двух случаев должен иметь место, предположение несостоятельно: такого $b$ нет.

СледствиеБрадобрея не существует

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

Доказательство

$(\forall x \in D)\,\left( R(b, x) \Leftrightarrow \neg R(x, x) \right)$
Пусть $D$ есть совокупность мужчин деревни, а $R(x, y)$ есть отношение « $x$ бреет $y$ ». Брадобрей $b$ есть мужчина из деревни, так что он лежит в $D$ ; то, что он брадобрей описанного рода, означает, что он бреет каждого мужчину деревни в точности тогда, когда этот мужчина не бреется самостоятельно.
$\resaltar{\neg (\exists b \in D)}\,(\forall x \in D)\,\left( R(b, x) \Leftrightarrow \neg R(x, x) \right)$
По диагональной лемме ни один мужчина деревни этому условию не удовлетворяет: описанного брадобрея не существует. История есть не парадокс, а доказательство того, что её герой невозможен.

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

Z = \{ x : x \notin x \}

СледствиеПарадокс Рассела

Принцип свёртывания без ограничений противоречив.

Доказательство

$\dato{Z}{(\forall x \in D)\,\left( x \in Z \Leftrightarrow x \notin x \right)}$
Пусть $D$ есть совокупность всех множеств, а $R(x, y)$ есть отношение « $y$ принадлежит $x$ ». Принцип свёртывания, применённый к свойству $x \notin x$ , утверждает, что существует множество $Z$ , элементы которого суть множества, не принадлежащие самим себе.
$(\forall x \in D)\,\left( \resaltar{R(Z, x)} \Leftrightarrow \resaltar{\neg R(x, x)} \right)$
При выбранном отношении условие на $Z$ есть в точности условие диагональной леммы, с $Z$ на месте $b$ : $x \in Z$ есть $R(Z, x)$ , а $x \notin x$ есть $\neg R(x, x)$ .
$\resaltar{Z \in Z \Leftrightarrow Z \notin Z}$
Множество $Z$ есть множество, так что оно лежит в $D$ ; по диагональной лемме такого $Z$ нет, и, взяв $x = Z$ , получаем невозможную равносильность. Но принцип утверждает, что оно существует. Следовательно, принцип влечёт противоречие.

В отличие от брадобрея, здесь существование $Z$ было не допущением рассказа, а принципом теории. Парадокс Рассела разрешается не объявлением того, что $Z$ не существует, а перестройкой теории: аксиоматическая теория множеств Цермело 1908 года позволяет образовывать с помощью свойства лишь подмножества уже данного множества, и при этом ограничении противоречие не выводится.

Что не есть парадокс

Иногда «парадоксом пустого множества» называют наблюдение, что пустое множество существует, хотя не имеет элементов, как если бы существующий объект должен был состоять из существующих объектов. Никакого противоречия здесь нет: множество не состоит из своих элементов, как стена из кирпичей, а определяется ими, и совокупность элементов множества может не содержать ни одного, подобно тому как пустая коробка остаётся коробкой. То, что факт удивляет, не делает его парадоксальным; парадокс требует вывести противоречие, а здесь никакого противоречия не выводится.

Как с ними обходится формальный язык

Из сказанного следует, что формальный язык избегает парадоксов не по волшебству, а двумя точными способами. Первый состоит в том, что у него может не быть средств, которые их порождают. Язык логики высказываний, который строит этот курс, не имеет ни предложений, говорящих о самих себе, ни предиката истинности: в нём нельзя записать предложение лжеца, и его семантика приписывает каждой формуле при каждой оценке переменных единственное истинностное значение. Второй состоит в том, что в более богатых языках парадокс превращается в теорему: рассуждение лжеца, проведённое строго, доказывает, что истинность достаточно выразительного языка не определима в самом этом языке (Тарский); рассуждение о брадобрее и о Расселе доказывает, что некоторые совокупности не являются множествами; а рассуждения, родственные рассуждению Берри, лежат в основе теорем Курта Гёделя о неполноте 1931 года. Так то, что в естественном языке есть недоумение, в формальном языке есть информация.

Четыре основания математической логики

Математическая логика родилась в конце XIX и начале XX века, у Фреге, Пеано, Рассела и Давида Гильберта, как ответ на точный вопрос: на каких основаниях покоится математика и свободны ли эти основания от противоречий. Сегодня её делят на четыре больших раздела, постоянно переплетающихся между собой.

Теория доказательств: изучает формальные доказательства как математические объекты, то есть как конечные последовательности формул, подчинённые явным правилам; спрашивает, что можно доказать в системе, непротиворечива ли система и как одни доказательства преобразуются в другие. Модуль «Вывод» этого курса даёт первое знакомство с ней.
Теория моделей: изучает отношение между формальным языком и структурами, которые его интерпретируют, его моделями; спрашивает, какие структуры выполняют множество формул и какие свойства структур выразимы в данном языке. Модуль «Семантика» с его оценками истинностных значений есть её самый элементарный вариант.
Теория множеств: изучает множества с помощью точных аксиом, таких как аксиомы Цермело и Френкеля, в рамках которых можно записать почти всю математику; она родилась во многом из необходимости избежать парадокса Рассела.
Теория вычислимости: изучает, какие задачи можно решить механической процедурой, а какие нельзя. Логика высказываний разрешима, как увидит курс: существует процедура, которая за конечное число шагов решает, общезначима ли формула; логика предикатов, напротив, неразрешима.

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

Карта курса

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

Язык: синтаксис. Строится язык-объект с его алфавитом из двух символов и правилом образования, доказывается, что каждая формула читается единственным образом, мы учимся доказывать по индукции, и высказывания и рассуждения естественного языка переводятся на формальный язык с указанием того, что перевод сохраняет и что теряет.
Вывод: фиксируется система аксиом и правил вывода и определяется, что значит, что формула $\varphi$ выводится из множества формул $\Gamma$ , что записывается как $\Gamma \vdash \varphi$ . Это синтаксическая сторона правильности: обращение со знаками по правилам, без внимания к их значению.
Семантика: каждой формуле приписывается истинностное значение при каждой оценке и определяется, что значит, что $\varphi$ есть следствие $\Gamma$ , что записывается как $\Gamma \models \varphi$ : всякая оценка, при которой истинны формулы из $\Gamma$ , делает истинной $\varphi$ . Это семантическая сторона правильности, определение этого урока, ставшее точным.
Метатеория: доказывается, что обе стороны совпадают. Корректность говорит, что всё выводимое есть следствие, а полнота, что всякое следствие выводимо. Затем изучаются компактность и механический метод, резолюция, позволяющий решать, выполнимо ли множество формул.

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

Решённые задачи

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

Решённая задача 1Всё истинно, и всё же неправильно

Показать, что следующее рассуждение неправильно, хотя его посылки и заключение истинны: «всякое число, кратное $6$ , чётно; число $12$ чётно; следовательно, $12$ кратно $6$ ».

Решение

$(\forall x)\,(S(x) \Rightarrow P(x)), \quad P(12), \quad S(12)$
Сократим « $x$ кратно $6$ » через $S(x)$ , а « $x$ чётно» через $P(x)$ . Посылки и заключение истинны, потому что $12 = 6 \cdot 2$ .
$(\forall x)\,(S(x) \Rightarrow P(x)), \quad P(\resaltar{c}), \quad S(\resaltar{c})$
Форма получается заменой имени $12$ буквой $c$ : две посылки и заключение.
$(\forall x)\,(S(x) \Rightarrow P(x)), \quad P(\resaltar{4})$
Ищем частный случай с истинными посылками: первая не зависит от $c$ , а вторая требует чётного числа. Возьмём $c = 4$ .
$\neg S(\resaltar{4})$
Заключение этого частного случая ложно, потому что $4$ не кратно $6$ .
$\resaltar{12 = 6 \cdot 2}$
У формы есть контрпример: она неправильна, и рассуждение тоже. Истинность его заключения происходит из арифметики, а не из посылок.

Решённая задача 2Многозначность области действия

Пусть $L$ есть список чисел $4$ , $6$ , $7$ . Показать, что предложение «все числа из $L$ не являются простыми» имеет два прочтения и что для этого списка одно из них истинно, а другое ложно.

Решение

$\dato{a}{\neg Q(4) \wedge \neg Q(6) \wedge \neg Q(7)}$
Сократим « $x$ простое» через $Q(x)$ . Первое прочтение: отрицание действует на каждое число, и предложение говорит, что ни одно не простое.
$\dato{n}{\neg\left( Q(4) \wedge Q(6) \wedge Q(7) \right)}$
Второе прочтение: отрицание действует на всё утверждение, и предложение говорит, что не все числа простые.
$Q(7), \quad \neg\left( \neg Q(4) \wedge \neg Q(6) \wedge \resaltar{\neg Q(7)} \right)$
Поскольку $7$ простое, последний член первого прочтения ложен, а с ним и вся конъюнкция: первое прочтение ложно.
$\neg Q(4), \quad \neg\left( \resaltar{Q(4)} \wedge Q(6) \wedge Q(7) \right)$
Поскольку $4$ не простое, конъюнкция второго прочтения ложна, а её отрицание истинно: второе прочтение истинно.
$\resaltar{\neg Q(4) \wedge \neg Q(6) \wedge \neg Q(7)} \Rightarrow \neg\left( Q(4) \wedge Q(6) \wedge Q(7) \right)$
Два прочтения не равносильны: первое влечёт второе, но не наоборот, и этот список это показывает. В математике второе записывают как «не все числа из $L$ простые», а первое, как «ни одно число из $L$ не простое».

Решённая задача 3Язык-объект и метаязык

Возьмём в качестве языка-объекта последовательности символов $\sigO$ и $\sigI$ , а в качестве метаязыка русский язык с греческими буквами, обозначающими произвольные последовательности. Классифицировать каждое из следующих выражений и решить, когда это имеет смысл, истинно ли оно: (а) $\sigO\sigO\sigI$ ; (б) « $\sigO\sigO\sigI$ состоит из трёх символов»; (в) «для всякой последовательности $\varphi$ последовательность $\sigI\varphi$ начинается с диска»; (г) « $\sigO\sigO\sigI$ истинна».

Решение

$\resaltar{\sigO\sigO\sigI}$
Выражение (а) принадлежит языку-объекту: это последовательность символов, а не предложение русского языка, и оно не истинно и не ложно; о нём говорят, но само оно ничего не утверждает.
$\sigO \; \sigO \; \sigI \quad (3)$
Выражение (б) есть предложение метаязыка, которое упоминает последовательность (а) и считает её символы: оно истинно.
$\resaltar{\sigI}\varphi$
Выражение (в) есть предложение метаязыка. Буква $\varphi$ не есть символ языка-объекта, а есть переменная метаязыка, пробегающая его последовательности; предложение истинно, потому что $\sigI\varphi$ по построению начинается с диска.
$v_2 = \sigO\sigO\sigI$
Выражение (г) принадлежит метаязыку, но пока не имеет истинностного значения: последовательность $\sigO\sigO\sigI$ будет переменной языка курса, а переменная не истинна и не ложна сама по себе, а лишь тогда, когда оценка, в модуле «Семантика», придаёт ей значение. В следующем уроке её назовут $v_2$ .

Решённая задача 4Эпименид не есть лжец

На доске написано предложение $e$ , возможно, среди прочих: «всякое предложение, написанное на этой доске, ложно». Принимая двузначность и схему истинности, доказать, что $e$ ложно и что на доске есть какое-то другое истинное предложение; и вывести, что парадокс возникает тогда и только тогда, когда никакое другое предложение на доске не истинно, как бывает, если $e$ на доске единственное.

Решение

$\dato{T}{V(e) \Leftrightarrow (\forall x \in O)\,F(x)}$
Пусть $O$ есть множество предложений на доске; $e$ есть одно из них. По схеме истинности $e$ истинно тогда и только тогда, когда все предложения из $O$ ложны.
$V(e) \Rightarrow \resaltar{F(e)} \Rightarrow \neg V(e)$
Если бы $e$ было истинно, все предложения из $O$ были бы ложны, а $e$ лежит в $O$ : $e$ было бы ложно и по двузначности не было бы истинно. Предположение опровергает само себя.
$\resaltar{F(e)}$
Следовательно, $e$ не истинно; по двузначности оно ложно.
$(\exists x \in O)\,\left( x \neq e \wedge V(x) \right)$
По схеме истинности то, что $e$ ложно, означает, что не все предложения из $O$ ложны: какое-то истинно, и это не $e$ , которое ложно.
$\neg (\exists x \in O)\,\left( x \neq e \wedge V(x) \right) \Rightarrow \resaltar{V(e) \wedge \neg V(e)}$
Если на доске есть другое истинное предложение, всё согласовано: $e$ просто ложно. Если же никакое другое не истинно, то нет никакого $x$ , отличного от $e$ , лежащего в $O$ и истинного, и получается противоречие, как в парадоксе лжеца; так бывает, в частности, когда $e$ есть единственное предложение на доске. Возникнет ли парадокс, зависит, следовательно, от эмпирического факта: от того, что написано на доске.

Решённая задача 5Гетерологическое

Прилагательное автологично, если оно применимо к самому себе («русский» есть русское слово; «многосложный» многосложно), и гетерологично, если нет («односложный» не односложно; «английский» не есть английское слово). Доказать, что если «гетерологический» есть прилагательное и отношение «применимо к» вполне определено для всех прилагательных, то получается противоречие; и решить, от какого допущения отказаться.

Решение

$\dato{R}{R(x, x)}$
Пусть $D$ есть совокупность прилагательных русского языка, а $R(x, y)$ есть отношение «прилагательное $x$ применимо к слову $y$ ». Прилагательное $x$ автологично, если $R(x, x)$ , и гетерологично, если $\neg R(x, x)$ .
$\dato{h}{(\forall x \in D)\,\left( R(h, x) \Leftrightarrow \neg R(x, x) \right)}$
Пусть $h$ есть прилагательное «гетерологический». По его определению оно применимо к прилагательному в точности тогда, когда это прилагательное не применимо к самому себе.
$R(\resaltar{h}, \resaltar{h}) \Leftrightarrow \neg R(\resaltar{h}, \resaltar{h})$
Если $h$ есть прилагательное, то оно лежит в $D$ , и его условие есть условие диагональной леммы. Взяв $x = h$ , получаем невозможную равносильность.
$h \in D \Rightarrow \resaltar{h \notin D}$
По диагональной лемме ни один объект из $D$ не удовлетворяет условию на $h$ . Если $h$ лежит в $D$ , возникает противоречие.
$\resaltar{h \notin D}$
Ложным оказывается второе допущение: «применимо к» не есть точное отношение для прилагательных, которые, как «гетерологический», сами определяются через это же отношение. В формальном языке отношение $R$ определялось бы в метаязыке, и прилагательное $h$ не принадлежало бы языку-объекту, так что условие $h \in D$ было бы ложным и противоречия не было бы.

Задачи для самостоятельного решения

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

Задача для самостоятельного решения 1Две похожие формы

Рассмотрим две следующие формы: (а) «если $p$ , то $q$ ; не $q$ ; следовательно, не $p$ »; (б) «если $p$ , то $q$ ; не $p$ ; следовательно, не $q$ ». Решить, какая из них правильна, а какая нет; для неправильной построить контрпример из утверждений о числах, а для правильной объяснить, почему ни один её частный случай не может быть контрпримером.

Подсказка

Для формы (б) найди истинную импликацию между свойствами чисел, например «если $n$ кратно $4$ , то оно чётно», и число, у которого нет первого свойства, но есть второе. Для формы (а) предположи, что посылки истинны, и спроси себя, что произошло бы, если бы $p$ было истинно.

Ответ

Форма (а), называемая modus tollens, правильна: если посылки истинны и $p$ было бы истинно, то истинно было бы и $q$ , вопреки второй посылке. Форма (б), отрицание антецедента, неправильна: «если $6$ кратно $4$ , то $6$ чётно; $6$ не кратно $4$ ; следовательно, $6$ не чётно» имеет истинные посылки и ложное заключение.

Задача для самостоятельного решения 2Паспорт, удостоверение и виза

Объявление гласит: «для въезда необходим паспорт или удостоверение личности и виза». Записать два его прочтения с помощью букв $p$ (паспорт), $d$ (удостоверение личности) и $v$ (виза) и описать человека, которого одно прочтение впускает, а другое нет.

Подсказка

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

Ответ

Прочтения таковы: $p \vee (d \wedge v)$ и $(p \vee d) \wedge v$ . Человек с паспортом и без визы может въехать согласно первому прочтению и не может согласно второму.

Задача для самостоятельного решения 3Кавычки

Решить, говорит ли каждое предложение о городе или о слове и истинно оно или ложно: (а) «Рим состоит из трёх букв»; (б) «„Рим“ состоит из трёх букв»; (в) «„Рим“ есть столица Италии»; (г) «предложение „Рим есть столица Италии“ содержит слово „Рим“».

Подсказка

Кавычки превращают выражение в имя этого выражения. Спроси себя в каждом случае, какой объект обозначает подлежащее предложения: город, слово или предложение.

Ответ

(а) Говорит о городе и ложно, потому что у города нет букв. (б) Говорит о слове и истинно. (в) Говорит о слове и ложно, потому что слово не есть столица. (г) Говорит о предложении и о слове и истинно.

Задача для самостоятельного решения 4Две стороны одной карточки

На одной стороне карточки написано предложение $A$ : «предложение $B$ истинно»; на другой стороне, предложение $B$ : «предложение $A$ ложно». Принимая двузначность и схему истинности, доказать, что нет способа приписать истинностные значения $A$ и $B$ . Что произойдёт, если $B$ будет говорить, напротив, «предложение $A$ истинно»?

Подсказка

Запиши схему истинности для каждого предложения и соединяй равносильности, пока не получишь такую, которая связывает $V(A)$ с ним самим. В варианте сделай то же самое и проверь, какие приписывания значений ей удовлетворяют.

Ответ

В первом варианте получается $V(A) \Leftrightarrow \neg V(A)$ , как в парадоксе лжеца, хотя ни одно предложение не говорит о самом себе. Во втором варианте $V(A) \Leftrightarrow V(B)$ допускает два приписывания значений, оба истинны или оба ложны: противоречия нет, но ничто не решает выбор между ними.

Подробное решение

Решение

$\dato{A}{V(A) \Leftrightarrow V(B)}$
По схеме истинности $A$ истинно в точности тогда, когда истинно $B$ .
$\dato{B}{V(B) \Leftrightarrow F(A) \Leftrightarrow \neg V(A)}$
По схеме истинности $B$ истинно в точности тогда, когда $A$ ложно; по двузначности быть ложным значит не быть истинным.
$V(A) \Leftrightarrow \resaltar{\neg V(A)}$
Соединяя обе равносильности, получаем, что истинность $A$ равносильна её собственному отрицанию, и рассуждаем как в парадоксе лжеца: если $A$ истинно, то оно не истинно, а если не истинно, то истинно.
$V(A) \Leftrightarrow V(B) \Leftrightarrow V(A)$
Во втором варианте схема истинности для $B$ даёт $V(B) \Leftrightarrow V(A)$ , что вместе с первой равносильностью требует лишь, чтобы оба предложения имели одно и то же значение: есть два согласованных приписывания значений и никакого противоречия.

Задача для самостоятельного решения 5Диагональ Кантора

Пусть $s_1, s_2, s_3, \ldots$ есть произвольный список бесконечных последовательностей из нулей и единиц, и будем писать $s_x(y)$ для $y$ -го члена последовательности $s_x$ . Доказать с помощью диагональной леммы, что последовательность $d$ , определённая условиями $d(y) = 1$ , когда $s_y(y) = 0$ , и $d(y) = 0$ , когда $s_y(y) = 1$ , в списке не встречается. Вывести, что ни один занумерованный список не содержит всех последовательностей из нулей и единиц.

Подсказка

Возьми в качестве совокупности $D$ натуральные числа, а в качестве отношения $R(x, y)$ утверждение $s_x(y) = 1$ . Какому условию удовлетворяло бы число $b$ , такое что $s_b = d$ ?

Ответ

Если бы было $d = s_b$ , то число $b$ удовлетворяло бы условию $R(b, y) \Leftrightarrow \neg R(y, y)$ для всякого $y$ , что запрещено диагональной леммой. Следовательно, $d$ отличается от каждой $s_b$ по крайней мере $b$ -м членом, и ни один список не содержит всех последовательностей.

Подробное решение

Решение

$\dato{R}{R(x, y) \Leftrightarrow s_x(y) = 1}$
Пусть $D$ есть множество натуральных чисел, а $R(x, y)$ есть утверждение о том, что $y$ -й член $s_x$ равен $1$ .
$\dato{d}{d(y) = 1 \Leftrightarrow \neg\left( s_y(y) = 1 \right)}$
По определению $d(y)$ равно $1$ в точности тогда, когда $s_y(y)$ не равно $1$ .
$(\forall y \in D)\,\left( R(\resaltar{b}, y) \Leftrightarrow \neg R(y, y) \right)$
Предположим, что $d$ стоит в списке на месте $b$ , то есть $d = s_b$ . Тогда для всякого $y$ утверждение $R(b, y)$ равносильно $d(y) = 1$ , что равносильно $\neg R(y, y)$ .
$d(b) \neq s_b(b)$
По диагональной лемме ни одно $b$ этому условию не удовлетворяет: последовательность $d$ в списке не встречается. Конкретно, она отличается от $s_b$ $b$ -м членом.
$(\forall b \in \mathbb{N})\,(d \neq s_b)$
Поскольку список был произвольным, ни один занумерованный список не содержит всех последовательностей из нулей и единиц: в каждом списке недостаёт по меньшей мере его диагональной последовательности.