Теория множеств: от наивной к аксиоматической

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

Но есть и практическая, не философская причина разбираться. Множества — это модель, которая буквально реализована в вашем рантайме и вашей БД:

• set / HashSet / frozenset — структура данных, чьё поведение выведено из аксиом экстенсиональности;
• SQL — это (почти) реляционная алгебра, а реляционная алгебра — это алгебра множеств кортежей;
• система типов TypeScript построена на union/intersection типов, которые ведут себя как множества значений;
• анализ потоков данных в компиляторе — это поиск неподвижной точки на решётке множеств;
• доказательство неразрешимости проблемы остановки — это буквально диагональный аргумент Кантора 1891 года, переписанный другими буквами.

Разберёмся сначала «на пальцах», потом строго, потом посмотрим, где наивная интуиция ломается — и зачем понадобились аксиомы.

Карта территории

Часть 1. Наивная теория множеств

Определение «по Кантору»

Георг Кантор в 1895 году дал определение, которое сегодня выглядит наивно (и это официальный термин — naive set theory):

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

Формально мы работаем не с определением, а с одним отношением: x ∈ A («x принадлежит A»). Всё остальное — производное.

Три ключевых свойства, которые отличают множество от списка и от мультимножества:

1. Нет порядка. {1, 2} = {2, 1}.
2. Нет кратности. {1, 1, 2} = {1, 2}. Элемент либо есть, либо нет.
3. Экстенсиональность. Множество полностью определяется своими элементами: A = B тогда и только тогда, когда ∀x (x ∈ A ↔ x ∈ B). У множества нет «имени», «идентичности» или «истории» — только содержимое.

Экстенсиональность — это ровно то, почему в Python {1,2} == {2,1} возвращает True, а два разных объекта list с одинаковым содержимым — тоже равны по ==, но не по is. Множества по своей природе — value type, а не reference type.

# Интуиция: множество = "коробка", содержимое которой и есть его identity
print({1, 2, 3} == {3, 2, 1, 3, 3})   # True — порядок и кратность не важны
print([1, 2, 3] == [3, 2, 1])         # False — список это НЕ множество

# Мультимножество — отдельная сущность, в Python это Counter
from collections import Counter
print(Counter("mississippi"))          # Counter({'i': 4, 's': 4, 'p': 2, 'm': 1})
print(set("mississippi") == set("misp"))  # True — кратности потеряны

Способы задать множество

• Перечислением: A = {1, 2, 3}.
• Выделением (comprehension): B = { x ∈ U | P(x) } — «все x из уже существующего множества U, для которых верно P». Это тот самый set comprehension из Python, и это не совпадение: синтаксис {x for x in U if P(x)} называется set-builder notation и пришёл прямиком из математики.
• Конструкцией: булеан, объединение, произведение существующих множеств.

Обратите внимание на «из уже существующего U» — это не педантизм, а место, где ниже рванёт парадокс Рассела.

Базовые операции

Строгие определения:

A ∪ B  = { x | x ∈ A  или  x ∈ B }        объединение
A ∩ B  = { x | x ∈ A  и    x ∈ B }        пересечение
A \ B  = { x | x ∈ A  и    x ∉ B }        разность
A △ B  = (A \ B) ∪ (B \ A)                симметрическая разность
A ⊆ B  ⟺ ∀x (x ∈ A → x ∈ B)               подмножество
P(A)   = { S | S ⊆ A }                    булеан (множество всех подмножеств)
A × B  = { (a, b) | a ∈ A, b ∈ B }        декартово произведение

Алгебра множеств с операциями ∪, ∩, \ — это булева алгебра: коммутативность, ассоциативность, дистрибутивность в обе стороны, законы де Моргана (A ∪ B)ᶜ = Aᶜ ∩ Bᶜ. Ровно те же законы, что у ||, &&, ! в вашем коде, и у |, &, ~ над битмасками. Битовая маска — это и есть представление подмножества фиксированного конечного универсума; подробнее об этой структуре — в статье Дискретная математика и комбинаторика.

A = {1, 2, 3, 4}
B = {3, 4, 5}

print(A | B)   # {1, 2, 3, 4, 5}   объединение
print(A & B)   # {3, 4}            пересечение
print(A - B)   # {1, 2}            разность
print(A ^ B)   # {1, 2, 5}         симметрическая разность
print({1, 2} <= A)      # True  — подмножество
print({1, 2} < {1, 2})  # False — строгое подмножество, а тут равенство
print(A.isdisjoint({9}))# True  — пересечение пусто

# Законы де Моргана — полный перебор всех пар подмножеств универсума {0,1,2,3}
U = set(range(4))
subs = [{i for i in range(4) if m >> i & 1} for m in range(1 << 4)]
assert all((U - (X | Y)) == (U - X) & (U - Y) and
           (U - (X & Y)) == (U - X) | (U - Y) for X in subs for Y in subs)
print("законы де Моргана держатся на всех 256 парах")

Сложность. В CPython set — это открытая адресация с probing’ом; амортизированно O(1) на add/in/discard. Операции A & B и A - B работают за O(min(|A|, |B|)) и O(|A|) соответственно, A | B — за O(|A| + |B|). Память — примерно O(n), но с константой заметно хуже, чем у списка: таблица держится не плотнее ~60% заполнения, чтобы probing не деградировал. Реализация: CPython Objects/setobject.c.

Булеан и почему 2^n — это не метафора

Для конечного A с |A| = n верно |P(A)| = 2^n. Интуиция проста: подмножество — это ответ «да/нет» для каждого из n элементов, то есть функция A → {0, 1}, то есть двоичная строка длины n. Поэтому булеан ещё обозначают 2^A.

from itertools import combinations

def powerset(s):
    """Все подмножества. Время и память: O(2^n * n) — иначе никак, ответ такого размера."""
    xs = list(s)
    return [frozenset(c) for r in range(len(xs) + 1) for c in combinations(xs, r)]

print(len(powerset({1, 2, 3})))  # 8 = 2^3

# Каноничный вариант через битмаски: mask пробегает 0..2^n-1, бит i = "элемент i внутри"
def powerset_bits(xs):
    xs = list(xs)
    for mask in range(1 << len(xs)):
        yield frozenset(x for i, x in enumerate(xs) if mask >> i & 1)

Это объясняет, почему полный перебор подмножеств — O(2^n) и почему задачи вроде SUBSET-SUM тяжелы: пространство поиска — булеан. Об этом подробно в статье Теория сложности.

Всё есть множество: пары, отношения, функции

Множество не знает про порядок — но нам нужны упорядоченные пары. Их кодируют множествами. Классическая конструкция Куратовского (1921):

(a, b) := { {a}, {a, b} }

Единственное, что от неё требуется — теорема: (a, b) = (c, d) ⟺ a = c и b = d. Никакой «истинной природы» у пары нет, кодировка — деталь реализации, ровно как struct в памяти.

def pair(a, b):
    """Пара Куратовского. Реализация как frozenset множеств."""
    return frozenset([frozenset([a]), frozenset([a, b])])

print(pair(1, 2) == pair(2, 1))  # False — порядок восстановлен
print(pair(1, 2) == pair(1, 2))  # True
print(pair(1, 1))                # frozenset({frozenset({1})}) — вырожденный случай, тоже корректен

Дальше всё выстраивается по цепочке:

• Отношение R между A и B — это просто подмножество R ⊆ A × B. Запись aRb означает (a, b) ∈ R.
• Функция f: A → B — это отношение, в котором каждому a ∈ A соответствует ровно один b. То есть функция и есть свой график. Никакого «правила вычисления» в теоретико-множественном определении нет — только таблица пар (возможно, бесконечная). Именно поэтому в математике f и f', вычисляющие одно и то же разными алгоритмами, — одна и та же функция, а в программировании — два разных объекта с разной сложностью.
• Инъекция — разным входам разные выходы; сюръекция — образ покрывает всё B; биекция — и то, и другое.

# Отношение как множество пар. Композиция и транзитивное замыкание — операции над множествами.
R = {(1, 2), (2, 3), (3, 4)}

def compose(R, S):
    """R ∘ S = {(a,d) | ∃b: (a,b) ∈ R и (b,d) ∈ S}. O(|R| * |S|) наивно."""
    return {(a, d) for (a, b) in R for (c, d) in S if b == c}

def transitive_closure(R):
    """Наименьшая транзитивная надстройка. Итерация до неподвижной точки."""
    T = set(R)
    while True:
        nxt = T | compose(T, T)
        if nxt == T:
            return T
        T = nxt

print(sorted(transitive_closure(R)))
# [(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)]

Транзитивное замыкание — это уже теория графов (достижимость), см. Теория графов. Наивная версия выше — O(n^4) в худшем случае; алгоритм Флойда–Уоршелла делает то же за O(n^3).

Свойства отношений (рефлексивность, симметричность, транзитивность) дают отношения эквивалентности — а те дают фактор-множества A/~. Это математика за union-find, за нормализацией строк (casefold), за интернированием, за дедупликацией в data engineering. Отношение частичного порядка (рефлексивность + антисимметричность + транзитивность) даёт решётки — фундамент для анализа потоков данных и для теории типов.

Часть 2. Мощность: сколько бывает бесконечностей

Биекция как единица измерения

Как сравнить размеры двух бесконечных множеств, если считать элементы нельзя? Кантор предложил: |A| = |B| тогда и только тогда, когда между A и B существует биекция. Это единственное определение, которое работает и для конечных, и для бесконечных множеств, и оно даёт странные последствия.

Множество называется счётным, если его можно занумеровать натуральными числами (существует биекция с ℕ). Счётны:

• чётные числа (n ↦ 2n) — хотя это «половина» натуральных;
• целые числа ℤ (нумеруем 0, 1, −1, 2, −2, …);
• рациональные ℚ — обход таблицы p/q по диагоналям;
• множество всех конечных строк над конечным алфавитом;
• множество всех программ на любом языке — программа это конечная строка;
• объединение счётного числа счётных множеств (с оговоркой про аксиому выбора).

Мощность ℕ обозначают ℵ₀ («алеф-ноль»).

Диагональный аргумент

Теорема Кантора (1891): множество бесконечных двоичных последовательностей несчётно.

Доказательство — конструктивное и его стоит один раз проделать руками. Предположим, что мы занумеровали все последовательности: s₀, s₁, s₂, .... Построим новую последовательность d, взяв i-й бит из sᵢ и инвертировав его. Тогда d отличается от s₀ в позиции 0, от s₁ в позиции 1, … от sᵢ в позиции i. Значит d нет в списке. Противоречие: список был «всеми».

# Диагональ Кантора на конечном срезе — видно механику
seqs = ["0101010101", "1100110011", "0011001100", "1111000011", "1010101010",
        "0000111100", "1001100110", "0110011001", "1110001110", "0001110001"]

diag = "".join("1" if seqs[i][i] == "0" else "0" for i in range(len(seqs)))
print(diag)                                  # 1000001100
print(all(diag != s for s in seqs))          # True — отличается от каждой
# и отличается от seqs[i] ИМЕННО в позиции i:
print(all(diag[i] != seqs[i][i] for i in range(len(seqs))))  # True

Последний шаг — это мост к теории вычислимости. Программ счётно много (ℵ₀), функций ℕ → {0,1} несчётно много (2^ℵ₀). Значит подавляющее большинство функций невычислимо — и это доказано за одну строку, ещё до всякой машины Тьюринга. Проблема остановки и теорема Гёделя о неполноте используют ту же диагонализацию.

Теорема Кантора и башня бесконечностей

Общая форма: для любого множества A нет сюръекции A → P(A), то есть |A| < |P(A)| всегда, включая бесконечные A.

Доказательство в три строки, и оно — прямой предок парадокса Рассела. Пусть f: A → P(A) — сюръекция. Рассмотрим D = { a ∈ A | a ∉ f(a) }. Так как f сюръективна, D = f(d) для какого-то d ∈ A. Спросим: d ∈ D? Если d ∈ D, то по определению D верно d ∉ f(d) = D — противоречие. Если d ∉ D = f(d), то по определению D верно d ∈ D — тоже противоречие. Значит сюръекции нет. Следствие: ℕ, P(ℕ), P(P(ℕ)), … — бесконечная башня всё бо́льших бесконечностей.

Континуум-гипотеза (CH): нет мощности строго между ℵ₀ и 2^ℵ₀. Гёдель (1940) показал, что CH нельзя опровергнуть в ZFC, Коэн (1963, метод форсинга) — что нельзя доказать. CH независима от ZFC. Это не «мы пока не знаем» — это доказанная невозможность решить вопрос данными аксиомами, ровно как проблема остановки не «пока не решена».

Часть 3. Кризис: где наивная теория ломается

Парадокс Рассела

Наивная теория неявно принимала схему неограниченной свёртки: для любого предиката P существует множество { x | P(x) }. Рассел в 1901 году взял P(x) := x ∉ x и получил:

R = { x | x ∉ x }
R ∈ R  ⟺  R ∉ R

Это не «странный объект» — это логическое противоречие, из которого по правилу ex falso quodlibet выводится вообще всё. Наивная теория множеств оказалась не просто неудобной, а непротиворечивой быть не могла.

class NaiveSet:
    """Множество, заданное произвольным предикатом — неограниченная свёртка."""
    def __init__(self, predicate):
        self.predicate = predicate
    def __contains__(self, x):
        return self.predicate(x)

R = NaiveSet(lambda x: x not in x)        # R = { x | x ∉ x }
try:
    print(R in R)
except RecursionError:
    print("RecursionError: вопрос 'R ∈ R?' не имеет ответа")

# Ограниченная свёртка (аксиома выделения) всегда безопасна: выделяем ИЗ существующего
print({x for x in {1, 2, 3, 4, 5, 6} if x % 2 == 0})   # {2, 4, 6}

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

Рядом стоят парадоксы того же семейства. Парадокс Кантора: пусть V — множество всех множеств; тогда P(V) ⊆ V, откуда |P(V)| ≤ |V|, что противоречит теореме Кантора. Парадокс Бурали-Форти: множество всех ординалов само было бы ординалом, большим всех ординалов. Общий диагноз: «слишком большие» коллекции нельзя считать множествами. Нужно правило, которое разрешает строить множества снизу вверх и запрещает «схлопывать всё сущее в одну коробку».

Часть 4. ZFC — аксиоматическая теория множеств

Цермело (1908), затем Френкель и Сколем: вместо «множество — это что угодно» — список аксиом первого порядка в языке с единственным нелогическим символом ∈. Всё, что можно доказать из этих аксиом, есть математика; всё остальное — нет.

Аксиомы (человеческим языком)

Ключевая правка — аксиома №5. Выделение позволяет только сужать уже существующее множество, а не создавать новое из воздуха. Рассел мгновенно обезвреживается: R = { x ∈ A | x ∉ x } — совершенно легальное множество для любого A, и из него выводится не противоречие, а безобидная теорема «R ∉ A», то есть «множества всех множеств не существует».

Обратите внимание: то же самое различие есть в вашем коде. {x for x in universe if pred(x)} — всегда корректно. {x for x in <всё что угодно> if pred(x)} — не компилируется, потому что нет итератора по «всему». Питон не даёт неограниченной свёртки по той же причине, что и ZFC: не существует конечного способа проитерировать универсум.

Кумулятивная иерархия

Аксиома регулярности даёт наглядную картину устройства математического универсума: всё строится слоями снизу.

V₀     = ∅
V(α+1) = P(V(α))
V(λ)   = ⋃ V(α)   для предельного λ
V      = ⋃ V(α)   по всем ординалам

V₅ уже содержит 65536 элементов, V₆ — 2^65536. Универсум растёт непредставимо быстро, но каждое множество лежит на каком-то конечном или трансфинитном этаже, и «этажа для всего» не существует — именно поэтому V это не множество, а собственный класс.

Натуральные числа как множества

Фон Нейман закодировал числа так, что n — это множество всех меньших чисел:

0 = ∅
1 = {∅}         = {0}
2 = {∅, {∅}}    = {0, 1}
n + 1 = n ∪ {n}

Элегантность: |n| = n (у числа n ровно n элементов), а отношение «меньше» — это буквально ∈, и «≤» — это ⊆.

def von_neumann(n):
    """Ординал n по фон Нейману: n = {0, 1, ..., n-1}."""
    s = frozenset()
    for _ in range(n):
        s = s | frozenset([s])
    return s

def show(s):
    if not s:
        return "∅"
    return "{" + ", ".join(sorted((show(x) for x in s), key=lambda t: (len(t), t))) + "}"

for n in range(4):
    print(n, "=", show(von_neumann(n)))
# 0 = ∅   /   1 = {∅}   /   2 = {∅, {∅}}   /   3 = {∅, {∅}, {∅, {∅}}}

three = von_neumann(3)
print(len(three))                          # 3  — |n| = n
print(von_neumann(2) in three)             # True  — "2 < 3" это "2 ∈ 3"
print(von_neumann(2) <= three)             # True  — "2 ≤ 3" это "2 ⊆ 3"

Дальше ℤ строится как фактор ℕ×ℕ по отношению «(a,b) ~ (c,d) ⟺ a+d = b+c», ℚ — как фактор ℤ×ℤ*, ℝ — как сечения Дедекинда или классы фундаментальных последовательностей. Всё — множества. Это и есть смысл фразы «теория множеств — основание математики».

Аксиома выбора: почему из-за неё спорят

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

Аргументы «за»: без AC ломаются вещи, которые все хотят иметь — у каждого векторного пространства есть базис, произведение непустых множеств непусто, лемма Цорна (нужна в алгебре повсюду), теорема Тихонова. Аргументы «против»: AC неконструктивна — она утверждает существование объекта, не давая способа его построить. Отсюда парадокс Банаха–Тарского: шар можно разбить на 5 частей и собрать из них два таких же шара. Части неизмеримы, построить их нельзя, AC лишь утверждает, что они «есть».

Для программиста здесь важна мораль про конструктивность. В конструктивной математике (и в языках с зависимыми типами — Coq, Agda, Lean) «существует x» означает «вот программа, которая строит x». AC в такой постановке либо тривиальна, либо неверна. Это прямо связано с изоморфизмом Карри–Ховарда: тип = утверждение, программа = доказательство. Подробнее — в статьях Математическая логика и доказательства и Теория категорий: основы.

Часть 5. Где это реально всплывает в коде

SQL и реляционная алгебра

Реляционная модель Кодда (1970) — это буквально теория множеств. Отношение (таблица) — множество кортежей; кортеж — элемент декартова произведения доменов.

Схема ORDER_ITEMS — это домен int × int × int с ограничениями; сама таблица — подмножество этого произведения. JOIN — ограниченное декартово произведение с последующим выделением, внешний ключ — требование π(ORDER_ITEMS.order_id) ⊆ π(ORDERS.id).

-- Операции ЯВНО именованы по теории множеств: UNION / INTERSECT / EXCEPT (Oracle: MINUS)
SELECT product_id FROM order_items WHERE order_id = 1
UNION                 -- A ∪ B; замените на INTERSECT (A ∩ B) или EXCEPT (A \ B)
SELECT product_id FROM order_items WHERE order_id = 2;

-- UNION ALL — это НЕ объединение множеств, а конкатенация мультимножеств.
-- Практический вывод: UNION делает дедупликацию (сортировка или хеш, O(n log n)
-- времени / O(n) памяти), UNION ALL — нет. Если дубликаты невозможны — берите ALL.

Практическая ловушка: SQL-таблица на самом деле — мультимножество (bag), а не множество, потому что допускает дубликаты строк. Кодд считал это дефектом; Дейт и Дарвен посвятили этому не одну главу в The Third Manifesto. Отсюда сюрпризы вроде SELECT COUNT(*) vs COUNT(DISTINCT x) и разного поведения EXCEPT / EXCEPT ALL. См. документацию PostgreSQL по комбинированию запросов.

Системы типов

В TypeScript тип — это множество значений, а union/intersection работают как ∪ и ∩:

type A = "red" | "green";        // множество из двух значений
type B = "green" | "blue";
type U = A | B;                  // "red" | "green" | "blue"  — объединение
type I = A & B;                  // "green"                    — пересечение

type X = string | never;         // string    never — пустое множество: A ∪ ∅ = A
type Y = string & never;         // never                        A ∩ ∅ = ∅
type Z = string | unknown;       // unknown   unknown — универсум: A ∪ U = U

// Отношение подтипа — это ⊆. Присваивание разрешено вниз по включению.
let a: A = "green";
let u: U = a;                    // OK:   A ⊆ U
// let b: A = u;                 // Error: U ⊄ A

Это не аналогия, а модель: подтипирование задаёт частичный порядок, а never/unknown — нижний и верхний элемент решётки. Обратите внимание: порядок частичный, а не линейный — {1,2} и {2,3} несравнимы, и A | B не «больше» ни одного конкретного типа в смысле линейного порядка. Отсюда типичная ошибка «раз это union, компилятор выберет нужную ветку» — не выберет, нужен narrowing. Подробности про язык — в треке TypeScript.

Отдельная линия — алгебраические типы данных: struct это A × B (произведение, |A|·|B| значений), enum/sum type это A ⊔ B (дизъюнктное объединение, |A|+|B| значений), функция это B^A (|B|^|A| значений). Арифметика мощностей буквально совпадает с арифметикой типов.

Анализ потоков данных в компиляторе

Классический liveness analysis — это итерация до неподвижной точки на решётке подмножеств множества переменных. Уравнения:

live_out[b] = ⋃ live_in[s]  по всем преемникам s
live_in[b]  = use[b] ∪ (live_out[b] \ def[b])

# Граф базовых блоков: b1 -> b2 -> {b3, b1}
blocks = {
    "b1": {"use": {"a"},     "def": {"b"},  "succ": ["b2"]},
    "b2": {"use": {"b","c"}, "def": {"d"},  "succ": ["b3", "b1"]},
    "b3": {"use": {"d"},     "def": set(),  "succ": []},
}

live_in  = {k: set() for k in blocks}
live_out = {k: set() for k in blocks}

changed, iters = True, 0
while changed:                      # монотонная итерация на конечной решётке -> завершается
    changed, iters = False, iters + 1
    for k, b in blocks.items():
        out = set().union(*(live_in[s] for s in b["succ"])) if b["succ"] else set()
        inn = b["use"] | (out - b["def"])
        if out != live_out[k] or inn != live_in[k]:
            live_out[k], live_in[k], changed = out, inn, True

print(iters, {k: sorted(v) for k, v in live_in.items()})
# 3 {'b1': ['a', 'c'], 'b2': ['a', 'b', 'c'], 'b3': ['d']}

Почему цикл гарантированно завершается — это теорема Кнастера–Тарского о неподвижной точке на полной решётке. Решётка здесь — P(Vars) с порядком ⊆, высота её |Vars|, функция монотонна, значит итерация сходится не более чем за O(|Vars| · |Blocks|) шагов. Ровно та же схема — в constant propagation, reaching definitions, escape analysis. Каноническая ссылка: Nielson, Nielson, Hankin, Principles of Program Analysis.

Приближённые множества: Bloom-фильтр

Когда точное множество не помещается в память, применяют структуры с односторонней ошибкой. Bloom-фильтр отвечает на x ∈ S: «точно нет» или «возможно да».

import hashlib

class BloomFilter:
    """Приближённое множество. Ложноположительные есть, ложноотрицательных НЕТ."""
    def __init__(self, m_bits=1 << 16, k_hashes=4):
        self.m, self.k, self.bits = m_bits, k_hashes, bytearray(m_bits // 8)

    def _positions(self, item):                         # двойное хеширование
        h = hashlib.blake2b(str(item).encode(), digest_size=16).digest()
        base, step = int.from_bytes(h[:8], "big"), int.from_bytes(h[8:], "big") | 1
        return [(base + i * step) % self.m for i in range(self.k)]

    def add(self, item):                                # O(k)
        for p in self._positions(item):
            self.bits[p // 8] |= 1 << (p % 8)

    def __contains__(self, item):                       # O(k)
        return all(self.bits[p // 8] >> (p % 8) & 1 for p in self._positions(item))

bf = BloomFilter()
for w in ["alpha", "beta", "gamma"]:
    bf.add(w)
print("alpha" in bf, "delta" in bf)   # True False; вероятность FP ≈ (1 - e^(-kn/m))^k

Ключевое свойство в терминах множеств: фильтр представляет надмножество S' ⊇ S. x ∉ S' влечёт x ∉ S — этого достаточно, чтобы отсекать походы на диск в LSM-деревьях (RocksDB, Cassandra). Оригинал: Bloom, 1970, “Space/Time Trade-offs in Hash Coding”. Родственная история — CRDT-множества (G-Set, 2P-Set, OR-Set): их сходимость доказывается как свойство полурешётки — слияние это ∪, которое коммутативно, ассоциативно и идемпотентно, поэтому порядок доставки сообщений не важен (Shapiro et al.).

Типичные заблуждения

«Множество — это просто список без дубликатов». Нет: список без дубликатов сохраняет порядок и допускает индексацию. set в Python не гарантирует порядок итерации между запусками для строк (при включённом PYTHONHASHSEED), и полагаться на него — источник флаки-тестов. Если нужен порядок — берите dict.fromkeys(xs) (dict гарантирует порядок вставки с 3.7).

«in для множества всегда O(1)». Амортизированно да, но при коллизиях — до O(n). И вычисление хеша ключа само по себе стоит O(len(key)) для строк. Для миллиона длинных строк это заметно.

Хеш-ловушки, ломающие экстенсиональность:

print({1, True, 1.0, 2})     # {1, 2} — потому что hash(1)==hash(True)==hash(1.0) и они ==

nan = float("nan")
s = {nan}
print(nan in s)              # True  — сработала проверка на идентичность (x is y)
print(float("nan") in s)     # False — другой объект, а NaN != NaN

Математическое множество не знает про NaN; ваш set — знает, и это регулярно всплывает при дедупликации числовых данных.

«Множество может содержать что угодно». В Python элементы обязаны быть хешируемыми и (по контракту) неизменяемыми. {{1,2}} — ошибка, нужно {frozenset({1,2})}. Это ограничение реализации, а не математики, но нарушать его нельзя: мутация элемента ломает инвариант хеш-таблицы, и элемент «теряется» внутри контейнера.

«ZFC доказано непротиворечива». Нет. По второй теореме Гёделя ZFC не может доказать собственную непротиворечивость (если она непротиворечива). Мы работаем на доверии, подкреплённом столетием безуспешных попыток найти противоречие.

«Аксиома выбора — экзотика, меня не касается». Если вы пользуетесь тем, что у любого векторного пространства есть базис, или леммой Цорна, или теоремой Хана–Банаха — вы пользуетесь AC.

«Все бесконечности одинаковы». |ℕ| = |ℚ| < |ℝ| < |P(ℝ)| < .... Причём |ℝ| = |ℝ²| = |ℝⁿ| — размерность не влияет на мощность, что само по себе шокировало Кантора («вижу, но не верю»).

Trade-offs: какую структуру выбирать

Практический ориентир: в Python set из n int занимает примерно 32–60 байт на элемент против 8 байт на элемент в array('q'). Если вам нужен только membership по плотному диапазону целых — битовый массив выигрывает на два порядка по памяти.

Мини-итог

• Множество определяется только своими элементами (экстенсиональность). Ни порядка, ни кратности, ни идентичности.
• Всё остальное кодируется множествами: пары (Куратовский), отношения (подмножества произведения), функции (графики), числа (фон Нейман).
• Мощности сравниваются биекциями. Диагональный аргумент Кантора даёт башню бесконечностей и одновременно — доказательство существования невычислимых функций.
• Неограниченная свёртка {x | P(x)} противоречива (Рассел). ZFC заменяет её на выделение из уже существующего множества плюс явные конструкторы (Пара, Булеан, Объединение, Замещение).
• CH и AC независимы от ZF — доказано, а не «пока неизвестно».
• В инженерной практике теория множеств — это SQL, системы типов, dataflow-анализ, CRDT и вероятностные структуры данных. Знание границ модели (мультимножества, NaN, хеш-коллизии) экономит дни отладки.

Источники

Учебники. Halmos P. Naive Set Theory (1960) — 100 страниц, лучший вход (несмотря на название, излагает ZFC аккуратно). Enderton H. Elements of Set Theory — золотая середина. Jech T. Set Theory, 3rd Millennium Edition, Springer — исчерпывающая монография. Kunen K. Set Theory: An Introduction to Independence Proofs — форсинг и независимость CH. Nielson, Nielson, Hankin Principles of Program Analysis, Springer — решётки и неподвижные точки в компиляторах.

Первоисточники и онлайн

• Stanford Encyclopedia of Philosophy: Set Theory и Zermelo–Fraenkel Set Theory — детальные обзоры с историей.
• Cantor, “Über eine elementare Frage der Mannigfaltigkeitslehre” (1891) — оригинал диагонального аргумента.
• Cohen P., “The Independence of the Continuum Hypothesis” (PNAS, 1963).
• Metamath Proof Explorer — вся ZFC, формализованная и машинно проверенная, с кликабельными доказательствами от аксиом.
• Codd E.F., “A Relational Model of Data for Large Shared Data Banks” (1970) — статья, из которой вырос SQL; PostgreSQL: Combining Queries.
• CPython Objects/setobject.c и TypeScript Handbook: Everyday Types.

Что дальше

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

Смежные темы трека: Дискретная математика и комбинаторика (счёт подмножеств и комбинаторные тождества), Абстрактная алгебра (структуры поверх множеств), Теория вычислимости (диагонализация в действии). Общая карта — в обзоре трека.