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

$\{n\in \mathbb {Z} \mid (\exists k\in \mathbb {Z} )[n=2k]\}$

— Множество всех чётных чисел,
выраженное в обозначениях множеств.

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

Множества, задаваемые перечислением

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

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

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

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

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

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

Так, $\{1,\dots ,n\}$ означает множество всех натуральных чисел $i$, таких что $1\leqslant i\leqslant n$. Другим обозначением для множества $\{1,\dots ,n\}$ является скобочное обозначение $[n]$. Небольшим исключением является случай $n=0$, в котором $[0]=\{1,\dots ,0\}$ является пустым множеством $\emptyset$. Аналогично, $\{a_{1},\dots ,a_{n}\}$ обозначает множество всех $a_{i}$ для $1\leqslant i\leqslant n$.

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

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

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

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

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

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

или

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

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

Задание области определения

Область определения E может появиться слева от вертикальной черты :

$\{x\in E\mid \Phi (x)\},$

или она может быть объединена с предикатом:

$\{x\mid x\in E{\text{ и }}\Phi (x)\}\quad {\text{или}}\quad \{x\mid x\in E\land \Phi (x)\}.$

Символ ∈ означает здесь принадлежность множеству, в то время как символ $\land$ означает логический оператор «И», известный как конъюнкция. Это обозначение представляет множество всех значений x, принадлежащих некоторому множеству E, для которых предикат принимает значение true, то есть истина (см. параграф «Аксиома существования» ниже). Если $\Phi (x)$ является конъюнкцией $\Phi _{1}(x)\land \Phi _{2}(x)$, то форма $\{x\in E\mid \Phi (x)\}$ иногда записывается в виде $\{x\in E\mid \Phi _{1}(x),\Phi _{2}(x)\}$, используя запятую вместо $\land$.

В общем случае некорректно рассматривать множество без определения области определения, поскольку область определения может представлять подмножество всех возможных объектов, которые могут существовать, для которых предикат верен. Это может легко привести к противоречию и парадоксу. Например, парадокс Рассела показывает, что выражение $\{x~|~x\not \in x\}$, хотя и выглядит правильно составленным как выражение для определения множества, не может определить множество без получения противоречия.

В случаях, когда множество E ясно определяется из контекста, его можно не задавать. В литературе принято, чтобы автор заранее указал область определения, а потом область при определении множеств не указывается. Например, автор может написать нечто вроде: «Если не указано противное, переменные принадлежат натуральным числам.»

Примеры

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

• $\{x\in \mathbb {R} \mid x>0\}$ — это множество всех строго положительных вещественных чисел, что можно записать в интервальных обозначениях как $(0,\infty )$.
• $\{x\in \mathbb {R} \mid |x|=1\}$ — это множество $\{-1,1\}$. Это множество можно определить также, как $\{x\in \mathbb {R} \mid x^{2}=1\}$; см. параграф «эквивалентные предикаты задают равные множества» ниже.
• Для каждого целого m мы можем определить $G_{m}=\{x\in \mathbb {Z} \mid x\geqslant m\}=\{m,m+1,m+2,\ldots \}$. В качестве примеров: $G_{3}=\{x\in \mathbb {Z} \mid x\geqslant 3\}=\{3,4,5,\ldots \}$ и $G_{-2}=\{-2,-1,0,\ldots \}$.
• $\{(x,y)\in \mathbb {R} \times \mathbb {R} \mid 0<y<f(x)\}$ — это множество пар вещественных чисел, таких что y больше 0 и меньше f(x) для заданной функции f. Здесь декартово произведение $\mathbb {R} \times \mathbb {R}$ означает множество всех упорядоченных пар вещественных чисел.
• $\{n\in \mathbb {N} \mid (\exists k)[k\in \mathbb {N} \land n=2k]\}$ — это множество всех чётных натуральных чисел. Знак $\land$ стоит для обозначения операции «И», которая известна как конъюнкция. Знак ∃ обозначает «существует», который известен как квантор существования. Так, например, $(\exists x)P(x)$ читается как «существует x, такое что P(x) …".
• $\{n\mid (\exists k\in \mathbb {N} )[n=2k]\}$ — это другой вариант записи того же самого множества чётных натуральных чисел. Нет необходимости требовать, чтобы n был натуральным числом, поскольку это следует из формулы в правой части.
• $\{a\in \mathbb {R} \mid (\exists p\in \mathbb {Z} )(\exists q\in \mathbb {Z} )[q\not =0\land aq=p]\}$ — это множество рациональных чисел, то есть это вещественные числа, которые можно записать как частное двух целых чисел.

Более сложные выражения в левой части

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

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

Например:

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

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

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

Эквивалентные предикаты задают равные множества

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

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

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

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

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

Например:

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

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

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

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

Аксиома существования множества

Во многих формальных теориях множеств, таких как система Цермело — Френкеля, форма записи множества не является частью формального синтаксиса теории. Вместо этого имеется аксиоматическая схема существования множества, которая утверждает, что если E – множество, а Φ(x) – формула из языка теории множеств, то существует множество Y, членами которого являются в точности элементы E, удовлетворяющие условию Φ:

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

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

Параллели в языках программирования

Основная статья: Списковое включение

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

На языке Python скобки записи множества заменяются на квадратные скобки, круглые или фигурные скобки, для определения списка, генератора и набора объектов соответственно. Python использует синтакс английского языка. Haskell заменяет скобки записи множества квадратными скобками и использует математические символы, включая стандартную для записи множества вертикальную черту.

То же самое можно получить в Scala с помощью Sequence Comprehensions, где ключевое слово «for» возвращает список переменных, полученных с помощью ключевого слова «yield».

Рассмотрим следующие задания множеств в некоторых языках программирования:

	Пример 1	Пример 2
Форма записи множества	$\{l\ |\ l\in L\}$	$\{(k,x)\ |\ 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)

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