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

Язык математики

Теория множеств — универсальный язык математики. Все математические объекты — числа, функции, структуры — можно определить через множества.

Джордж Кантор создал теорию множеств в 1870-х, несмотря на сопротивление консервативных математиков. Давид Гильберт назвал его теорию «раем, из которого нас никто не изгонит».

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

Объединение: 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ᶜ = U\A (U — универсум).

Законы де Моргана: (A∪B)ᶜ = Aᶜ∩Bᶜ; (A∩B)᷊ = Aᶜ∪Bᶜ.

Мощность множеств

Множества A и B равномощны, если существует биекция A → B. Конечные: |A| — число элементов. Бесконечные: сравниваем по биекции.

Счётные множества: ℕ, ℤ, ℚ (биекция с ℕ). Несчётные: ℝ, [0,1], все подмножества ℕ.

Теорема Кантора: |A| < |2^A| для любого A. Нет «наибольшего» бесконечного множества.

Континуум-гипотеза: |ℝ| = 2^{|ℕ|}. Нет кардинала между |ℕ| и |ℝ|. Независима от аксиом ZFC (Гёдель 1940, Коэн 1963).

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

A × B = {(a,b): a∈A, b∈B}. |A×B| = |A|·|B|.

Функция f: A→B — подмножество A×B такое, что для каждого a∈A ровно одна пара (a,b).

Аксиоматика: системы ZF и ZFC

Теория множеств сама нуждается в строгой аксиоматике — иначе возникают парадоксы. Парадокс Рассела: рассмотрим R = {x : x ∉ x} — «множество всех множеств, не содержащих себя». Тогда R ∈ R ⟺ R ∉ R — противоречие! Это показало, что нельзя строить «слишком большие» множества без ограничений.

Система аксиом Цермело–Френкеля (ZF) решает эту проблему. Основные аксиомы: Экстенсиональности (два множества равны, если имеют одни элементы), Пустого множества (∅ существует), Пары ({a,b} существует), Объединения (⋃A существует), Степени (2^A существует), Бесконечности (ℕ существует), Подмножества (аксиома разделения: {x∈A : φ(x)} существует для формулы φ), Замены (образ функции на множестве существует), Регулярности (нет бесконечно убывающих цепей ∈). Добавление аксиомы выбора (AC) даёт ZFC.

Аксиома выбора: Для любой коллекции непустых множеств существует функция выбора, выбирающая по одному элементу из каждого. Эквивалентные формулировки: лемма Цорна, теорема Тихонова (произведение компактов компактно), теорема о базисе (у любого векторного пространства есть базис Гамеля). Аксиома выбора необходима для большей части современной математики, но приводит к «странным» следствиям — теорема Банаха–Тарского: шар можно разбить на конечное число частей и сложить из них два шара того же размера.

Иерархия бесконечностей Кантора

Кантор показал, что существуют разные «размеры» бесконечности. Два множества равномощны (|A| = |B|), если между ними есть биекция. Алефы: ℵ₀ = |ℕ|, ℵ₁ — следующий кардинал после ℵ₀. Теорема Кантора |A| < |2^A| даёт бесконечную иерархию: |ℕ| < |2^ℕ| < |2^{2^ℕ}| < ...

Доказательство: предположим биекцию f: A → 2^A. Рассмотрим D = {a∈A : a ∉ f(a)}. Если D = f(d) для некоторого d, то d∈D ⟺ d∉f(d)=D — противоречие. Это обобщение диагонального аргумента Кантора.

Кардинал |ℝ| = 2^{ℵ₀} = c называется мощностью континуума. Гипотеза континуума утверждает, что ℵ₁ = c, то есть нет кардинала между |ℕ| и |ℝ|. Гёдель (1940) доказал непротиворечивость, Коэн (1963) — независимость от ZFC. Истинность GH — принципиально неразрешимый в ZFC вопрос.

Применения теории множеств в информатике

В программировании типы данных — это множества допустимых значений. Тип Boolean = {true, false}, тип Int — конечное подмножество ℤ, тип функции A → B соответствует B^A. Операции над типами: объединение типов (union types), пересечение (intersection types), декартово произведение (product types — структуры и кортежи).

Реляционная алгебра баз данных — прямое приложение теории множеств. Таблица — отношение (множество кортежей), SELECT — разделение, JOIN — декартово произведение с фильтром, UNION и INTERSECT — объединение и пересечение. SQL буквально реализует операции над конечными множествами.

Мощность множества и теорема Кантора

Два множества равномощны (|A|=|B|), если существует биекция между ними. Теорема Кантора: |A| < |P(A)| для любого A. Следствие: нет «наибольшего» бесконечного множества. Счётные множества: ℕ, ℤ, ℚ (все биективны друг другу). Несчётные: ℝ, P(ℕ), (0,1) — аргумент диагонали Кантора. Кардинальность ℝ обозначается 𝔠 = 2^{ℵ₀}. Гипотеза континуума: нет мощности строго между ℵ₀ и 𝔠 — независима от ZFC (Гёдель 1940, Коэн 1963).

Численный пример: диагональный аргумент Кантора

Задача: Показать, что |P({1,2,3})| > |{1,2,3}|, построив «диагональное» множество.

Шаг 1: P({1,2,3}) = {∅,{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}} — 8 элементов. |{1,2,3}|=3.

Шаг 2: Попробуем биекцию f: 1↦{1,3}, 2↦{2}, 3↦{1,2,3}. Построим D = {n∈{1,2,3}: n∉f(n)}.

Шаг 3: 1∉{1,3}? Нет (1∈{1,3}) → 1∉D. 2∉{2}? Нет (2∈{2}) → 2∉D. 3∉{1,2,3}? Нет → 3∉D. D=∅.

Шаг 4: ∅∉{f(1),f(2),f(3)}={{1,3},{2},{1,2,3}} — биекция пропустила ∅. Любые 3 элемента из P({1,2,3}) не покрывают все 8. Теорема Кантора: |P(A)|=2^{|A|}>|A| для любого A, даже бесконечного.