Форма записи множества

Множество можно описать путём перечисления всех его элементов внутри фигурных скобок, как в следующих примерах:

• ${\displaystyle \{7,3,15,31\}}$ — это множество, содержащее четыре числа: 3, 7, 15 и 31.
• ${\displaystyle \{a,c,b\}=\{a,b,c\}}$ — это множество, содержащее a, b и c (порядок элементов в множестве не рассматривается, только их присутствие).

Такое задание иногда называется «методом перечисления» для конкретного множества^[2].

Непосредственное перечисление элементов применимо лишь к конечным множествам. Для бесконечных множеств, закономерность построения которых очевидна, используют запись с многоточием, как показано в следующих примерах:

• ${\displaystyle \{1,2,3,\ldots ,100\}}$ — это множество целых чисел от 1 до 100 включительно.
• ${\displaystyle \{1,2,3,\ldots \}}$ — это множество всех натуральных чисел.
• ${\displaystyle \{\ldots ,-2,-1,0,1,2,\ldots \}=\{0,1,-1,2,-2,\ldots \}}$ — это множество всех целых чисел.

В множестве нет упорядочения (это объясняет верность равенства в последнем примере), но при использовании многоточия используется последовательность до (или после) многоточия, как удобный способ объяснения, какие элементы принадлежат множеству. Показывается несколько первых элементов последовательности, а последующее многоточие предполагает, что нужно применить самую простую интерпретацию для продолжения последовательности. Если справа от многоточия нет значения, предполагается, что последовательность бесконечна.

Так, ${\displaystyle \{1,\dots ,n\}}$ означает множество всех натуральных чисел ${\displaystyle i}$, таких что ${\displaystyle 1\leqslant i\leqslant n}$. При n < 1 это множество по соглашению считается пустым множеством ${\displaystyle \emptyset }$. Аналогично, ${\displaystyle \{a_{1},\dots ,a_{n}\}}$ обозначает множество всех ${\displaystyle a_{i}}$ для ${\displaystyle 1\leqslant i\leqslant n}$.

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

• ${\displaystyle \{}$ номера домов по проспекту Косыгина ${\displaystyle \}}$ — это множество всех номеров домов по проспекту Косыгина.

Однако такой подход может привести к потере точности или двусмысленности. Так, список адресов по проспекту Косыгина может означать как список домов, так и список квартир в этих домах.

Для записи множества могут использоваться предикаты (логические условия, которые для каждого значения переменной либо истинны, либо ложны), а не явное перечисление элементов^[1]. Такая запись включает три элемента: переменная, двоеточие или вертикальная черта в качестве разделителя и логический предикат. В этом случае есть переменная слева от разделителя и правило справа от него. Эти три части заключаются в фигурные скобки:

${\displaystyle \{x\mid \Phi (x)\}}$

или

${\displaystyle \{x:\Phi (x)\}.}$

Разделитель можно читать «такое что», «для которого», или «со свойством». Φ(x) — это предикат . Все значения переменной x, для которых предикат является истинным, принадлежат определяемому множеству. Все значения x, для которых предикат является ложным, множеству не принадлежат. Таким образом, ${\displaystyle \{x\mid \Phi (x)\}}$ — это множество всех значений x, для которых верна формула Φ. Это может быть пустое множество, если никакое значение x не удовлетворяет формуле.

Расширение формы записи множеств заменяет единственную переменную x выражением. Таким образом вместо ${\displaystyle \{x\mid \Phi (x)\}}$ мы можем иметь ${\displaystyle \{\Psi (x)\mid \Phi (x)\},}$, что можно читать как

${\displaystyle \{\Psi (x)\mid \Phi (x)\}=\{y\mid \exists (x),y=\Psi (x){\text{ и }}\Phi (x)\}}$.

Например:

• ${\displaystyle \{2n\mid n\in \mathbb {N} \}}$, где ${\displaystyle \mathbb {N} }$ — множество всех натуральных чисел — это множество всех чётных натуральных чисел.
• ${\displaystyle \{p/q\mid p\in \mathbb {Z} ,q\in \mathbb {N} \}}$, где ${\displaystyle \mathbb {Z} }$ — множество всех целых чисел — это ℚ, множество всех рациональных чисел.
• ${\displaystyle \{2t+1\mid t\in \mathbb {Z} \}}$ — это множество нечётных целых.
• ${\displaystyle \{(t,2t+1)\mid t\in \mathbb {Z} \}}$ — множество всех пар ${\displaystyle (t,2t+1)}$, где ${\displaystyle t}$ — целое число.

Если обратные функции можно явно указать, выражение слева может быть исключено посредством простой подстановки. Рассмотрим в качестве примера множество ${\displaystyle \{2t+1\mid t\in \mathbb {Z} \}}$. Сделаем подстановку ${\displaystyle u=2t+1}$, откуда получаем ${\displaystyle t=(u-1)/2}$, затем заменим t в форме записи множества

${\displaystyle \{2t+1\mid t\in \mathbb {Z} \}=\{u\mid (u-1)/2\in \mathbb {Z} \}.}$

Два множества равны тогда и только тогда, когда они имеют одни и те же элементы. Для множеств, задаваемых характеристическими предикатами (то есть в форме ${\displaystyle \{x\mid \mathrm {P} (x)\}}$), равенство выполняется тогда и только тогда, когда эти предикаты логически эквивалентны (с учётом базовых множеств). То есть:

${\displaystyle \{x\in A\mid P(x)\}=\{x\in B\mid Q(x)\}}$

тогда и только тогда, когда

${\displaystyle (\forall t)[(t\in A\land P(t))\Leftrightarrow (t\in B\land Q(t))]}$.

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

Например:

${\displaystyle \{x\in \mathbb {R} \mid x^{2}=1\}=\{x\in \mathbb {Q} \mid |x|=1\}}$

Поскольку два предиката-правила логически эквивалентны:

${\displaystyle (x\in \mathbb {R} \land x^{2}=1)\Leftrightarrow (x\in \mathbb {Q} \land |x|=1).}$

Равенство выполняется, поскольку для любого вещественного числа ${\displaystyle x}$ условие ${\displaystyle x^{2}=1}$ равносильно условию ${\displaystyle |x|=1}$. В частности, оба множества равны множеству ${\displaystyle \{-1,1\}}$.

Во многих формальных теориях множеств, таких как система Цермело — Френкеля, нотация ${\displaystyle \{x\in E\mid \Phi (x)\}}$ не является частью формального синтаксиса теории. Вместо этого используется схема аксиом выделения (также называемая аксиомой выделения или схемой выделения), которая гарантирует, что для любого множества ${\displaystyle E}$ и любого предиката ${\displaystyle \Phi (x)}$ существует множество ${\displaystyle \{x\in E\mid \Phi (x)\}}$:

${\displaystyle (\forall E)(\exists Y)(\forall x)[x\in Y\Leftrightarrow x\in E\land \Phi (x)].}$

Множество ${\displaystyle Y}$, существование которого утверждается аксиомой, есть в точности множество, описанное в форме записи ${\displaystyle \{x\in E\mid \Phi (x)\}}$.

Аналогичная нотация, доступная во многих языках программирования (особенно Python и Haskell) — это Генератор списков (англ. list comprehension), который комбинирует операции map и фильтр над одним и более списком.

На языке Python скобки записи множества заменяются на квадратные скобки, круглые или фигурные скобки, для определения списка, генератора и множества соответственно. Python использует синтаксис английского языка. Haskell заменяет скобки записи множества квадратными скобками и использует математические символы, включая стандартную для записи множества вертикальную черту. В Haskell генератор списков записывается как [выражение | переменная <- список, условие], где <- означает «берётся из», а условия (стражи) служат для фильтрации элементов.

В Scala используется конструкция for-comprehension: запись for (enumerators) yield e создаёт коллекцию значений выражения e, где enumerators — это разделённые точкой с запятой генераторы (например, x <- список) и фильтры (например, if x > 0).

В языке C# аналогичная конструкция реализована через LINQ (Language Integrated Query) с ключевыми словами from, in, where, select.

В SQL роль характеристического предиката выполняет условие в предложении WHERE оператора SELECT: в результат попадают только строки таблицы, для которых это условие истинно. Рассмотрим следующие задания множеств в некоторых языках программирования:

	Пример 1	Пример 2
Форма записи множества	${\displaystyle \{l\mid l\in L\}}$	${\displaystyle \{(k,x)\mid k\in K\wedge x\in X\wedge P(x)\}}$
Python	[l for l in L]	[(k, x) for k in K for x in X if P(x)]
Haskell	[l | l <- ls]	[(k, x) | k <- ks, x <- xs, p x]
Scala	for (l <- L) yield l	for (k <- K; x <- X if P(x)) yield (k,x)
C#	from l in L select l	from k in K from x in X where P(x) select (k,x)
SQL	SELECT l FROM L_set	SELECT k, x FROM K_set, X_set WHERE P(x)

В примерах на языке Python используется генератор списков (англ. list comprehension) — конструкция для создания списков, цикл for для перебора элементов, оператор принадлежности `in` и условный оператор `if` для фильтрации.

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