Обозначение построителя множеств

$\{n\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\leq i\leq n$. Еще одно обозначение для $\{1,\dots ,n\}$ это обозначение скобок $[n]$. Тонкий частный случай $n=0$, в котором $[0]=\{1,\dots ,0\}$ равно пустому множеству $\emptyset$. Сходным образом, $\{a_{1},\dots ,a_{n}\}$ обозначает множество всех $a_{i}$ для $1\leq i\leq n$.

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

• $\{$ адреса на Сосновой улице $\}$ — это набор всех адресов на Пайн-стрит.

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

Наборы, определенные предикатом

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

$\{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{ and }}\Phi (x)\}\quad {\text{or}}\quad \{x\mid x\in E\land \Phi (x)\}.$

Символ ∈ здесь обозначает принадлежность к множеству , а символ $\land$ Символ обозначает логический оператор «и», известный как логическое соединение . Это обозначение представляет набор всех значений x , принадлежащих некоторому заданному множеству E, для которого предикат истинен (см. « Аксиому существования множества » ниже). Если $\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\geq m\}=\{m,m+1,m+2,\ldots \}$. В качестве примера: $G_{3}=\{x\in \mathbb {Z} \mid x\geq 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]\}$ – множество рациональных чисел ; то есть действительные числа, которые можно записать как отношение двух целых чисел .

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

Расширение нотации set-builder заменяет одну x выражением переменную . Поэтому вместо $\{x\mid \Phi (x)\}$, у нас может быть $\{f(x)\mid \Phi (x)\},$ который следует прочитать

$\{f(x)\mid \Phi (x)\}=\{y\mid \exists x(y=f(x)\wedge \Phi (x))\}$.

Например:

• $\{2n\mid n\in \mathbb {N} \}$, где $\mathbb {N}$ — множество всех натуральных чисел, — множество всех четных натуральных чисел.
• $\{p/q\mid p,q\in \mathbb {Z} ,q\not =0\}$, где $\mathbb {Z}$ представляет собой набор всех целых чисел, $\mathbb {Q} ,$ совокупность всех рациональных чисел.
• $\{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 ), представляет собой понимание списка , которое объединяет операции отображения и фильтрации над одним или несколькими списками .

В 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)\}$
Питон	{l for l in L}	{(k, x) for k in K for x in X if P(x)}
Хаскелл	[l | l <- ls]	[(k, x) | k <- ks, x <- xs, p x]
Скала	for (l <- L) yield l	for (k <- K; x <- X if P(x)) yield (k,x)
С#	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)
Пролог	setof(L,member(L,Ls),Result)	setof((K,X),(member(K,Ks),member(X,Xs),call(P,X)),Result)
Эрланг	[l || l <- ls]
Юлия	[l for l ∈ L]	[(k, x) for k ∈ K for x ∈ X if P(x)]

Нотация построителя множеств и нотация понимания списка являются экземплярами более общей нотации, известной как понимание монады , которая позволяет выполнять операции, подобные карте/фильтру, над любой монадой с нулевым элементом .

См. также

• Глоссарий теории множеств