Логика и множества

Пятьдесят глав подряд мы доказывали теоремы и ни разу не спросили, что значит само это слово. Мы писали «для любого $\varepsilon > 0$ найдётся $\delta$», «множество значений», «бесконечно много простых», «следовательно», а прошлая глава мерила информацию ответами «да» или «нет». Всё это работало так, как работает родной язык: им пользуются, не открывая грамматики.

Но у родного языка есть привычки, которые математике не годятся. «Чай или кофе?» в самолёте предлагает одно из двух, а в объявлении «скидка студентам или пенсионерам» студент-пенсионер скидки не лишится. «Все студенты сдали» иногда значит «почти все». Языку математики нужно, чтобы у каждой фразы был ровно один смысл, а про каждое рассуждение можно было проверить, правильно ли оно. Его грамматику мы и выучим, а упражняться будем на острове, который придумал американский логик и фокусник Рэймонд Смаллиан в книге «Как же называется эта книга?» (1978).

Остров рыцарей и лжецов

На острове живут жители двух типов. Рыцари всегда говорят правду, лжецы всегда лгут. Снаружи их не отличить. Вы встречаете двоих, $A$ и $B$, и $A$ говорит: «Хотя бы один из нас лжец». Кто есть кто?

Переберём случаи. Пусть $A$ лжец. Тогда его слова ложны, то есть лжецов среди них нет и оба рыцари, включая самого $A$. Противоречие: $A$ не может быть одновременно лжецом и рыцарем. Значит, $A$ рыцарь. Тогда его слова правдивы, и лжец среди двоих есть. Раз это не $A$, то это $B$. Ответ: $A$ рыцарь, $B$ лжец.

Мы перебрали возможные миры и отбросили тот, что противоречит сам себе, — обе главные операции этой главы. Слова островитянина либо истинны, либо ложны, и тип жителя обязан совпадать с истинностью его слов.

На острове есть фраза, которую не может произнести никто: «Я лжец». Рыцарь, сказав её, солгал бы, а лжец сказал бы правду. Такие фразы не истинны и не ложны, и в мир высказываний их не пускают. Запомним эту фразу: в конце главы она вернётся и едва не разрушит всю математику.

Жителей трое. $A$ говорит: «Мы все лжецы». $B$ говорит: «Ровно один из нас рыцарь». $C$ молчит. Сколько среди них рыцарей?

$A$ не может быть рыцарем: тогда его слова «мы все лжецы» были бы правдой, и он оказался бы лжецом. Значит, $A$ лжец, его слова ложны, и хотя бы один рыцарь среди троих есть. Если бы $B$ был лжецом, рыцарем был бы только $C$ — ровно один, и слова $B$ оказались бы правдой. Противоречие, значит, $B$ рыцарь, и рыцарь среди троих ровно один: $C$ лжец. Ответ: один рыцарь. Проверьте в виджете, собрав этот остров во вкладке «Свой остров».

Урок первый: не, и, или

Из простых высказываний складывают сложные с помощью слов-связок, которые логики договорились понимать строго и записывать значками. Отрицание $\lnot A$ («не $A$») истинно, когда $A$ ложно. Конъюнкция $A \land B$ («$A$ и $B$») истинна, когда истинны оба. Дизъюнкция $A \lor B$ («$A$ или $B$») истинна, когда истинно хотя бы одно из двух, в том числе когда оба. Это «или» из объявления о скидке, а не из самолёта; для «ровно одного из двух» есть отдельная связка, исключающее «или» $A \oplus B$.

Истинность сложного высказывания зависит только от истинности частей, поэтому связку целиком описывает таблица всех сочетаний. Истину обозначим буквой И, ложь — буквой Л.

Значок $\equiv$ не связка внутри формулы, а наше утверждение о двух формулах. Простейшая тавтология — $A \lor \lnot A$, закон исключённого третьего: любое высказывание истинно или ложно. Второй знаменитый закон отвечает на вопрос, который возникает в любом споре: что значит, что человек неправ, если он сказал «или»?

Хитрость в том, что таблица истинности конечна: проверив четыре строки, мы проверили все возможные случаи сразу.

Выпишем все четыре сочетания значений $A$ и $B$. Других не бывает: каждое высказывание либо истинно, либо ложно. В каждой строке найдём $A \lor B$: ложь только в последней, где ложны оба. Отрицание переворачивает столбец: $\lnot(A \lor B)$ истинно только в последней строке. Теперь правая часть. Конъюнкция $\lnot A \land \lnot B$ истинна, когда истинны $\lnot A$ и $\lnot B$, то есть когда ложны и $A$, и $B$. Это снова только последняя строка. Столбцы совпадают во всех четырёх строках. Значит, $\lnot(A \lor B) \equiv \lnot A \land \lnot B$ — первый закон доказан. Второй закон выведем из первого, не рисуя новой таблицы. Первый закон верен для любых высказываний, в том числе для $\lnot A$ и $\lnot B$: $\lnot(\lnot A \lor \lnot B) \equiv \lnot\lnot A \land \lnot\lnot B \equiv A \land B$, ведь двойное отрицание возвращает исходное значение. Равносильные формулы и после отрицания остаются равносильными, поэтому $\lnot A \lor \lnot B \equiv \lnot(A \land B)$.

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

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

Урок второй: если…, то…

Самая коварная связка — «если…, то…». Возьмём обещание: «Если завтра пойдёт дождь, я возьму зонт». Когда его нарушат? Только если дождь пошёл, а зонта нет. Если дождя нет, обещание ничего не требовало, и нарушить его нельзя, что бы человек ни сделал с зонтом.

Посылка: «пойдёт дождь». Пока она ложна, импликация истинна при любом заключении. Заключение: «я возьму зонт». Если оно истинно, импликация истинна при любой посылке. Отрицание посылки. Импликация утверждает ровно одно: не бывает так, чтобы посылка выполнилась, а заключение нет. Пример: «если $n$ делится на $4$, то $n$ чётно». При $n = 8$ посылка и заключение истинны; при $n = 6$ посылка ложна, заключение истинно; при $n = 7$ ложны оба. Во всех трёх случаях импликация истинна. Опровергнуть её могло бы только число, которое делится на $4$ и нечётно, а таких нет.

Строки с ложной посылкой сбивают с толку сильнее всего: «если $2 + 2 = 5$, то Луна сделана из сыра» — истинное высказывание. Логики говорят: из лжи следует что угодно. По известной байке, Бертрана Рассела однажды попросили доказать, что из $2 + 2 = 5$ следует, что он римский папа. Рассел ответил: отнимем по три от обеих частей и получим $1 = 2$; папа и я — двое, значит, мы с папой — один человек. Именно поэтому противоречие в теории — катастрофа: если в ней доказаны и $C$, и $\lnot C$, то в ней доказуемо любое утверждение.

Поменяв посылку и заключение местами, получают обратное утверждение $B \to A$. Оно может быть верным, а может и не быть: «если число делится на $4$, оно чётно» верно, а «если число чётно, оно делится на $4$» — нет, контрпример $6$. Зато у каждой импликации есть близнец, который равносилен ей всегда.

Снова четыре строки. Ищем, где каждая импликация ложна: у импликации такая строка всего одна.

Выпишем четыре сочетания значений $A$ и $B$. $A \to B$ ложна только там, где $A$ истинно, а $B$ ложно, — во второй строке. $\lnot B \to \lnot A$ ложна только там, где истинно $\lnot B$ и ложно $\lnot A$, то есть $B$ ложно, а $A$ истинно. Это та же вторая строка. Столбцы совпадают во всех строках, значит, $A \to B \equiv \lnot B \to \lnot A$. Для сравнения — обратное утверждение $B \to A$. Оно ложно в третьей строке, где $B$ истинно, а $A$ ложно, а во второй истинно. Столбцы расходятся, и из $A \to B$ вывести $B \to A$ нельзя.

Смысл закона понятен и без таблицы. «Если идёт дождь, асфальт мокрый» и «если асфальт сухой, дождя нет» говорят одно и то же. А «если асфальт мокрый, идёт дождь» — уже другое: асфальт могла полить поливальная машина.

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

Правило «если на одной стороне гласная, то на другой чётное число» — импликация $P \to Q$, и нарушить её может только карточка, где $P$ истинно, а $Q$ ложно. Переворачивать надо $E$ (вдруг за ней нечётное) и $7$ (вдруг за ней гласная). У карточки $K$ посылка ложна, у карточки $4$ заключение уже истинно, и оборот ничего не решает. Большинство выбирает $E$ и $4$ или одну $E$; правильный ответ в разных опытах дают порядка одного человека из десяти. Посылку мы проверяем, а про контрапозицию «если нечётное, то не гласная» забываем.

Правило бара «если пьёт пиво, то старше восемнадцати» устроено так же: проверять надо пиво и шестнадцатилетнего. Здесь в опытах правильно отвечает большинство — искать нарушителей мы привыкли в жизни. Логика в двух вкладках одна, а интуиция разная, и математике нужна логика, которая не зависит от того, о чём речь.

Импликации в обе стороны дают эквивалентность $A \leftrightarrow B \equiv (A \to B) \land (B \to A)$: «$A$ тогда и только тогда, когда $B$», «$A$ необходимо и достаточно для $B$». Так связаны житель острова и его слова: если $X$ — «$X$ рыцарь», а $S$ — сказанное, то $X \leftrightarrow S$. Вся головоломка острова — конъюнкция таких эквивалентностей, и виджет выше решал её таблицей.

Урок третий: все и некоторые

Связок не хватает, чтобы записать самое обычное математическое утверждение: «квадрат любого числа неотрицателен». Здесь говорится не про одно высказывание, а про бесконечно много: $0^2 \ge 0$, $1^2 \ge 0$, $(-2{,}5)^2 \ge 0$, …

Значок $\exists$ — повёрнутая буква E, от слова «существует» (exists); его ввёл Джузеппе Пеано в 1897 году. Значок $\forall$ — перевёрнутая A (all) — появился только в 1935-м, у Герхарда Генцена. Кванторы кажутся простыми словами, пока их не два. Пусть $R(s, z)$ означает «студент $s$ решил задачу $z$». Фраза $\forall z\ \exists s\ R(s, z)$ читается «каждую задачу кто-нибудь решил», а $\exists s\ \forall z\ R(s, z)$ — «кто-то решил все задачи». Разница только в порядке значков, а смысл разный: во второй фразе один студент на всех, в первой у каждой задачи может быть свой. Из второй первая следует, обратно — нет.

Понимание кванторов лучше всего проверять игрой. Утверждение с кванторами — партия двух игроков: Доказывающий ходит за $\exists$ и выбирает подходящий объект, Опровергающий ходит за $\forall$ и выбирает самый неудобный. Утверждение истинно, если у Доказывающего есть выигрышная стратегия, — так истину объясняют в игровой семантике, которую развивал финский логик Яакко Хинтикка.

В партии за $\forall z\ \exists s$ Доказывающий выбирает студента, уже зная задачу, и его выбор может от задачи зависеть. В партии за $\exists s\ \forall z$ он выбирает вслепую, одного студента против любой задачи. Так же было в игре со Скептиком из главы о пределах: мы называли $N$, уже услышав $\varepsilon$.

Как отрицать утверждения с кванторами? «Не все лебеди белые» означает «есть лебедь, который не белый». Европейцы веками считали лебедей белыми, пока в конце XVII века голландские моряки не увидели в Австралии чёрных, и одного чёрного лебедя хватило.

Отсюда механическое правило: чтобы отрицать цепочку кванторов, каждый $\forall$ меняют на $\exists$, каждый $\exists$ на $\forall$, а утверждение в конце отрицают. Одна тонкость: условие, прикреплённое к переменной, как в $\forall \varepsilon > 0$, при отрицании остаётся на месте. Запись $\forall \varepsilon > 0\ \ Q$ — сокращение для $\forall \varepsilon\ (\varepsilon > 0 \to Q)$, и её отрицание по закону для импликации $\lnot(A \to B) \equiv A \land \lnot B$ есть $\exists \varepsilon\ (\varepsilon > 0 \land \lnot Q)$, то есть $\exists \varepsilon > 0\ \ \lnot Q$.

Теперь можно честно сказать, что значит «последовательность не стремится к $a$». Определение из главы 25 и его отрицание:

$$a_n \to a:\quad \forall \varepsilon > 0\ \ \exists N\ \ \forall n > N\quad |a_n - a| < \varepsilon;$$ $$a_n \not\to a:\quad \exists \varepsilon > 0\ \ \forall N\ \ \exists n > N\quad |a_n - a| \ge \varepsilon.$$

Вторая строка — готовая стратегия Скептика: один допуск $\varepsilon$, и после любого номера $N$ найдётся член вне полосы. Для $(-1)^n$ и $a = 1$ годится $\varepsilon = 1$: после любого $N$ встретится нечётный $n$, а там $|a_n - 1| = 2 \ge 1$. В главе 25 этот ход мы нашли догадкой, теперь его выдаёт правило.

Функция $f$ непрерывна в точке $a$, если $\forall \varepsilon > 0\ \exists \delta > 0\ \forall x$: из $|x - a| < \delta$ следует $|f(x) - f(a)| < \varepsilon$. Что значит, что $f$ в точке $a$ разрывна?

$\exists \varepsilon > 0\ \forall \delta > 0\ \exists x$: $|x - a| < \delta$ и $|f(x) - f(a)| \ge \varepsilon$ $\exists \varepsilon > 0\ \forall \delta > 0\ \exists x$: из $|x - a| < \delta$ следует $|f(x) - f(a)| < \varepsilon$ $\forall \varepsilon \le 0\ \exists \delta \le 0\ \forall x$: из $|x - a| \ge \delta$ следует $|f(x) - f(a)| \ge \varepsilon$ $\exists \varepsilon > 0\ \forall \delta > 0\ \forall x$: из $|x - a| < \delta$ следует $|f(x) - f(a)| \ge \varepsilon$

Меняем $\forall \varepsilon$ на $\exists \varepsilon$, $\exists \delta$ на $\forall \delta$, $\forall x$ на $\exists x$ и отрицаем импликацию: $\lnot(A \to B) \equiv A \land \lnot B$. Получилась стратегия Скептика: он называет один допуск, и в любом окошке вокруг $a$, даже самом узком, находит точку, где значение отскочило от $f(a)$ хотя бы на $\varepsilon$. Так ведёт себя знак $\operatorname{sgn} x$ в нуле: годится $\varepsilon = \frac12$.

Урок четвёртый: грамматика доказательства

В главе 0 доказательство было названо цепочкой шагов, каждый из которых по правилам логики следует из предыдущих. Теперь правила можно назвать. Формально доказательство — конечная последовательность высказываний, каждое из которых либо аксиома, либо уже доказанная теорема, либо допущение, либо получено из предыдущих по правилу вывода. Главное правило вывода знали ещё древнегреческие стоики: из $A$ и $A \to B$ следует $B$. Его называют modus ponens, а его законность видна из таблицы: формула $\bigl(A \land (A \to B)\bigr) \to B$ — тавтология. Такую последовательность может проверить машина, не понимающая смысла слов; программы вроде Lean и Coq так и проверяют доказательства больших теорем (глава 60). Люди пишут короче, но ход их доказательств подчиняется нескольким схемам, и каждая схема — тавтология.

С обратной стороны

Иногда из $A$ трудно вывести $B$, а из $\lnot B$ вывести $\lnot A$ легко. По закону контрапозиции это одно и то же.

Напрямую непонятно, с какой стороны зайти. Докажем контрапозицию: если заключение ложно, то ложна и посылка.

Отрицание заключения «$a > 10$ или $b > 10$» по закону де Моргана — «$a \le 10$ и $b \le 10$». Отложим от угла квадрата $10 \times 10$ прямоугольник со сторонами $a$ и $b$. Раз обе стороны не длиннее десяти, его противоположный угол лежит внутри квадрата или на его границе. Весь прямоугольник помещается в квадрат: он заполняет угол квадрата, от которого отложен. Часть фигуры не больше целого, поэтому $ab \le 10 \cdot 10 = 100$. Без картинки: $ab \le 10b \le 10 \cdot 10$, потому что при положительных множителях неравенства можно умножать. Мы доказали $\lnot B \to \lnot A$: если $a \le 10$ и $b \le 10$, то $ab \le 100$. По закону контрапозиции это равносильно исходному утверждению.

От противного

От противного: предполагаем $\lnot A$ и выводим противоречие $C \land \lnot C$; формула $(\lnot A \to (C \land \lnot C)) \to A$ — тавтология. Так доказаны иррациональность $\sqrt2$ (глава 6) и бесконечность ряда простых (глава 3). Вот пример ещё короче.

По цепочке

Математическая индукция из главы 13 тоже схема: $\bigl(P(1) \land \forall k\ (P(k) \to P(k + 1))\bigr) \to \forall n\ P(n)$. Её строгость лучше всего видна на доказательстве, которое ею притворяется.

«Докажем, что все лошади одной масти. Утверждение $P(n)$: в любом табуне из $n$ лошадей все одной масти. База: $P(1)$ верно. Шаг: возьмём табун из $k + 1$ лошади. Без последней лошади остаётся табун из $k$ — они одной масти; без первой — тоже $k$, тоже одной масти. Лошади в середине входят в оба табуна, значит, масть у всех одна». Где ошибка?

В базе: $P(1)$ не доказано Шаг не работает при переходе от $k = 1$ к $k + 1 = 2$ Нельзя предполагать $P(k)$, это и надо доказать Лошадей на свете конечное число, индукция к ним неприменима

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

Предъявить или доказать, что есть

Утверждение «существует $x$ со свойством $P$» проще всего доказать построением, предъявив такой $x$. Но иногда существование удаётся доказать, не показав объекта.

Доказательство безупречно, но какая из двух пар работает, оно не говорит. Такие доказательства называют неконструктивными; интуиционисты, часть логиков XX века, их не признавали. Здесь ответ, впрочем, известен: по теореме Гельфонда — Шнайдера (1934) число $\sqrt2^{\sqrt2}$ трансцендентно, так что работает второй случай. А есть и совсем простой конструктивный пример: $\sqrt2^{\log_2 9} = 2^{\frac12\log_2 9} = 2^{\log_2 3} = 3$, где $\log_2 9$ иррационален по той же причине, что и $\log_2 3$.

Одним примером

Последняя схема — опровержение. Раз $\lnot\,\forall x\ P(x) \equiv \exists x\ \lnot P(x)$, утверждение «для всех» опровергает один контрпример. А утверждение «существует» примером не опровергнешь: его отрицание начинается с «для всех» и требует доказательства. С этой асимметрии начинался курс.

Урок пятый: множества

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

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

Задают множество либо списком, $\{2, 3, 5, 7\}$, либо свойством: $\{x \in \mathbb R \mid x^2 < 2\}$ — все действительные $x$, для которых $x^2 < 2$, то есть интервал $(-\sqrt2;\ \sqrt2)$. Порядок и повторы в списке не важны: $\{1, 2, 2\} = \{2, 1\}$, у них одни и те же элементы.

Пустое множество — подмножество любого $A$: условие $\forall x\ (x \in \varnothing \to x \in A)$ выполнено, потому что посылка $x \in \varnothing$ всегда ложна, а из лжи следует что угодно. И пустое множество одно: у двух пустых множеств одни и те же элементы — никаких.

Операции над множествами — связки логики в новом платье: $x \in A \cup B$ означает $x \in A \lor x \in B$, пересечение — «и», дополнение — «не». Каждый закон логики сразу даёт закон для множеств, а круги Эйлера — таблица истинности, нарисованная на плоскости.

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

Внутри объемлющего прямоугольника $U$ — два круга, $A$ и $B$. Они делят $U$ на четыре области: в обоих кругах, только в $A$, только в $B$, вне обоих. Объединение $A \cup B$ — три области из четырёх, всё, что попало хотя бы в один круг. Его дополнение $(A \cup B)^{c}$ — оставшаяся четвёртая область, снаружи обоих кругов. Теперь правая часть. $A^{c}$ — всё вне круга $A$; заштрихуем его наклонными линиями. $B^{c}$ — всё вне круга $B$; заштрихуем его в другую сторону. Пересечение $A^{c} \cap B^{c}$ — там, где штриховки перекрещиваются: вне обоих кругов. Это та же область, что и на третьем шаге. Области совпали при любом расположении кругов — двигайте центры, проверьте, что и у кругов без общих точек всё сходится. На языке элементов: $x \in (A \cup B)^{c} \iff \lnot(x \in A \lor x \in B) \iff (x \notin A) \land (x \notin B) \iff x \in A^{c} \cap B^{c}$ по первому закону де Моргана для высказываний. Второй закон получается так же из второго.

Сколько строк таблицы истинности формулы $A \lor B \lor C \lor D$ содержат И? Иными словами, на сколько областей из шестнадцати ложится объединение четырёх множеств общего положения?

Всего строк $2^4 = 16$. Дизъюнкция ложна только там, где ложны все четыре переменные, — это одна строка. Остальные $16 - 1 = 15$ строк дают И.

Урок шестой: функция — это множество пар

В главе 9 функция была правилом: каждому $x$ сопоставляется ровно одно $y$. Но что такое «правило»? Теория множеств отвечает неожиданно: функцию можно отождествить с её графиком.

Никакого «правила» в определении нет: отображение — список пар, в котором каждый элемент $A$ стоит первым ровно один раз, и формулой его задавать не обязательно. Три главных свойства отображений — про стрелки, которые ведут из $A$ в $B$.

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

Для бесконечных множеств это неверно, и здесь начинается следующая глава. Отображение $n \mapsto n + 1$ из $\mathbb N$ в $\mathbb N$ инъективно, но в единицу не ведёт ни одна стрелка. А $n \mapsto \lceil n/2 \rceil$ (половина, округлённая вверх) задевает каждое натуральное число, но единицу получает дважды, из $1$ и из $2$.

Сколько существует сюръекций из множества $\{1, 2, 3\}$ в множество $\{a, b\}$?

Всего отображений $2^3 = 8$: каждый из трёх элементов независимо выбирает $a$ или $b$ (правило произведения). Не сюръективны только два из них: все в $a$ и все в $b$. Остаётся $8 - 2 = 6$. Инъекций среди них нет ни одной: трём элементам не хватит двух разных образов.

Урок седьмой: равные по-разному

Дроби $\frac12$, $\frac24$ и $\frac36$ записаны по-разному, а число одно (глава 5). Часы показывают одно и то же в 3 часа ночи и в 15 часов. Приём один: объекты объявляют «одинаковыми», если они совпадают в чём-то важном, и работают с целыми группами.

«Иметь одинаковый остаток при делении на $12$» — отношение эквивалентности на целых числах. «Делить» — нет: $2$ делит $4$, но $4$ не делит $2$, симметрии нет. «Отличаться меньше чем на единицу» — тоже нет: $0 \sim 0{,}6$ и $0{,}6 \sim 1{,}2$, но $0$ и $1{,}2$ отличаются больше чем на единицу, транзитивность нарушена. Эквивалентность же режет множество на куски без остатка и без наложений.

Теперь можно сказать, что такое остаток и что такое дробь, не произнося слов «одно и то же, записанное по-разному». Классы целых чисел по модулю $n$ — это элементы $\mathbb Z_n$ из главы об остатках: $\mathbb Z_{12}$ — двенадцать классов, цифры на циферблате. А положительное рациональное число — класс пар натуральных чисел по отношению $(p, q) \sim (p', q') \iff pq' = p'q$: пары $(1, 2)$, $(2, 4)$, $(3, 6)$, … образуют один класс, и этот класс и есть $\frac12$. На клетчатой плоскости каждый класс лежит на луче из начала координат — рисунок, который понадобится в следующей главе.

Сколько существует различных отношений эквивалентности на множестве $\{a, b, c\}$?

По теореме о разбиении отношение эквивалентности — то же, что разбиение множества на классы: зная классы, мы знаем, кто кому эквивалентен, и наоборот. Разбиений множества из трёх элементов пять: все в одном классе; каждый в своём; и три способа выделить пару — $\{a, b\}\{c\}$, $\{a, c\}\{b\}$, $\{b, c\}\{a\}$. Ответ: $5$.

Урок восьмой: слово, которое ломает словарь

Кантор разрешил называть множеством «любое объединение» объектов. Возьмём это всерьёз. Множество всех множеств, если оно есть, само множество и потому лежит в себе. Множество всех чашек не чашка и в себе не лежит. Соберём вместе все множества, которые не лежат сами в себе:

$$R = \{x \mid x \notin x\}.$$

Это разговор островитянина, который сказал «я лжец». Спросим про само $R$: лежит ли оно в себе?

Предположим, что $R$ существует. Про любое множество можно спросить, лежит ли оно в $R$, — и про само $R$ тоже. По закону исключённого третьего либо $R \in R$, либо $R \notin R$. Пусть $R \in R$. В $R$ лежат только множества, не содержащие себя, значит, $R \notin R$. Противоречие. Пусть $R \notin R$. Тогда $R$ — множество, не содержащее себя, а все такие множества по определению лежат в $R$. Значит, $R \in R$. Снова противоречие. Оба случая невозможны, и других нет. Значит, предположение неверно: такого множества нет. Короче: определение $R$ даёт $R \in R \leftrightarrow R \notin R$, а высказывание вида $A \leftrightarrow \lnot A$ ложно в каждой строке таблицы.

Бертран Рассел нашёл это противоречие в 1901 году; Эрнст Цермело в Гёттингене натолкнулся на него чуть раньше, но не опубликовал. В июне 1902 года Рассел написал о нём Готлобу Фреге, который заканчивал второй том «Основных законов арифметики» — попытки вывести всю арифметику из логики. Аксиомы Фреге разрешали собрать в множество всё, что обладает каким-нибудь свойством, и множество $R$ у него существовало. Том вышел в 1903 году с послесловием:

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

В популярной версии, которую пересказывал и сам Рассел, парадокс звучит так: деревенский брадобрей бреет тех и только тех жителей, кто не бреется сам. Бреет ли он себя? Оба ответа невозможны, но вывод прост: такого брадобрея не бывает. С множествами вывод тот же, а кризис в том, что прежние правила разрешали такое множество построить.

Выход нашёл тот же Цермело. В 1908 году он предложил аксиомы, по которым множество нельзя собрать «из всего на свете», а можно только вырезать из уже существующего.

Свой ход в споре с парадоксом аксиома выделения делает скромно: противоречивое множество не запрещено, его просто не из чего построить. Сегодня основой математики служит система ZFC: аксиомы Цермело, дополненные в 1922 году Абрахамом Френкелем и Туральфом Сколемом. Буква C в названии напоминает, что среди них есть аксиома выбора (choice) — её часто рассматривают отдельно от остальных. Вот все девять аксиом обзорно, словами:

Удивительно, что почти всей математике больше ничего не нужно. Числа тоже строятся из множеств: Джон фон Нейман в 1923 году предложил считать нулём пустое множество, единицей — $\{\varnothing\}$, двойкой — $\{\varnothing, \{\varnothing\}\}$ и вообще $n + 1 = n \cup \{n\}$. Здесь удобно начинать натуральный ряд с нуля; в российской школьной традиции ноль к натуральным числам не относят, и это вопрос договорённости, а не истины. Принцип индукции, который Пеано в 1889 году объявил аксиомой арифметики, в ZFC становится теоремой. Из пар натуральных чисел строятся целые и дроби (урок седьмой), из дробей — действительные числа, из них — функции, пространства, вероятности. Весь этот курс вырастает из девяти строк таблицы.

Экзамен на острове

Грамматику учат не только чтением, но и упражнениями. В тренажёре три уровня: посчитать строки таблицы истинности, выбрать правильное отрицание утверждения с кванторами и разобраться с жителями острова.

Куда дальше

Для конечных множеств мы доказали: если в $A$ и $B$ поровну элементов, то инъекция из $A$ в $B$ обязательно биекция. Для натуральных чисел это неверно: сдвиг $n \mapsto n + 1$ переводит $\mathbb N$ в его собственную часть $\{2, 3, 4, \dots\}$ взаимно однозначно. Выходит, у бесконечного множества столько же элементов, сколько у его части? Галилей заметил это ещё в 1638 году — квадратов $1, 4, 9, 16, \dots$ столько же, сколько всех натуральных чисел, — и решил, что слова «больше» и «меньше» к бесконечностям неприменимы. Георг Кантор решил иначе: считать множества одинаковыми по размеру, если между ними есть биекция, и посмотреть, что получится. Получилось, что бесконечности бывают разные. Можно ли сравнить натуральные числа с точками отрезка, и существует ли самая большая бесконечность, — спорят три собеседника в следующей главе.