Уровень B2 · Upper-Intermediate

Фундамент математики

«Бог создал натуральные числа, всё остальное — дело рук человеческих». Леопольд Кронекер

Уровень B2 пересекает настоящий порог: формулы приходят на смену словам. Аксиомы Пеано превращают «число» из интуиции в девять точных строк; наивная теория множеств Кантора превращает «совокупность» в рай — хотя, как гласит старая анонимная поговорка о теории множеств, это «рай с кучей тёмных подвалов», и парадокс Рассела — самый тёмный из них. Ответ главы — наследственно-конечные множества: достаточно богатая, свободная от парадоксов вселенная, построенная из одного лишь $\emptyset$.

Что вы узнаете

—Первопорядковую арифметику Пеано ($\mathsf{PA}$) аксиома за аксиомой: равенство, последователь, сложение, умножение, порядок и схема индукции.
—Почему индукция — это схема, по одной аксиоме на формулу, а не единое второпорядковое предложение, и чем это оборачивается по силе теории.
—Наивный принцип свёртывания Кантора, почему он так соблазнителен и как именно его ломает парадокс Рассела.
—Как ограничение свёртывания одним примитивным предикатом ($\in$) и коротким списком аксиом даёт наследственно-конечные множества ($\mathsf{HF}$) — свободные от парадоксов по построению.
—Почему $\mathsf{HF}$ и $\mathsf{PA}$ оказываются взаимно интерпретируемыми — два языка для одной и той же финитной математики.

1. От слов к формулам

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

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

2. Рай, его подвалы и выход из положения

Аксиомы арифметики Пеано достаточно коротки, чтобы прочесть их за один присест, — и последняя из них делает почти всю работу:

PA1–7Равенство, инъективность последователя, $S(a)\ne 0$, рекурсивные законы для $+,\cdot,<$.

PA8$\varphi[a/0]\land\forall x\,(\varphi[a/x]\to\varphi[a/Sx])\to\forall y\,\varphi[a/y]$ — индукция, по одной аксиоме на формулу $\varphi$.

Последний пункт — именно схема, а не единое предложение, потому что логика первого порядка не умеет квантифицировать по «всем свойствам», как это делает логика второго порядка, — ограничение с реальными последствиями: именно из-за него у $\mathsf{PA}$ есть нестандартные модели, и она не может однозначно зафиксировать $\mathbb N$ с точностью до изоморфизма так, как это умеет её второпорядковый аналог.

Подробный обзор всей этой лестницы теорий — от первопорядковой $\mathsf{PA}$ через $\mathsf{ACA}_0$ и $\mathsf{Z}_2$ до теоретико-множественной $\mathsf{ZFA}$ — см. в материале «Иерархия теорий арифметики второго порядка».

У наивной теории множеств Кантора такого ограничения нет: любое свойство $\mathcal A(a)$ задаёт множество $\{x\mid\mathcal A(x)\}$. Именно эта свобода позволила ему построить арифметику трансфинитных кардиналов — и именно она же ломается. Определим $R=\{x\mid x\notin x\}$. Верно ли $R\in R$? Если да, то по определению $R\notin R$; если нет, то $R$ удовлетворяет собственному определяющему свойству, значит $R\in R$. В любом случае — противоречие, парадокс Рассела.

Исправление — не в изобретательности, а в сдержанности: перестать спрашивать «какое свойство задаёт множество?» и начать спрашивать «отталкиваясь от уже имеющегося множества, какие новые множества мне позволено построить?». $\mathsf{HF}$, наследственно-конечные множества, отвечает коротким списком аксиом — пара, объединение, булеан, выделение, регулярность — и, что решающе важно, отрицанием аксиомы бесконечности. Результат — вселенная, где любое множество конечно, любой элемент множества сам конечен, и расселовское $R$ просто невозможно построить. А поскольку любое такое множество можно закодировать натуральным числом и обратно, $\mathsf{HF}$ и $\mathsf{PA}$ оказываются описанием одной и той же математики на двух разных диалектах.

3. Проверьте себя

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

Выразите утверждение «Каждое натуральное число является либо нулём, либо последователем» на языке $\PA$.
Формализуйте определение «квадратного числа» (полного квадрата), используя только умножение.
Выразите следующие арифметические понятия на языке $\PA$:
- «$x$ — чётное число».
- «$x$ является делителем $y$» ($x \mid y$).
- «$x$ — простое число».
- Гипотеза Гольдбаха: «Каждое чётное целое число, большее 2, является суммой двух простых чисел».
Запишите определение простого числа, используя только предикат делимости ($x \mid y$) и предикат обратимости (быть делителем единицы) $Inv(x) \leftrightarrow \exists y\,(xy=1)$.
Выразите «Гипотезу о числах-близнецах»: существует бесконечно много пар простых чисел $p, q$, таких что $q = S(S(p))$.

Всего в уровне B2 — 21 упражнение, каждое с полным разобранным решением в приложении книги.

Остальная часть уровня B2 — и ещё один уровень

Этот конспект пропускает полный вывод базовых свойств арифметики из одних лишь аксиом, точное различие слабого и сильного порядка, разницу между истинностью для всех натуральных чисел и формальной доказуемостью универсального утверждения, а также древовидное представление, делающее «наследственную конечность» наглядной. Уровень C1 доводит полную аксиоматику $\mathsf{ZFC}$, аксиому выбора и универсум фон Неймана до самого края теоретико-множественного рая.

Все способы купить К обзору книги

← Уровень B1 — Формальная логика Уровень C1 — Рай для математиков →