Множества и операции (углубление) ♾️

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

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

Дальше урок делает строгими операции, которые в школе вводились через картинки: объединение, пересечение, разность, симметрическая разность, декартово произведение. У каждой появится формальное определение через принадлежность элемента, и на этом языке докажутся законы де Моргана — не «проверь на кругах», а честное рассуждение «элемент слева тогда и только тогда, когда элемент справа». А в конце — отношения на множестве и один из самых полезных фактов курса: отношение эквивалентности и разбиение множества на непересекающиеся классы — это буквально одно и то же, только описанное с двух разных сторон.

Всё это не абстрактная гимнастика. Мощность множества различает дискретное и непрерывное вероятностное пространство — от этого зависит, суммировать вероятности или интегрировать плотность. Операции над множествами — это язык фильтров, JOIN-ов и WHERE-условий в любой базе данных. А отношение эквивалентности — это ровно то, что происходит, когда кластеризация разбивает датасет на группы: каждый кластер — класс эквивалентности по отношению «похож на».

История: откуда это взялось?

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

Кантор развил идею дальше и ввёл понятие кардинального числа — меры «количества элементов», которая работает и для бесконечных множеств. Он показал, что бесконечностей бесконечно много: для любого множества $A$ множество всех его подмножеств $\mathcal{P}(A)$ имеет строго бо́льшую мощность, чем само $A$ — сегодня это называют теоремой Кантора. Реакция коллег была резкой. Леопольд Кронекер, влиятельный берлинский профессор, считал канторовскую теорию бессмысленной игрой с несуществующими объектами и активно мешал её признанию. Зато Давид Гильберт оценил масштаб идеи иначе: он назвал канторовский рай «раем, из которого никто не сможет нас изгнать», имея в виду теорию множеств как новый фундамент для всей математики.

Наивная версия теории множеств (любое свойство задаёт множество объектов, ему удовлетворяющих) прожила недолго. В 1901 году Бертран Рассел обнаружил в ней противоречие — знаменитый парадокс о множестве всех множеств, которые не содержат себя в качестве элемента: содержит ли оно само себя? Любой ответ ведёт к противоречию. Парадокс заставил математиков переписать основания заново, уже с ограничениями на то, какие «множества» разрешены. Итогом стала аксиоматика Эрнста Цермело и Абрахама Френкеля (система ZFC, 1908–1922 годы), которая до сих пор служит стандартным фундаментом математики. Именно на этом фундаменте — уже без парадоксов — и строится всё, что мы разберём в этом уроке.

Мощность множества: как сравнивать бесконечности

Интуиция: считать без счёта

Представь, что ты не умеешь считать, но в зале стоят стулья и заходят зрители. Как узнать, хватит ли стульев, не пересчитывая ни то, ни другое? Очень просто: рассадить зрителей по одному на стул. Если каждому досталось ровно по одному месту и свободных стульев не осталось — зрителей и стульев поровну. Этот трюк — сопоставление «один к одному» — работает и для конечных, и для бесконечных множеств, и оказывается единственным разумным способом сравнивать бесконечности, потому что «пересчитать» их напрямую нельзя.

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

Определение: Множества $A$ и $B$ называются равномощными ($|A| = |B|$), если между ними существует биекция $f: A \to B$ — функция, которая одновременно инъективна (разным элементам $A$ соответствуют разные элементы $B$) и сюръективна (каждый элемент $B$ является образом какого-то элемента $A$). Множество называется конечным, если оно равномощно $\{1, 2, \dots, n\}$ при некотором $n \in \mathbb{N}$ (или пусто), и бесконечным в противном случае.

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

Пример 1 (лёгкий). Множества $A = \{1, 2, 3\}$ и $B = \{\text{кот}, \text{пёс}, \text{хомяк}\}$ равномощны: биекция $1 \mapsto \text{кот}$, $2 \mapsto \text{пёс}$, $3 \mapsto \text{хомяк}$ сопоставляет каждому элементу ровно одного партнёра. Для конечных множеств это просто означает «в них поровну элементов», и здесь по три с каждой стороны.

Пример 2 (средний). Натуральные числа $\mathbb{N} = \{1, 2, 3, \dots\}$ и чётные натуральные числа $E = \{2, 4, 6, \dots\}$ равномощны, хотя $E$ — собственное подмножество $\mathbb{N}$. Биекция задаётся формулой $f(n) = 2n$: каждому натуральному $n$ соответствует ровно одно чётное число $2n$, и каждое чётное число получается ровно из одного $n$. Значит, «чётных чисел» ровно столько же, сколько «всех натуральных» — при том, что интуитивно кажется, будто чётных вдвое меньше. Это и есть парадокс Галилея, замеченный ещё в XVII веке и получивший строгое объяснение только у Кантора.

Пример 3 (сложный). Открытый интервал $(0, 1)$ равномощен всей числовой прямой $\mathbb{R}$. Биекцию даёт, например, функция $f(x) = \tan\left(\pi x - \dfrac{\pi}{2}\right)$: она непрерывно и монотонно растягивает интервал $(0,1)$ на всю прямую, каждому $x \in (0,1)$ сопоставляя ровно одно значение из $\mathbb{R}$, и наоборот. Значит, «отрезок конечной длины» и «вся бесконечная прямая» содержат ровно одинаковое количество точек — ещё один результат, который в XIX веке шокировал даже самого Кантора: в письме к Дедекинду 1877 года он написал «Я вижу это, но не верю в это».

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

Счётные множества: первая бесконечность

Интуиция: гостиница Гильберта

Представь отель с бесконечным числом занятых номеров, куда приезжает ещё один гость. Кажется, что мест нет. Но администратор просит каждого постояльца переехать из номера $n$ в номер $n+1$ — и номер 1 освобождается для нового гостя. Более того, в такой отель можно заселить сразу бесконечно много новых гостей: постояльца из номера $n$ переселить в номер $2n$, и все нечётные номера освобождаются. Это мысленный эксперимент Гильберта, и он иллюстрирует главное свойство счётной бесконечности: её элементы можно перенумеровать, выстроить в один бесконечный список без пропусков.

Определение: Множество $A$ называется счётным, если оно конечно или равномощно множеству натуральных чисел $\mathbb{N}$ (то есть его элементы можно перенумеровать: $A = \{a_1, a_2, a_3, \dots\}$). Мощность бесконечного счётного множества обозначают $\aleph_0$ («алеф-ноль») — это наименьшая бесконечная мощность. Множество, которое бесконечно, но не счётно, называется несчётным.

Пример 1 (лёгкий). $\mathbb{N}$ счётно тривиально — это его собственное определение, нумерация $a_n = n$.

Пример 2 (средний). Множество целых чисел $\mathbb{Z} = \{\dots, -2, -1, 0, 1, 2, \dots\}$ счётно, хотя интуитивно кажется вдвое (даже «в два раза плюс единица») больше $\mathbb{N}$. Нумерация зигзагом: $a_1 = 0$, $a_2 = 1$, $a_3 = -1$, $a_4 = 2$, $a_5 = -2, \dots$ — формула $a_n = \dfrac{(-1)^n \lceil n/2 \rceil}{1}$ даёт explicit-биекцию $\mathbb{N} \to \mathbb{Z}$. Каждое целое число рано или поздно встретится в этом списке ровно один раз.

Пример 3 (сложный). Множество рациональных чисел $\mathbb{Q}$ счётно — результат, который на первый взгляд кажется невозможным: между любыми двумя рациональными числами есть ещё бесконечно много рациональных, а между двумя натуральными зазор фиксирован. Тем не менее счётность доказывается диагональным перебором Кантора: расположи положительные дроби $p/q$ в бесконечную таблицу, где строка — числитель, столбец — знаменатель, и обходи таблицу по диагоналям ($1/1$; затем $2/1, 1/2$; затем $3/1, 2/2, 1/3$; и так далее), пропуская дроби, которые уже встречались в несократимом виде. Каждая положительная рациональная дробь стоит на своей диагонали на конечном расстоянии от начала, значит рано или поздно будет пронумерована. Добавив ноль и отрицательные дроби тем же зигзагом, что и для $\mathbb{Z}$, получаем нумерацию всего $\mathbb{Q}$.

Почему это важно: счётность — это не «маленькая» бесконечность в бытовом смысле, а очень щедрый класс. Объединение счётного числа счётных множеств — снова счётно, декартово произведение двух счётных множеств — счётно. В машинном обучении именно на счётности $\mathbb{N}$ и $\mathbb{Z}$ держится дискретное вероятностное пространство: вероятности исходов можно перечислить и просуммировать в ряд $\sum_i p_i = 1$. Как только пространство исходов становится несчётным (например, непрерывная случайная величина на отрезке), суммы заменяются интегралами плотности — и это принципиальная, а не техническая разница.

Несчётные множества: диагональный аргумент Кантора

Интуиция: список, который нельзя составить полностью

Диагональный аргумент — это доказательство от противного с очень изящной конструкцией. Представь, что кто-то утверждает, будто у него есть полный пронумерованный список всех действительных чисел из интервала $(0,1)$, записанных бесконечными десятичными дробями. Задача — построить число из этого же интервала, которого в списке точно нет, тем самым опровергнув полноту списка.

Строится оно так: берём первую цифру после запятой у первого числа списка и меняем её на любую другую (например, если это $1$, ставим $2$, иначе ставим $1$) — это первая цифра нового числа. Берём вторую цифру у второго числа списка, тоже меняем — это вторая цифра нового. И так для каждого $n$-го числа списка меняем его $n$-ю цифру. Полученное число отличается от первого числа списка минимум в первом знаке, от второго — минимум во втором, и вообще от $n$-го числа списка — минимум в $n$-м знаке. Значит, оно не совпадает ни с одним числом списка, хотя само лежит в $(0,1)$. Список был неполным — а он был взят произвольным, значит полного списка не существует в принципе.

Определение: Множество называется несчётным, если оно бесконечно, но не равномощно $\mathbb{N}$ — то есть его элементы принципиально нельзя перенумеровать одним бесконечным списком. Мощность множества $\mathbb{R}$ называют мощностью континуума и обозначают $\mathfrak{c}$ или $2^{\aleph_0}$.

Пример 1 (лёгкий, интуитивный). Формальная теорема Кантора (1891): интервал $(0,1)$ несчётен. Доказательство — ровно диагональный аргумент выше: для любой попытки перенумеровать все числа интервала строится число, отсутствующее в списке. Значит, биекции $\mathbb{N} \to (0,1)$ не существует.

Пример 2 (средний). Раз $(0,1)$ и $\mathbb{R}$ равномощны (мы это уже видели через функцию тангенса), то $\mathbb{R}$ тоже несчётно. Значит, $\mathfrak{c} > \aleph_0$ — континуум строго больше счётной мощности, и это первая известная в математике пара бесконечностей разного размера.

Пример 3 (сложный, обобщение). Та же идея работает не только для чисел. Рассмотрим множество всех бесконечных последовательностей из нулей и единиц (например, все бесконечные результаты подбрасывания монетки). Предположим, что их можно перенумеровать: $s_1, s_2, s_3, \dots$ Построим новую последовательность $t$, где $n$-й бит равен $1$, если $n$-й бит $s_n$ равен $0$, и наоборот. Тогда $t$ отличается от каждой $s_n$ ровно в позиции $n$, значит $t$ не входит в список. Список опять неполный, и множество всех бинарных последовательностей несчётно. Именно на этой версии диагонального аргумента строится знаменитая теорема Кантора: для любого множества $A$ мощность его булеана $\mathcal{P}(A)$ (множества всех подмножеств) строго больше мощности $A$ самого — $|\mathcal{P}(A)| > |A|$. Отсюда следует, что бесконечностей не просто две, а бесконечно много: $\aleph_0 < |\mathcal{P}(\mathbb{N})| < |\mathcal{P}(\mathcal{P}(\mathbb{N}))| < \dots$

Почему это важно: различие счётного и несчётного — не философская тонкость, а рабочий инструмент. В теории вероятностей дискретная случайная величина (число успехов, номер класса) живёт на счётном пространстве исходов, а непрерывная (время ожидания, координата) — на несчётном; отсюда разные формулы (сумма против интеграла) и разное определение плотности. В теории вычислимости множество всех возможных программ счётно (это конечные строки символов), а множество всех функций $\mathbb{N} \to \{0,1\}$ несчётно — значит, «почти все» функции принципиально невычислимы никаким алгоритмом, просто потому что программ на них не хватает.

Строгие операции над множествами

Интуиция: от картинок к формулам

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

Определение. Пусть $A$ и $B$ — подмножества некоторого универсума $U$. Тогда:

$$A \cup B = \{x \mid x \in A \text{ или } x \in B\} \quad \text{(объединение)}$$

$$A \cap B = \{x \mid x \in A \text{ и } x \in B\} \quad \text{(пересечение)}$$

$$A \setminus B = \{x \mid x \in A \text{ и } x \notin B\} \quad \text{(разность)}$$

$$A \triangle B = (A \setminus B) \cup (B \setminus A) = \{x \mid x \text{ принадлежит ровно одному из } A, B\} \quad \text{(симметрическая разность)}$$

Дополнение $A^c = U \setminus A$ — это всё, что не входит в $A$, в пределах универсума $U$.

Каждая формула читается буквально: «$x$ принадлежит $A \cup B$ тогда и только тогда, когда $x$ принадлежит $A$ или принадлежит $B$». Именно эта запись «$x \in \dots \iff \dots$» — рабочий инструмент для любого доказательства про множества: чтобы показать, что два множества равны, достаточно показать, что у них одинаковое условие принадлежности элемента.

Пример 1 (лёгкий). Пусть $A = \{1, 2, 3, 4\}$, $B = \{3, 4, 5, 6\}$, универсум $U = \{1, \dots, 8\}$. Тогда:

• $A \cup B = \{1, 2, 3, 4, 5, 6\}$;

• $A \cap B = \{3, 4\}$;

• $A \setminus B = \{1, 2\}$ (то, что есть только в $A$);

• $A \triangle B = \{1, 2, 5, 6\}$ (то, что есть ровно в одном из множеств);

• $A^c = \{5, 6, 7, 8\}$.

Пример 2 (средний, база данных). Таблица users_tech содержит ID пользователей, смотревших техвидео: $A = \{101, 102, 103, 104\}$. Таблица users_games содержит ID смотревших игровые стримы: $B = \{103, 104, 105, 106\}$. Аналитик хочет найти «геймеров-программистов» (смотрят и то, и то) и отдельно «чистую» техническую аудиторию (смотрит только техвидео, стримы — никогда). Первое — это $A \cap B = \{103, 104\}$, ровно операция INNER JOIN по ID. Второе — это $A \setminus B = \{101, 102\}$, ровно WHERE id NOT IN (SELECT id FROM users_games). А $A \triangle B = \{101, 102, 105, 106\}$ — это «одноплановые» зрители, интересующиеся только одной темой из двух.

Пример 3 (сложный, тождество). Докажем тождество $A \setminus (B \cup C) = (A \setminus B) \cap (A \setminus C)$ методом «элемент слева тогда и только тогда, когда элемент справа», без единой картинки. Возьмём произвольный $x$.

По логическому закону де Моргана для высказываний $\text{не}(P \text{ или } Q) \iff (\text{не } P) \text{ и } (\text{не } Q)$, продолжаем:

Цепочка равносильностей ведёт слева направо и справа налево одновременно, значит множества совпадают поэлементно — а это и есть определение равенства множеств.

Почему это важно: как только операции определены через принадлежность элемента, а не через рисунок, ими можно оперировать формально в коде и в доказательствах — фильтр df[(df.age > 18) & (df.city == "Moscow")] в pandas — это буквально пересечение двух множеств строк, а ~mask — дополнение.

Декартово произведение

Интуиция: все возможные пары

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

Определение: Декартовым произведением множеств $A$ и $B$ называется множество всех упорядоченных пар

$$A \times B = \{(a, b) \mid a \in A, \ b \in B\}.$$

Пары упорядочены: $(a, b) \ne (b, a)$ при $a \ne b$. Для конечных множеств $|A \times B| = |A| \cdot |B|$.

Пример 1 (лёгкий). $A = \{1, 2\}$, $B = \{x, y, z\}$. Тогда $A \times B = \{(1,x), (1,y), (1,z), (2,x), (2,y), (2,z)\}$ — шесть пар, ровно $2 \cdot 3$.

Пример 2 (средний). Стандартная координатная плоскость $\mathbb{R}^2 = \mathbb{R} \times \mathbb{R}$ — это декартово произведение прямой самой на себя: каждая точка плоскости — упорядоченная пара координат $(x, y)$. Игральная кость и монетка вместе образуют пространство исходов $\{1,\dots,6\} \times \{\text{орёл}, \text{решка}\}$ из 12 элементов — на нём и строится равномерное распределение вероятностей для совместного броска.

Пример 3 (сложный, ML). Таблица признаков в машинном обучении — это подмножество декартова произведения областей значений всех признаков. Если признак «возраст» принимает значения из $A \subset \mathbb{N}$, признак «доход» — из $B \subset \mathbb{R}_{\ge 0}$, а признак «город» — из конечного множества $C = \{\text{Москва}, \text{Питер}, \dots\}$, то каждая строка датасета — это элемент $A \times B \times C$, а весь датасет — некоторое подмножество этого произведения (не все комбинации реально встречаются). Ровно так же операция pd.merge с параметром how="cross" буквально строит декартово произведение двух таблиц: каждая строка первой соединяется с каждой строкой второй, и число результирующих строк равно произведению количества строк.

Почему это важно: декартово произведение — это математический фундамент реляционных баз данных (декартово произведение таблиц лежит в основе любого JOIN — сначала строится полное произведение, а потом к нему применяется условие-фильтр, то есть пересечение с диагональю совпадающих ключей) и фундамент понятия «признакового пространства» в ML: вектор признаков объекта — это точка в декартовом произведении областей определения всех признаков.

Законы де Моргана для множеств

Интуиция: дополнение переворачивает союзы

Закон де Моргана для логики говорит: отрицание «$P$ или $Q$» равносильно «не $P$ и не $Q$». Для множеств происходит буквально то же самое, только вместо логического отрицания — дополнение до универсума, а вместо «или»/«и» — объединение и пересечение. Интуиция простая: «не входит хотя бы в одно из объединения» значит «не входит ни в одно из них по отдельности».

Определение (законы де Моргана): Для любых подмножеств $A, B$ универсума $U$:

$$(A \cup B)^c = A^c \cap B^c, \qquad (A \cap B)^c = A^c \cup B^c.$$

Пример 1 (лёгкий, проверка на числах). $U = \{1,\dots,10\}$, $A = \{1,2,3,4\}$, $B = \{3,4,5,6\}$. Тогда $A \cup B = \{1,2,3,4,5,6\}$, а $(A \cup B)^c = \{7,8,9,10\}$. С другой стороны, $A^c = \{5,6,7,8,9,10\}$, $B^c = \{1,2,7,8,9,10\}$, и $A^c \cap B^c = \{7,8,9,10\}$. Совпало.

Пример 2 (средний, доказательство). Докажем $(A \cap B)^c = A^c \cup B^c$ поэлементно.

Третий переход — это в точности логический закон де Моргана, применённый к высказываниям «$x \in A$» и «$x \in B$». Цепочка равносильна в обе стороны, значит множества равны.

Пример 3 (сложный, применение к запросам). В базе данных пользователей нужно найти всех, кто не является одновременно «активным» ($A$) и «платящим» ($B$) — то есть выборку $(A \cap B)^c$. По закону де Моргана это то же самое, что $A^c \cup B^c$: неактивные ИЛИ неплатящие. На SQL первая формулировка — WHERE NOT (active AND paying), вторая — WHERE NOT active OR NOT paying; современный оптимизатор запросов их равносильность знает и использует, но человеку при отладке фильтра часто проще мыслить в терминах правой части — она разбивается на два независимых условия, каждое из которых легко проверить отдельно. То же самое происходит и в pandas: ~(mask_a & mask_b) эквивалентно ~mask_a | ~mask_b.

Почему это важно: законы де Моргана — это не разовый трюк, а способ упрощать любое отрицание составного условия — в коде, в логике программ, в написании SQL-фильтров и в доказательствах теорем. Умение автоматически «раскрывать» отрицание объединения и пересечения экономит время на любом уровне, от школьной задачи до код-ревью.

Отношения на множестве: рефлексивность, симметричность, транзитивность

Интуиция: связи между элементами как множество пар

Отношение — это способ сказать, что некоторые элементы множества связаны друг с другом определённым образом: «$a$ меньше $b$», «$a$ друг $b$», «$a$ делится на $b$». Формально удобнее всего описать отношение не словами, а как множество тех пар, для которых утверждение верно, — тогда отношение становится просто подмножеством декартова произведения, а значит, к нему применимы все уже разобранные операции над множествами.

Определение: Бинарным отношением на множестве $A$ называется любое подмножество $R \subseteq A \times A$. Вместо $(a,b) \in R$ обычно пишут $a \mathrel{R} b$. Отношение называется: — рефлексивным, если $a \mathrel{R} a$ для любого $a \in A$; — симметричным, если из $a \mathrel{R} b$ всегда следует $b \mathrel{R} a$; — транзитивным, если из $a \mathrel{R} b$ и $b \mathrel{R} c$ всегда следует $a \mathrel{R} c$.

Пример 1 (лёгкий). Отношение $\le$ на $\mathbb{R}$: рефлексивно ($a \le a$ всегда), не симметрично ($2 \le 3$, но неверно $3 \le 2$), транзитивно (из $a \le b$ и $b \le c$ следует $a \le c$).

Пример 2 (средний). Отношение «$a$ и $b$ учатся в одной школе» на множестве всех школьников: рефлексивно (каждый учится в своей школе вместе с собой), симметрично (если $a$ учится в одной школе с $b$, то и $b$ — с $a$), транзитивно (если $a$ и $b$ в одной школе, и $b$ и $c$ в одной школе, то и $a$ с $c$ — в одной). Все три свойства выполнены сразу — и, забегая вперёд, это не случайность: такое отношение является отношением эквивалентности.

Пример 3 (сложный, контрпример на транзитивность). Отношение «$a$ знаком с $b$» на множестве людей: рефлексивность спорна по договорённости (обычно не считают, что человек «знаком сам с собой», значит нерефлексивно), симметрично на практике (если ты знаком с человеком, обычно и он знаком с тобой — хотя в жизни бывают знаменитости, знающие о фанатах, а не наоборот, так что строго это допущение), но не транзитивно: то, что $a$ знаком с $b$, а $b$ знаком с $c$, вовсе не означает, что $a$ знаком с $c$ — у $b$ может быть два круга знакомых, которые никогда не пересекались. Это стандартный контрпример, показывающий, что транзитивность — самое хрупкое из трёх свойств и требует отдельной проверки, а не «здравого смысла».

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

Отношения эквивалентности и разбиения

Интуиция: группировка «похожих» элементов

Когда отношение одновременно рефлексивно, симметрично и транзитивно, оно перестаёт быть просто связью между парами и начинает вести себя как обобщение равенства: оно аккуратно делит всё множество на непересекающиеся группы, внутри которых все элементы «эквивалентны» друг другу, а между группами — нет. Это ровно то, что интуитивно происходит при кластеризации данных: правило «объект $a$ похож на объект $b$» задаёт отношение, и если оно устроено как эквивалентность, датасет распадается на чистые, непересекающиеся кластеры.

Определение: Отношение $R$ на множестве $A$ называется отношением эквивалентности, если оно рефлексивно, симметрично и транзитивно. Для $a \in A$ классом эквивалентности элемента $a$ называется множество $[a] = \{x \in A \mid x \mathrel{R} a\}$. Разбиением множества $A$ называется набор непустых попарно непересекающихся подмножеств, объединение которых равно $A$.

Теорема (фундаментальная связь): классы эквивалентности любого отношения эквивалентности на $A$ образуют разбиение $A$; и наоборот, по любому разбиению $A$ можно построить отношение эквивалентности («лежать в одном блоке разбиения»), классы которого совпадают с блоками этого разбиения.

Пример 1 (лёгкий). Отношение «иметь одинаковый остаток от деления на 3» на $\mathbb{Z}$ — классический пример сравнения по модулю: $a \equiv b \pmod 3$. Рефлексивность: остаток $a$ равен остатку $a$. Симметричность: если у $a$ и $b$ одинаковый остаток, то и у $b$ с $a$. Транзитивность: если остаток $a$ равен остатку $b$, а остаток $b$ равен остатку $c$, то остаток $a$ равен остатку $c$. Классы эквивалентности: $[0] = \{\dots, -3, 0, 3, 6, \dots\}$, $[1] = \{\dots, -2, 1, 4, 7, \dots\}$, $[2] = \{\dots, -1, 2, 5, 8, \dots\}$. Эти три класса не пересекаются и в объединении дают всё $\mathbb{Z}$ — идеальное разбиение на три части.

Пример 2 (средний, проверка не-эквивалентности). Рассмотрим отношение «$a$ и $b$ — друзья в соцсети» на множестве пользователей. Рефлексивность и симметричность обычно выполняются по устройству платформы (кто-то договорился считать пользователя другом самому себе, а дружба взаимна по определению кнопки «добавить в друзья»). Но транзитивность не выполняется: у Аси есть друг Борис, у Бориса — друг Виктор, но Ася с Виктором могут быть вообще не знакомы. Значит, «дружба» — не отношение эквивалентности, и группировать пользователей в чистые непересекающиеся кластеры по этому правилу напрямую нельзя: получится не разбиение, а пересекающийся граф сообществ, для которого нужны другие алгоритмы (например, поиск сообществ в графах, а не классы эквивалентности).

Пример 3 (сложный, ML-кластеризация). Пусть на множестве объектов датасета задано отношение «$a \sim b$, если расстояние между их векторами признаков строго меньше порога $\varepsilon$ и это отношение достроено до транзитивного замыкания» (то есть $a \sim c$, если существует цепочка $a \sim x_1 \sim x_2 \sim \dots \sim c$ с шагами меньше $\varepsilon$). Такая конструкция рефлексивна (расстояние объекта до себя — ноль), симметрична (расстояние симметрично: $d(a,b) = d(b,a)$) и транзитивна по построению — это ровно то, как работает агломеративная кластеризация по связным компонентам (single linkage): объекты, соединённые цепочкой близких соседей, попадают в один класс эквивалентности, то есть в один кластер, и кластеры не пересекаются по построению. Важная тонкость: если бы отношение осталось просто «$d(a,b) < \varepsilon$» без транзитивного замыкания, оно было бы рефлексивным и симметричным, но не транзитивным (как в примере с дружбой) — именно поэтому наивная кластеризация «по прямому порогу» без замыкания не гарантирует чистого разбиения, а склеивание в цепочку («chaining effect») — известная особенность single linkage.

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

Практика: 30 заданий

Базовые задания (1–10)

Задание 1: Постройте явную биекцию между $\mathbb{N} = \{1,2,3,\dots\}$ и множеством натуральных чисел, кратных пяти, $F = \{5, 10, 15, \dots\}$. Равномощны ли эти множества?

Задание 2: Даны множества $A = \{2,4,6,8,10\}$ и $B = \{4,8,12,16\}$, универсум $U = \{1,2,\dots,16\}$. Найдите $A \cup B$, $A \cap B$, $A \setminus B$, $A \triangle B$.

Задание 3: Дано отношение $R$ на множестве $\{1,2,3\}$: $R = \{(1,1), (2,2), (3,3), (1,2), (2,1)\}$. Проверьте его на рефлексивность, симметричность и транзитивность.

Задание 4: Найдите декартово произведение $A \times B$, если $A = \{a, b\}$, $B = \{1, 2, 3\}$. Сколько в нём элементов?

Задание 5: Используя законы де Моргана, упростите отрицание условия «$x > 5$ или $x < -5$» без слова «не» перед скобкой.

Задание 6: На множестве студентов задано отношение «$a$ и $b$ сдают один и тот же набор экзаменов в эту сессию». Является ли оно отношением эквивалентности? Если да, опишите классы.

Задание 7: Определите, счётно или несчётно множество всех конечных подмножеств $\mathbb{N}$ (то есть множество $\{S \subset \mathbb{N} \mid S \text{ конечно}\}$). Обоснуйте на уровне идеи.

Задание 8: Пусть $A$ — множество студентов, изучающих Python, $B$ — множество студентов, изучающих R. В группе 30 студентов, $|A| = 18$, $|B| = 15$, $|A \cap B| = 8$. Сколько студентов не изучает ни один из этих языков?

Задание 9: Задано разбиение множества $A = \{1,2,3,4,5,6\}$ на блоки $\{1,2\}, \{3,4,5\}, \{6\}$. Постройте по этому разбиению отношение эквивалентности (перечислите все пары).

Задание 10: Верно ли, что $\mathbb{Z} \times \mathbb{Z}$ счётно? Кратко обоснуйте идею (без полного построения нумерации).

Средние задания (11–20)

Задание 11: Докажите методом «элемент слева тогда и только тогда, когда элемент справа», что $A \setminus (B \cap C) = (A \setminus B) \cup (A \setminus C)$.

Задание 12: В таблице пользователей есть признак is_premium (множество $P$) и признак is_active_30d (активен за последние 30 дней, множество $A$). Требуется найти пользователей, которые НЕ являются одновременно премиум и активными. Запишите результат двумя равносильными способами через операции над множествами и объясните смысл каждого.

Задание 13: На множестве $\mathbb{Z}$ задано отношение $a \mathrel{R} b \iff a - b$ делится на 4. Проверьте все три свойства и опишите классы эквивалентности.

Задание 14: Постройте биекцию, доказывающую, что множество всех целых чисел $\mathbb{Z}$ и множество всех натуральных чисел $\mathbb{N}$ равномощны, и явно посчитайте, каким натуральным числам соответствуют $-3, 0, 3$.

Задание 15: Даны множества $A = \{x \in \mathbb{R} \mid 1 \le x \le 5\}$ и $B = \{x \in \mathbb{R} \mid 3 \le x \le 8\}$. Найдите $A \cup B$, $A \cap B$, $A \triangle B$ в виде объединения интервалов.

Задание 16: На множестве $\{1,2,3,4\}$ приведите пример отношения, которое рефлексивно и транзитивно, но НЕ симметрично. Проверьте все три свойства явно.

Задание 17: Алгоритм кластеризации по правилу «$a \sim b$, если $|a - b| \le 2$» применён к множеству чисел $\{1, 2, 4, 5, 9, 10, 11\}$ без транзитивного замыкания. Проверьте, является ли это отношение транзитивным, приведя контрпример при необходимости.

Задание 18: Докажите, что если $A \subseteq B$, то $A \cap B = A$ и $A \cup B = B$.

Задание 19: Используя диагональный аргумент Кантора, объясните (на уровне идеи, без формул), почему множество всех бесконечных десятичных дробей вида $0,d_1d_2d_3\ldots$, где каждая цифра $d_i \in \{0, 1\}$ (то есть используются только 0 и 1), несчётно.

Задание 20: В интернет-магазине множество $A$ — покупатели категории «электроника», множество $B$ — покупатели категории «одежда», множество $C$ — покупатели категории «книги». Опишите словами и через операции множество покупателей, которые купили ровно одну из трёх категорий (не две, не три).

Продвинутые задания (21–30)

Задание 21: Докажите, что множество $\mathbb{Q}$ является счётным объединением счётных множеств, и на основе этого обоснуйте, почему счётное объединение счётных множеств счётно (идея доказательства).

Задание 22: Пусть $A$ — конечное множество из $n$ элементов. Докажите (или обоснуйте на уровне идеи через биекцию с двоичными строками), что $|\mathcal{P}(A)| = 2^n$, где $\mathcal{P}(A)$ — множество всех подмножеств $A$.

Задание 23: В датасете задан признак "категория товара" со значениями из конечного множества $C$ (10 категорий). Для one-hot encoding каждому товару сопоставляется вектор длины 10. Свяжите эту конструкцию с декартовым произведением и посчитайте, сколько существует различных one-hot векторов для одного товара с ровно одной категорией.

Задание 24: Докажите закон де Моргана $(A \cup B)^c = A^c \cap B^c$ для общего случая (произвольные $A, B \subseteq U$) методом двойного включения.

Задание 25: На множестве векторов признаков $\{v_1, \dots, v_6\} \subset \mathbb{R}^2$ задано отношение «$v_i \sim v_j$, если оба вектора лежат в одной и той же координатной четверти (включая границы по договорённости отнесения к ближайшей четверти)». Векторы: $v_1=(1,2)$, $v_2=(-1,3)$, $v_3=(2,-1)$, $v_4=(-2,-2)$, $v_5=(3,1)$, $v_6=(-3,4)$. Постройте классы эквивалентности.

Задание 26: Приведите пример отношения на множестве $\{1,2,3\}$, которое симметрично и транзитивно, но НЕ рефлексивно, и покажите, что оно не является отношением эквивалентности, хотя из симметричности и транзитивности иногда ошибочно "выводят" рефлексивность.

Задание 27: Используя теорему Кантора ($|\mathcal{P}(A)| > |A|$ для любого $A$), объясните, почему не существует «множества всех множеств» (свяжите с историей парадокса Рассела из вводной части урока).

Задание 28: В реляционной базе данных таблица Orders (10000 строк) и таблица Customers (2000 строк) соединяются через INNER JOIN по customer_id. Объясните операцию через декартово произведение и пересечение, и укажите, почему результат INNER JOIN не может быть больше, чем декартово произведение таблиц.

Задание 29: Даны три множества: $A$ — пользователи, поставившие лайк посту, $B$ — пользователи, оставившие комментарий, $C$ — пользователи, сделавшие репост. Известно $|A|=50$, $|B|=30$, $|C|=20$, $|A\cap B|=15$, $|A\cap C|=10$, $|B\cap C|=8$, $|A\cap B\cap C|=5$. Сколько уникальных пользователей взаимодействовало с постом хотя бы одним способом?

Задание 30: Отношение эквивалентности $R$ на множестве $A=\{1,2,\dots,12\}$ задано как «иметь одинаковый остаток от деления на 4». Постройте классы эквивалентности и проверьте, что они действительно образуют разбиение (все условия разбиения — непустота, попарная непересекаемость, объединение равно $A$).

Частые ошибки

Ошибка 1. Путают равномощность бесконечных множеств с интуитивным «столько же по размеру».

Как выглядит: «чётных чисел явно меньше, чем всех натуральных — они же составляют только половину».

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

Как правильно: для бесконечных множеств собственное подмножество вполне может быть равномощно всему множеству — это не парадокс, а определяющее свойство бесконечности (свойство Дедекинда). Единственный строгий критерий сравнения — существование биекции, а не «интуитивное чувство размера».

Ошибка 2. Считают, что раз между рациональными числами «бесконечно много» других рациональных, то $\mathbb{Q}$ обязано быть несчётным.

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

Почему возникает: путают плотность (между любыми двумя элементами есть третий) со счётностью/несчётностью — это независимые свойства.

Как правильно: $\mathbb{Q}$ плотно на прямой, но при этом счётно — диагональная нумерация Кантора перечисляет все дроби без пропусков. Плотность не мешает счётности; несчётность $\mathbb{R}$ доказывается принципиально другим инструментом — диагональным аргументом, а не плотностью.

Ошибка 3. Забывают проверять транзитивность отдельно, считая, что раз отношение «интуитивно про похожесть», оно автоматически транзитивно.

Как выглядит: «$a$ похож на $b$, $b$ похож на $c$ — значит и $a$ похож на $c$», без проверки.

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

Как правильно: всегда проверять транзитивность на конкретном контрпримере (как с дружбой или с порогом расстояния $|a-b|\le\varepsilon$) — интуитивно «похожие» отношения сплошь и рядом оказываются нетранзитивными, и тогда классов эквивалентности в строгом смысле не будет.

Ошибка 4. Путают операции $A \setminus B$ и $B \setminus A$.

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

Почему возникает: по аналогии с объединением и пересечением, которые действительно коммутативны ($A\cup B = B\cup A$), а разность — нет.

Как правильно: $A \setminus B$ — это то, что есть в $A$, но нет в $B$; $B \setminus A$ — наоборот. В общем случае $A\setminus B \ne B\setminus A$. Единственная симметричная комбинация — симметрическая разность $A \triangle B = (A\setminus B)\cup(B\setminus A)$, и её название не случайно совпадает по смыслу с «симметричной».

Ошибка 5. При использовании законов де Моргана путают, какая операция куда переходит.

Как выглядит: пишут $(A \cup B)^c = A^c \cup B^c$ вместо правильного $A^c \cap B^c$.

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

Как правильно: мнемоника — дополнение «переворачивает» союз: объединение (или) под отрицанием превращается в пересечение (и), и наоборот. Можно быстро проверить на маленьком числовом примере, как в разборе примеров: если результат не совпал на конкретных числах — формула перепутана.

Ошибка 6. Считают декартово произведение коммутативным, как объединение и пересечение.

Как выглядит: пишут $A \times B = B \times A$ без оговорок.

Почему возникает: аналогия с $A\cup B = B\cup A$.

Как правильно: $A \times B$ состоит из пар вида (элемент $A$, элемент $B$), а $B \times A$ — из пар вида (элемент $B$, элемент $A$). Даже если $|A\times B| = |B\times A|$ по числу элементов, сами множества пар различны при $A \ne B$: например, $(1, x) \in A\times B$, но $(1,x) \notin B\times A$, если $1 \notin B$ или $x \notin A$.

Ошибка 7. Полагают, что раз множество несчётно, то с ним «нельзя ничего вычислять» или что оно «сложнее» счётного во всех отношениях.

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

Почему возникает: смешение мощности с вычислительной сложностью или практической применимостью.

Как правильно: несчётность — чисто количественная характеристика («нельзя перенумеровать»), она никак не мешает работать с непрерывными случайными величинами, интегралами и вообще большей частью математического анализа — эта область как раз построена поверх несчётного множества $\mathbb{R}$.

Главное запомнить

• Мощность — это способ сравнивать «количество элементов» через биекцию: $|A|=|B|$, если между ними есть взаимно однозначное соответствие. Для бесконечных множеств собственная часть может быть равномощна целому.

• Счётное множество — конечное или равномощное $\mathbb{N}$; его элементы можно перенумеровать одним бесконечным списком. $\mathbb{N}$, $\mathbb{Z}$, $\mathbb{Q}$ счётны, несмотря на разную интуитивную «густоту».

• Несчётное множество нельзя перенумеровать: $\mathbb{R}$ — классический пример, доказываемый диагональным аргументом Кантора. Мощность $\mathbb{R}$ называют континуумом, $\mathfrak{c} = 2^{\aleph_0} > \aleph_0$.

• Диагональный аргумент — универсальная техника: предположи список, построй элемент, отличающийся от $n$-го элемента списка в $n$-й позиции, получи противоречие. Обобщается в теорему Кантора: $|\mathcal{P}(A)| > |A|$ для любого множества.

• Операции $A\cup B$, $A\cap B$, $A\setminus B$, $A\triangle B$ строго определяются через принадлежность элемента: «$x \in \dots \iff \dots$». Это позволяет доказывать тождества методом «элемент слева ⟺ элемент справа», а не рисунком.

• Декартово произведение $A\times B$ — множество упорядоченных пар, $|A\times B|=|A|\cdot|B|$, не коммутативно. Это математический язык признаковых пространств и основа операции JOIN в базах данных.

• Законы де Моргана: $(A\cup B)^c = A^c\cap B^c$, $(A\cap B)^c = A^c\cup B^c$ — дополнение переворачивает объединение в пересечение и наоборот, прямое следствие логических законов де Моргана.

• Бинарное отношение — подмножество $A\times A$. Три ключевых свойства: рефлексивность ($aRa$), симметричность ($aRb \Rightarrow bRa$), транзитивность ($aRb, bRc \Rightarrow aRc$) — каждое нужно проверять отдельно, транзитивность чаще всего нарушается.

• Отношение эквивалентности = рефлексивное + симметричное + транзитивное. Его классы эквивалентности всегда образуют разбиение множества на непустые непересекающиеся блоки, и наоборот — любое разбиение задаёт отношение эквивалентности. Это в точности формализация идеи «чистой» кластеризации.

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

Связь с другими темами курса

Что нужно было знать до этого урока

Формально этот урок не требует специфической техники из линейной алгебры — уроки 151–175 (векторы, матрицы, определители, системы уравнений, линейные пространства, собственные векторы, евклидово пространство) дали инструментарий для вычислений, а этот урок закладывает язык, на котором формулируются определения всей дальнейшей математики: что такое функция (урок 177 определит её как специальное отношение — подмножество $A \times B$, где каждому $a$ соответствует не более одного $b$), что такое предел последовательности (через $\varepsilon$-окрестности, то есть подмножества $\mathbb{R}$), что такое непрерывность. Из школьной программы нужны только базовые представления о множествах чисел $\mathbb{N} \subset \mathbb{Z} \subset \mathbb{Q} \subset \mathbb{R}$ и элементарная логика («и», «или», «не», «тогда и только тогда»).

Что изучить дальше

Урок 177 «Функции: инъекция, сюръекция, биекция» — прямое продолжение: функция формально определяется как отношение специального вида, а инъективность и сюръективность — это в точности условия, которые в этом уроке использовались для определения биекции и равномощности, только теперь они получат отдельные названия и подробный разбор. Понимание из этого урока «биекция = взаимно однозначное соответствие» станет строгим фундаментом. Дальше по курсу — числовые последовательности (урок 178) и пределы, где счётность индексного множества $\mathbb{N}$ используется неявно на каждом шаге, а несчётность $\mathbb{R}$ стоит за самим понятием $\varepsilon$-окрестности точки на непрерывной прямой.

Где это нужно в жизни

💻 Программирование. Операции над множествами — это set() в Python (|, &, -, ^ — буквально $\cup, \cap, \setminus, \triangle$), а SQL целиком построен на теории множеств: UNION, INTERSECT, EXCEPT, JOIN (декартово произведение с фильтром), WHERE NOT (...) (законы де Моргана). Хеш-таблицы и хеш-множества с точки зрения теории — это структуры данных для эффективной проверки принадлежности элемента множеству.

🤖 ML/AI. Отношения эквивалентности и разбиения — формальная модель кластеризации: k-means, DBSCAN, иерархическая кластеризация в конечном счёте строят разбиение датасета, и качество алгоритма можно обсуждать в терминах того, насколько построенное отношение «похожести» близко к отношению эквивалентности. Счётность/несчётность различает дискретные модели (языковые модели над конечным словарём токенов — счётное пространство) и непрерывные (диффузионные модели, VAE — работают в $\mathbb{R}^n$, несчётном пространстве), что напрямую влияет на выбор функции потерь (кросс-энтропия против MSE).

📊 Data Science. Диаграммы Венна и операции над множествами — стандартный язык для описания когорт пользователей в аналитике (retention-анализ, A/B-тестирование пересекающихся групп). One-hot encoding, о котором шла речь в задачах, — это биекция между категориальным признаком и подмножеством декартова произведения бинарных векторов. Feature engineering через join таблиц — это прямое применение декартова произведения с фильтром.

🔬 Наука. В статистике вероятностное пространство строится как тройка $(\Omega, \mathcal{F}, P)$, где $\mathcal{F}$ — специальное семейство подмножеств $\Omega$ (сигма-алгебра), замкнутое относительно счётных объединений — счётность здесь не случайна, а требование самой теории меры. В теории графов классы эквивалентности задают компоненты связности.

💰 Финансы. Сегментация клиентской базы банка на непересекающиеся группы риска — практическая реализация разбиения множества; переходы между сегментами со временем моделируются марковскими цепями, где состояния — это классы некоторого отношения на признаковом пространстве клиента.

Интересные факты

• Знаменитая фраза Кантора «Я вижу это, но не верю в это» (из письма Дедекинду 1877 года) была реакцией на собственное доказательство, что отрезок и вся плоскость $\mathbb{R}^2$ равномощны — то есть точек в квадрате ровно столько же, сколько на отрезке его стороны. Результат настолько противоречил интуиции, что автор доказательства сам ему не доверял.

• Гипотеза о том, что между мощностью $\mathbb{N}$ и мощностью $\mathbb{R}$ нет никакой промежуточной бесконечности (континуум-гипотеза), сформулированная Кантором в 1878 году, не была доказана или опровергнута почти столетие. В 1940 году Курт Гёдель показал, что её нельзя опровергнуть средствами стандартной аксиоматики ZFC, а в 1963 году Пол Коэн показал, что её нельзя и доказать — то есть в рамках общепринятых аксиом теории множеств у этого вопроса просто нет ответа, это независимое от аксиом утверждение.

• Диагональный аргумент Кантора — не изолированный трюк, а прародитель целого семейства доказательств «от противного через самоприменимость»: теорема Гёделя о неполноте (1931), проблема остановки Тьюринга (1936, недоказуемость существования универсального алгоритма-детектора зацикливания) и парадокс Рассела используют структурно одну и ту же идею — построить объект, который по конструкции обязан отличаться от каждого элемента предполагаемого полного списка.

• Кронекер, главный противник теории множеств Кантора при жизни последнего, придерживался финитизма — считал законными только объекты, строящиеся из натуральных чисел за конечное число шагов. Его знаменитая фраза «Бог создал натуральные числа, всё остальное — дело рук человека» отражает эту позицию. Именно многолетняя научная и личная травля со стороны Кронекера считается одной из причин тяжёлых депрессий, которыми Кантор страдал в последние десятилетия жизни.

Лайфхаки и полезные трюки

1. Чтобы доказать равномощность, не обязательно писать формулу биекции целиком — достаточно явно описать правило и проверить на паре примеров, что оно не даёт совпадений и не пропускает элементы. Формальная запись нужна только там, где интуитивно неочевидно, что правило действительно взаимно однозначно (как в зигзаг-нумерации $\mathbb{Z}$).

2. Быстрая проверка тождества с множествами — подставить маленькие конкретные множества. Прежде чем доказывать тождество формально методом двойного включения, проверь его на паре чисел, как в разборе законов де Моргана. Если тождество неверно, конкретный пример вскроет это за 30 секунд и сэкономит время на ошибочном доказательстве.

3. Мнемоника для законов де Моргана: «дополнение переворачивает союз». Объединение под чертой отрицания становится пересечением, пересечение — объединением. Если сомневаешься, распиши через принадлежность элемента буквально по определению — цепочка «$x \in \dots \iff \dots$» никогда не подведёт.

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

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

6. Для подсчёта $|A\cup B\cup C|$ используй формулу включений-исключений, а не пытайся считать «на глаз». Знаки чередуются: сложить одиночные множества, вычесть все попарные пересечения, прибавить тройное пересечение. Ошибка в знаке — самая частая причина неверного ответа в задачах на объединение трёх множеств.

7. При работе с pandas/SQL переводи текстовое условие фильтра сначала на язык множеств, а потом в код. «Пользователи, которые НЕ являются одновременно X и Y» — это $(X\cap Y)^c$, а по закону де Моргана это же $X^c \cup Y^c$ — вторая форма почти всегда проще и быстрее реализуется как ~mask_x | ~mask_y.

Теория множеств, о которой шёл разговор в этом уроке, — это не отдельная тема среди прочих, а грамматика, на которой написан весь дальнейший курс. Функция, предел, непрерывность, вероятностное пространство — за каждым из этих понятий стоит операция над множествами или отношение с конкретными свойствами, и после этого урока их формальные определения перестанут быть чёрным ящиком. А диагональный аргумент, с которым ты только что познакомился, ещё не раз всплывёт — под разными масками, но с одной и той же идеей — в теоремах о неразрешимости, о неполноте и о границах вычислимости. Следующий шаг — сделать функции, упомянутые здесь мимоходом как частный случай отношения, полноценным объектом изучения: это тема урока 177.