Теория множеств

Множество — коллекция различных объектов, рассматриваемых как единое целое. Объекты называются элементами. Запись: A = {1, 2, 3} означает "множество A содержит числа 1, 2, 3".

Что общего у {яблоко, стул, теорема Пифагора}? Все три — элементы одного множества. Звучит тривиально, но Георг Кантор в 1874 году показал: из этой простоты вырастает вся математика. И бесконечностей оказалось бесконечно много — одни больше других.

Почему коллекции объектов взорвали математику

До Кантора бесконечность была философским понятием. Аристотель запрещал актуальную бесконечность — только потенциальная (можно добавлять элементы бесконечно). Но Кантор в 1874 году доказал: натуральных чисел {1, 2, 3, ...} столько же, сколько чётных {2, 4, 6, ...} — биекция (взаимно однозначное соответствие) n ↔ 2n.

Затем шок: действительных чисел (отрезок [0,1]) БОЛЬШЕ, чем натуральных. Диагональный метод Кантора (1891): предположим, все действительные из [0,1] перенумерованы. Построим число, отличающееся от каждого в n-м знаке — получили число, не вошедшее в список. Противоречие — континуум несчётен.

На практике теория множеств стала языком математики. Функция — множество пар (x, y). Отношение — подмножество декартова произведения. Действительные числа — множество дедекиндовых сечений рациональных. Вся математика переписана через множества после работ Кантора.

Операции: как строить новые множества

Объединение A ∪ B — всё из A или B. Пример: {1,2} ∪ {2,3} = {1,2,3}. Базы данных SQL используют UNION для объединения таблиц — прямое применение операции над множествами.

Пересечение A ∩ B — только общие элементы. {1,2,3} ∩ {2,3,4} = {2,3}. Поисковые системы ищут пересечение множеств документов по каждому слову запроса — AND-логика.

Разность A \ B — из A убрать всё, что есть в B. {1,2,3} \ {2,4} = {1,3}. SQL DELETE WHERE использует разность множеств строк.

Декартово произведение A × B — все пары (a,b), где a ∈ A, b ∈ B. {1,2} × {x,y} = {(1,x), (1,y), (2,x), (2,y)}. Таблицы в реляционных БД — декартово произведение столбцов. Координатная плоскость — ℝ × ℝ.

Дополнение Ā — всё, что не в A (относительно универсального множества). В программировании: NOT-операция, инверсия битовой маски.

Парадоксы, которые чуть не убили математику

Бертран Рассел в 1901 году задал вопрос: пусть R — множество всех множеств, не содержащих себя как элемент. Содержит ли R само себя? Если да, то по определению не должно. Если нет, то должно. Логическое противоречие в основаниях математики.

Парадокс брадобрея — популярная версия: брадобрей бреет всех, кто не бреется сам. Бреет ли он себя? Любой ответ ведёт к противоречию. Это показало: наивная теория множеств Кантора ("множество — любая коллекция") противоречива.

Кризис оснований математики длился 20 лет. Решение: аксиоматическая теория множеств Цермело-Френкеля (ZFC, 1922). Вместо "множество всего" — система аксиом, запрещающая парадоксальные конструкции. Аксиома регулярности запрещает множествам содержать себя.

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

Кантор ввёл кардинальные числа — размеры бесконечных множеств. ℵ₀ (алеф-нуль) — мощность натуральных чисел. Счётные множества: целые, рациональные (дроби) — все имеют мощность ℵ₀, хотя интуитивно рациональных "больше".

Континуум (действительные числа) имеет мощность 2^(ℵ₀) = c. Это больше ℵ₀ — диагональный метод доказывает несчётность. Теорема Кантора: множество всех подмножеств A (булеан, 2^A) всегда больше самого A. Иерархия бесконечностей: ℵ₀ < c < 2^c < 2^(2^c) < ...

Гипотеза континуума: существует ли мощность между ℵ₀ и c? Кантор считал, что нет (c = ℵ₁). Гёдель (1940) и Коэн (1963) доказали: эта гипотеза независима от аксиом ZFC — нельзя ни доказать, ни опровергнуть. Математика не полна.

От абстракции к SQL и Python

Реляционные базы данных — прямая реализация теории множеств. Таблица — множество строк (кортежей). SELECT — выбор подмножества. JOIN — декартово произведение с фильтрацией. Э. Кодд в 1970 году построил реляционную модель на теоретико-множественной алгебре.

Python: set — встроенный тип. Операции: A | B (объединение), A & B (пересечение), A - B (разность), A ^ B (симметрическая разность). Проверка x in A — за O(1) через хеш-таблицу. Математическая абстракция стала типом данных.

Топология определяет непрерывность через открытые множества. Теория меры (основа вероятности) строится на σ-алгебрах множеств. Функциональный анализ изучает множества функций. Вся современная математика говорит на языке множеств.

Границы теории множеств

Не всякая коллекция — множество. Собственные классы (class) — слишком большие объекты. Класс всех множеств — не множество, иначе парадокс Рассела. В категорной теории (альтернативный фундамент математики) вообще нет множеств — только объекты и морфизмы.

Контринтуитивный факт: парадокс Банаха-Тарского (1924). Шар можно разбить на 5 кусков, переставить их и получить два шара исходного размера. Не физика — чистая теория множеств с аксиомой выбора. Доказывает: наша интуиция о бесконечных множествах ненадёжна.