«Боже, дай мне разум и душевный покой принять то, что я не могу изменить, мужество изменить то, что я могу, и мудрость отличить одно от другого». Молитва об умиротворении Рейнхольда Нибура
Уровень B1 — это момент, когда язык перестаёт быть только описательным и становится инструментом компетентного мышления: логика высказываний и логика предикатов строятся строго, символ за символом, а модели превращают синтаксис в нечто, что можно сверить с семантикой — и всё это увенчивается двумя самыми знаменитыми теоремами Гёделя.
Формализация самой логики — превращение её в объект математического изучения — была главным проектом на рубеже XX века: «Principia Mathematica» Фреге, Рассела и Уайтхеда и программа Гильберта были нацелены на строгие аксиоматические системы логики, достаточно сильные, чтобы перестроить на них всю математику. На уровне B1 книга идёт тем же путём: пропозициональные формулы определяются ровно тремя правилами (любая переменная — формула; комбинации под $\neg,\land,\lor,\to$ — формулы; ничего больше), и всё дальнейшее — выводимость, корректность, полнота — строится строго на этом синтаксисе.
Награда — настоящий сдвиг в возможностях языка. Вплоть до уровня A2 язык $\Math$ описывал вещи. Теперь он способен удостоверить, что одно описание следует из других описаний, — разница между умением говорить на языке и умением компетентно на нём рассуждать.
Теория непротиворечива, если из неё не выводимы одновременно формула и её отрицание; она совместна, если у неё есть модель — структура, в которой истинны все её теоремы. Звучит как два разных свойства: одно про доказательства, другое про семантику. Теорема Гёделя о полноте логики предикатов говорит, что это одно и то же свойство, сформулированное как единый критерий.
Два направления этого критерия весят совсем не одинаково. Гёделю принадлежит доказательство содержательного направления, слева направо — непротиворечива $\Rightarrow$ совместна, — которое строит модель из одних лишь термов самого языка: все константные символы отправляются в универсум, а каждая истинная экзистенциальная формула даёт терм-«свидетель», выразимый в самом языке. Обратное, справа налево, сравнительно тривиально: оно прямо следует из корректности исчисления предикатов относительно моделей — если в какой-то модели истинны все аксиомы теории, то по индукции по длине вывода всякая формула, выводимая из этих аксиом, тоже истинна в этой модели, а значит, теория, у которой есть модель, никогда не может вывести одновременно $\varphi$ и $\neg\varphi$.
Равносильная формулировка того же критерия: $\Gamma\Vdash\varphi$ равносильно $\Gamma\vdash\varphi$ — семантическое следование и синтаксическая выводимость оказываются в классической логике предикатов одним и тем же отношением.
Неполнота затем проводит границу: чистая логика предикатов, теория порядков, теория равенства, теория групп — все они непротиворечивы и полны относительно метатеории. В тот момент, когда теория получает способность говорить о собственной доказуемости (как это умеет арифметика Пеано через гёделевскую нумерацию), полнота теряется — факт, который снова и снова подтверждают независимые формулы вроде аксиомы выбора относительно $\mathsf{ZF}$ или пятого постулата Евклида относительно абсолютной геометрии.
Одно упражнение из блока задач главы, из русского издания.
Всего в уровне B1 — 20 упражнений, каждое с полным разобранным решением в приложении книги.