Множество

Понятие множества сложилось лишь в конце XIX века, однако его предыстория восходит к античности: проблема бесконечного занимала греческих философов и математиков с самого начала. Апории Зенона Элейского («бегун», «дихотомия») показали, к каким противоречиям приводит неосторожное обращение с актуальной бесконечностью и бесконечным делением^[11]. Аристотелевская логика закрепила способы рассуждения об «общем» и «частном», которые впоследствии стали логическим каркасом теоретико-множественного языка^[12][13]; сами же греки, опасаясь актуальной бесконечности, довольствовались «потенциальной» бесконечностью в методе исчерпывания^[14].

Трудности, связанные с бесконечными совокупностями, были замечены задолго до создания теории множеств. Ещё Галилео Галилей в «Беседах о двух новых науках» (1638) отметил, что натуральных чисел столько же, сколько их квадратов, поскольку каждому числу отвечает ровно один квадрат, — хотя квадраты составляют лишь часть натурального ряда. Этот факт, получивший название парадокса Галилея, сам Галилей счёл доводом против применения понятий «больше», «меньше» и «равно» к бесконечным совокупностям^[15].

Первым, кто попытался легализовать актуальную бесконечность, стал Бернард Больцано: в посмертно изданных «Парадоксы бесконечного» (1851) он фактически определил бесконечное множество как такое, которое можно взаимно однозначно отобразить на свою собственную часть^[16][17]. Строгое арифметическое оформление эта идея получила у Дедекинда: в работе «Was sind und was sollen die Zahlen?» (1888) он определил бесконечное множество через отображение на собственную часть, а в работе 1872 года построил действительные числа «сечениями»^[18][19][20].

Собственно теория множеств создана Георгом Кантором: исходя из задач анализа (тригонометрические ряды), он ввёл производные множества, доказал счётность множества рациональных чисел и несчётность континуума, построил теорию кардинальных и порядковых чисел и сформулировал континуум-гипотезу^[21][22][23]. Переписка Кантора с Дедекиндом показывает, как формировались эти идеи, включая представление о множествах как о «многообразиях», мыслимых в виде одного объекта^[24].

Свободное образование множеств («всякое свойство определяет множество») привело к противоречиям: парадокс Бурали-Форти (1897) о множестве всех порядковых чисел^[25], «парадокс множества всех множеств», отмеченный самим Кантором в письме к Дедекинду (1899)^[26], парадокс Ришара (1905), связанный с определимостью^[27], и, наконец, парадокс Рассела, проанализированный в «Principia Mathematica»^[28][29]. Эти антиномии вызвали «кризис оснований» и заставили пересмотреть основания теории множеств^[30].

Первую аксиоматизацию дал Цермело (1908), одновременно доказавший (1904) с помощью аксиомы выбора теорему о вполне упорядочении любого множества^[31][32]; система была уточнена Френкелем (1922) и Сколемом (1922), что привело к системе ZF^[33][34], и независимо — фон Нейманом, различившим «множества» и «классы»^[35][36]. Параллельно развивались иные подходы: интуиционизм Брауэра, отвергавший часть классической логики^[37][38], и гильбертовская программа метаматематики^[39], завершившаяся теоремами Гёделя о неполноте (1931) и о непротиворечивости аксиомы выбора и континуум-гипотезы (1940)^[40][41][42].

В XX веке теория множеств стала универсальным языком математики: на нём строятся топологические пространства^[43][44], метрические^[45][46] и функциональные пространства^[47], теория меры и интегрирования^[48][49][50]. В собственной концепции Бурбаки множество рассматривается как бесформенный «субстрат», на котором аксиоматически задаются математические структуры — алгебраические, порядковые, топологические; единство математики, по Бурбаки, состоит не в общем предмете, а в иерархии структур^[51]; метафизические псевдопроблемы о «природе» множества при этом исчезают вместе с самим наивным понятием множества^[52].

Первый способ состоит в том, чтобы выписать все элементы множества. Например, множество ${\displaystyle Y}$ неотрицательных чётных чисел, меньших 10:

${\displaystyle Y=\{0,\,2,\,4,\,6,\,8\}.}$

Перечисление применимо только к конечным множествам, причём практически удобно лишь тогда, когда элементов немного: выписать таким образом множество из тысячи элементов затруднительно, а из бесконечного числа элементов — невозможно. Для множеств с очевидной закономерностью используют сокращённую запись с многоточием, например ${\displaystyle \{1,2,\ldots ,100\}}$, однако она уже является формой описания, а не полным перечислением^[54][55].

Второй способ применяется, когда перечисление невозможно или неудобно. Множество задаётся характеристическим свойством его элементов:

${\displaystyle Y=\{x\in X\mid A(x)\},}$

что читается: «множество тех ${\displaystyle x}$ из ${\displaystyle X}$, для которых истинно ${\displaystyle A(x)}$». Указание объемлющего множества ${\displaystyle X}$ существенно: согласно схеме выделения, подмножество можно выделять только внутри заранее заданного множества — именно этим ограничением аксиоматическая теория избегает парадокса Рассела.

Например, график функции ${\displaystyle f\colon X\to Y}$ задаётся так:

${\displaystyle \Gamma =\{(x,y)\in X\times Y\mid f(x)=y\},}$

где ${\displaystyle \times }$ — декартово произведение множеств^[56][57].

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

В отличие от арифметических сложения и вычитания, для которых ${\displaystyle (a+b)-c=a+(b-c)}$, для операций над множествами это неверно. Например, при ${\displaystyle A=\{1,3\}}$, ${\displaystyle B=\{1,2\}}$, ${\displaystyle C=\{2,3\}}$ имеем ${\displaystyle (A\cup B)\setminus C=\{1\}}$, тогда как ${\displaystyle A\cup (B\setminus C)=\{1,3\}}$^[65].

• Пустое множество — множество, не содержащее ни одного элемента; обозначается ${\displaystyle \varnothing }$. Оно единственно и является подмножеством любого множества.
• Одноэлементное множество — множество, состоящее из одного элемента. Следует отличать ${\displaystyle a}$ от ${\displaystyle \{a\}}$.
• Универсальное множество (универсум) — множество, содержащее все объекты, рассматриваемые в данной задаче. «Множества всех множеств» не существует (парадокс Кантора), поэтому универсум всегда понимается относительно конкретного контекста.

• Кортеж (в частности, упорядоченная пара) — упорядоченный конечный набор объектов; элементы могут повторяться.
• Мультимножество — совокупность, в которой учитывается кратность элементов.
• Пространство — множество с дополнительной структурой.
• Вектор — элемент линейного пространства; в координатной записи — упорядоченный набор чисел.
• Последовательность — функция натурального аргумента; порядок существен, элементы могут повторяться.
• Нечёткое множество — объект, принадлежность которому задаётся не отношением, а функцией со значениями в ${\displaystyle [0,1]}$: элемент может принадлежать ему «в некоторой степени».
• Класс — совокупность, которая может быть слишком «большой», чтобы быть множеством (например, класс всех множеств).

• Система множеств — множество, элементы которого сами являются множествами.
• Алгебра множеств, кольцо множеств, сигма-алгебра — системы множеств, замкнутые относительно определённых операций.
• Булеан — множество всех подмножеств данного множества.
• Семейство множеств — индексированный аналог системы множеств.

В рамках ZFC все математические объекты строятся из множеств. Натуральные числа определяются по фон Нейману: ${\displaystyle 0=\varnothing }$, ${\displaystyle n+1=n\cup \{n\}}$, так что каждое число есть множество всех предшествующих. Упорядоченная пара определяется по Куратовскому, функция — как множество пар, отношение — как подмножество декартова произведения. Далее из натуральных чисел строятся целые, рациональные и действительные числа^[75].

Отношение эквивалентности на множестве задаёт его разбиение на непересекающиеся классы; эта конструкция лежит в основе построения фактор-групп, фактор-колец и фактор-пространств. Топология на множестве ${\displaystyle X}$ определяется как система его подмножеств, называемых открытыми и удовлетворяющих трём аксиомам^[76].

Мера определяется как функция на сигма-алгебре подмножеств, принимающая неотрицательные значения и счётно-аддитивная. Понятия длины, площади, объёма и вероятности являются частными случаями меры^[77].

До 1930-х годов теория вероятностей не имела общепринятого строгого обоснования; она входила в число задач, поставленных Д. Гильбертом в шестой проблеме (1900). Решение предложил А. Н. Колмогоров в книге «Основные понятия теории вероятностей» (1933): он заметил, что вероятность обладает теми же свойствами, что и мера в теории меры, созданной Э. Борелем и А. Лебегом, и построил теорию как раздел теории меры^[79].

Вероятностное пространство — тройка ${\displaystyle (\Omega ,{\mathcal {F}},{\mathsf {P}})}$, где:

• ${\displaystyle \Omega }$ — произвольное непустое множество, называемое пространством элементарных исходов; его элементы ${\displaystyle \omega \in \Omega }$ — элементарные исходы;
• ${\displaystyle {\mathcal {F}}}$ — σ-алгебра подмножеств ${\displaystyle \Omega }$, элементы которой называются событиями;
• ${\displaystyle {\mathsf {P}}\colon {\mathcal {F}}\to [0,1]}$ — вероятностная мера: счётно-аддитивная функция с условием нормировки ${\displaystyle {\mathsf {P}}(\Omega )=1}$.

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

Например, при бросании игральной кости ${\displaystyle \Omega =\{1,2,3,4,5,6\}}$; событие «выпало чётное число» — это подмножество ${\displaystyle A=\{2,4,6\}}$, событие «выпало больше четырёх» — подмножество ${\displaystyle B=\{5,6\}}$. Событию «выпало чётное и больше четырёх» отвечает пересечение ${\displaystyle A\cap B=\{6\}}$.

Каждая теоретико-множественная операция получает вероятностное истолкование^[80]:

Язык множеств	Язык теории вероятностей
${\displaystyle \omega \in A}$	исход ${\displaystyle \omega }$ благоприятствует событию ${\displaystyle A}$
${\displaystyle A\subseteq B}$	из ${\displaystyle A}$ следует ${\displaystyle B}$
${\displaystyle A\cap B}$	произошли оба события
${\displaystyle A\cup B}$	произошло хотя бы одно из событий
${\displaystyle {\overline {A}}=\Omega \setminus A}$	событие ${\displaystyle A}$ не произошло (противоположное событие)
${\displaystyle A\cap B=\varnothing }$	события несовместны
${\displaystyle A\,\triangle \,B}$	произошло ровно одно из двух событий
${\displaystyle \Omega }$	достоверное событие
${\displaystyle \varnothing }$	невозможное событие

Соответственно и вероятностные тождества оказываются переводом теоретико-множественных. Из ${\displaystyle A\cup B=(A\setminus B)\sqcup (B\setminus A)\sqcup (A\cap B)}$ и аддитивности меры следует формула сложения:

${\displaystyle {\mathsf {P}}(A\cup B)={\mathsf {P}}(A)+{\mathsf {P}}(B)-{\mathsf {P}}(A\cap B).}$

Для приведённого примера с костью: ${\displaystyle {\mathsf {P}}(A\cup B)={\tfrac {3}{6}}+{\tfrac {2}{6}}-{\tfrac {1}{6}}={\tfrac {4}{6}}}$, что согласуется с прямым подсчётом ${\displaystyle A\cup B=\{2,4,5,6\}}$. Обобщение на любое число событий даёт формулу включений-исключений.

Из ${\displaystyle {\overline {A}}=\Omega \setminus A}$ получается правило дополнения ${\displaystyle {\mathsf {P}}({\overline {A}})=1-{\mathsf {P}}(A)}$, а законы де Моргана превращаются в равенства

${\displaystyle {\overline {A\cup B}}={\overline {A}}\cap {\overline {B}},\qquad {\overline {A\cap B}}={\overline {A}}\cup {\overline {B}},}$

означающие: «не произошло ни одного» равносильно «не произошло первое и не произошло второе».

Естественно было бы объявить событием любое подмножество ${\displaystyle \Omega }$, то есть взять ${\displaystyle {\mathcal {F}}=2^{\Omega }}$. Для конечных и счётных ${\displaystyle \Omega }$ так и поступают. Однако при ${\displaystyle \Omega =[0,1]}$ это невозможно: не существует счётно-аддитивной меры, определённой на всех подмножествах отрезка и инвариантной относительно сдвигов.

Препятствие обнаружил Дж. Витали в 1905 году. Разобьём ${\displaystyle [0,1)}$ на классы чисел, отличающихся на рациональное слагаемое, и выберем по одному представителю из каждого класса (аксиома выбора); полученное множество ${\displaystyle V}$ обладает тем свойством, что счётное число его сдвигов на рациональные числа покрывает ${\displaystyle [0,1)}$ без пересечений. Если бы вероятность ${\displaystyle {\mathsf {P}}(V)}$ была определена, то сумма счётного числа одинаковых слагаемых должна была бы равняться единице, что невозможно: при ${\displaystyle {\mathsf {P}}(V)=0}$ сумма равна нулю, при ${\displaystyle {\mathsf {P}}(V)>0}$ — бесконечности.

Поэтому событиями объявляют не все подмножества, а лишь элементы выбранной σ-алгебры. Требования к ${\displaystyle {\mathcal {F}}}$ ровно те, которые нужны, чтобы результат операций над событиями снова был событием^[81]:

• ${\displaystyle \Omega \in {\mathcal {F}}}$;
• если ${\displaystyle A\in {\mathcal {F}}}$, то ${\displaystyle {\overline {A}}\in {\mathcal {F}}}$;
• если ${\displaystyle A_{1},A_{2},\ldots \in {\mathcal {F}}}$, то ${\displaystyle \bigcup _{n=1}^{\infty }A_{n}\in {\mathcal {F}}}$.

Замкнутость относительно счётных объединений (а не только конечных) существенна: она позволяет говорить о событиях вида «произойдёт хотя бы одно из бесконечной серии» и делает осмысленными предельные теоремы. На числовой прямой обычно берут борелевскую σ-алгебру — наименьшую σ-алгебру, содержащую все интервалы.

Случайная величина — это функция ${\displaystyle X\colon \Omega \to \mathbb {R} }$, удовлетворяющая условию измеримости: прообраз любого борелевского множества ${\displaystyle B\subseteq \mathbb {R} }$ является событием,

${\displaystyle X^{-1}(B)=\{\omega \in \Omega \mid X(\omega )\in B\}\in {\mathcal {F}}.}$

Смысл условия прост: без него запись ${\displaystyle {\mathsf {P}}(X\in B)}$ не имела бы смысла, поскольку вероятность определена только на элементах ${\displaystyle {\mathcal {F}}}$. Привычные обозначения вида ${\displaystyle \{X<t\}}$ или ${\displaystyle \{a\leqslant X\leqslant b\}}$ — это сокращения для соответствующих подмножеств ${\displaystyle \Omega }$^[82].

Функция распределения определяется как вероятность прообраза луча:

${\displaystyle F_{X}(t)={\mathsf {P}}{\bigl (}\{\omega \mid X(\omega )\leqslant t\}{\bigr )},}$

а математическое ожидание — как интеграл Лебега по мере ${\displaystyle {\mathsf {P}}}$:

${\displaystyle {\mathsf {E}}X=\int _{\Omega }X(\omega )\,{\mathsf {P}}(d\omega ).}$

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

События ${\displaystyle A}$ и ${\displaystyle B}$ называются независимыми, если

${\displaystyle {\mathsf {P}}(A\cap B)={\mathsf {P}}(A)\cdot {\mathsf {P}}(B).}$

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

Для нескольких событий независимость в совокупности требует выполнения равенства для всех подмножеств индексов, а не только для пар. Различие показывает пример С. Н. Бернштейна: пусть ${\displaystyle \Omega }$ состоит из четырёх равновероятных исходов, а события ${\displaystyle A}$, ${\displaystyle B}$, ${\displaystyle C}$ — трёх подмножеств по два элемента, попарно пересекающихся ровно по одному общему исходу. Тогда

${\displaystyle {\mathsf {P}}(A\cap B)={\mathsf {P}}(A\cap C)={\mathsf {P}}(B\cap C)={\tfrac {1}{4}}={\tfrac {1}{2}}\cdot {\tfrac {1}{2}},}$

то есть события попарно независимы, однако

${\displaystyle {\mathsf {P}}(A\cap B\cap C)={\tfrac {1}{4}}\neq {\tfrac {1}{8}}={\mathsf {P}}(A)\,{\mathsf {P}}(B)\,{\mathsf {P}}(C),}$

и в совокупности они зависимы^[83].

Условная вероятность события ${\displaystyle A}$ при условии ${\displaystyle B}$ (где ${\displaystyle {\mathsf {P}}(B)>0}$) определяется как

${\displaystyle {\mathsf {P}}(A\mid B)={\frac {{\mathsf {P}}(A\cap B)}{{\mathsf {P}}(B)}}.}$

Геометрически это переход к новому пространству исходов: множество ${\displaystyle B}$ объявляется новым достоверным событием, а мера нормируется так, чтобы ${\displaystyle {\mathsf {P}}(B\mid B)=1}$.

Если события ${\displaystyle H_{1},H_{2},\ldots }$ образуют разбиение пространства ${\displaystyle \Omega }$ (попарно не пересекаются и в объединении дают ${\displaystyle \Omega }$), то для любого события ${\displaystyle A}$ справедлива формула полной вероятности:

${\displaystyle {\mathsf {P}}(A)=\sum _{i}{\mathsf {P}}(A\mid H_{i})\,{\mathsf {P}}(H_{i}),}$

вытекающая из представления ${\displaystyle A=\bigsqcup _{i}(A\cap H_{i})}$ и счётной аддитивности меры. Отсюда получается формула Байеса:

${\displaystyle {\mathsf {P}}(H_{k}\mid A)={\frac {{\mathsf {P}}(A\mid H_{k})\,{\mathsf {P}}(H_{k})}{\sum _{i}{\mathsf {P}}(A\mid H_{i})\,{\mathsf {P}}(H_{i})}}.}$

В общем случае условное ожидание относительно σ-алгебры ${\displaystyle {\mathcal {G}}\subseteq {\mathcal {F}}}$ определяется как проекция в пространстве ${\displaystyle L^{2}}$; на этом языке формулируется понятие мартингала^[84].

Если ${\displaystyle \Omega }$ конечно и все исходы равновозможны, вероятностная мера задаётся отношением мощностей:

${\displaystyle {\mathsf {P}}(A)={\frac {|A|}{|\Omega |}},}$

то есть «числом благоприятных исходов, делённым на общее число исходов». Это классическое определение Лапласа оказывается частным случаем колмогоровского при ${\displaystyle {\mathcal {F}}=2^{\Omega }}$. Подсчёт ${\displaystyle |A|}$ и ${\displaystyle |\Omega |}$ — задача комбинаторики: например, при бросании двух костей ${\displaystyle |\Omega |=36}$, а событию «сумма равна семи» отвечает подмножество из шести пар, откуда ${\displaystyle {\mathsf {P}}=6/36=1/6}$.

Для бесконечных ${\displaystyle \Omega }$ такое определение неприменимо: отношение мощностей теряет смысл. Его аналогом служит геометрическая вероятность, где вместо количества элементов берётся мера множества (длина, площадь, объём)^[85].

Теоретико-множественный язык необходим и для формулировки предельных теорем. Для последовательности событий ${\displaystyle A_{1},A_{2},\ldots }$ определяют верхний предел

${\displaystyle \limsup _{n\to \infty }A_{n}=\bigcap _{n=1}^{\infty }\bigcup _{k\geqslant n}A_{k},}$

то есть множество исходов, принадлежащих бесконечно многим ${\displaystyle A_{n}}$ («${\displaystyle A_{n}}$ происходят бесконечно часто»). Именно в этих терминах формулируется лемма Бореля — Кантелли: если ${\displaystyle \sum _{n}{\mathsf {P}}(A_{n})<\infty }$, то ${\displaystyle {\mathsf {P}}(\limsup A_{n})=0}$.

Различие между сходимостью почти наверное и сходимостью по вероятности также выражается через множества: первая означает, что множество исходов, где сходимость нарушается, имеет меру нуль. На этом языке формулируется усиленный закон больших чисел^[86].

Мощности конечных множеств связаны формулой включений-исключений:

${\displaystyle |A\cup B|=|A|+|B|-|A\cap B|,}$

обобщающейся на любое число множеств. Число подмножеств ${\displaystyle n}$-элементного множества равно ${\displaystyle 2^{n}}$, число его ${\displaystyle k}$-элементных подмножеств — биномиальному коэффициенту ${\displaystyle {\tbinom {n}{k}}}$^[87].

Множество — один из базовых типов данных во многих языках программирования; типичная реализация основана на хеш-таблицах или сбалансированных деревьях поиска. Реляционная модель данных, предложенная Э. Коддом в 1970 году, трактует таблицу базы данных как множество кортежей, а запросы — как операции реляционной алгебры, прямо восходящие к теоретико-множественным. В теории формальных языков язык определяется как множество слов в заданном алфавите.