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

$\{n\mid \exists k\in \mathbb {Z} ,n=2k\}$

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

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

Определение наборов по свойствам также известно как понимание набора , абстракция набора набора или определение содержания .

Наборы, определяемые перечислением [ править ]

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

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

Иногда это называют «методом списка» для определения набора. ^[2]

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

$\{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 в противном случае. ^[3]В этой форме нотация построителя множеств состоит из трех частей: переменная, разделитель двоеточие или вертикальная черта и предикат. Таким образом, слева от разделителя находится переменная, а справа от него — правило. Эти три части заключены в фигурные скобки:

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

или

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

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

Указание домена [ править ]

Домен $E$ может появиться слева от вертикальной полосы: ^[5]

\{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\},$ хотя на первый взгляд оно хорошо сформировано как выражение для построения множества, оно не может определить множество, не создавая противоречия. ^[6]

В случаях, когда набор $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. ^[7]

Рассмотрим эти примеры обозначений построителя множеств на некоторых языках программирования:

	Пример 1	Пример 2
Набор-конструктор	$\{l\ \|\ l\in L\}$	$\{(k,x)\ \|\ k\in K\wedge x\in X\wedge P(x)\}$
Питон	{ l для l в L }	{( k , x ) для k в K для x в X , если P ( x )}
Хаскелл	[ л \| л <- лс ]	[( k , x ) \| k <- ks , x <- xs , p x ]
Скала	для ( l <- L ) выход l	for ( k <- K ; x <- X если P ( x )) выход ( k , x )
С#	из l в L выберите l	из k в K из x в X где P ( x ) выберите ( k , x )
SQL	ВЫБЕРИТЕ l ИЗ L_set	ВЫБЕРИТЕ k , x ИЗ K_set , X_set ГДЕ P ( x )
Пролог	setof ( L , член ( L , Ls ), Результат )	setof (( K , X ),( член ( K , Ks ), член ( X , Xs ), вызов ( P , X )), Результат )
Эрланг	[ л \|\| л <- лс ]
Юлия	[ l for l ∈ L ]	[( k , x ) для k ∈ K для x ∈ X , если P ( x )]

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

См. также [ править ]

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

Примечания [ править ]

^ Розен, Кеннет (2007). Дискретная математика и ее приложения (6-е изд.). Нью-Йорк, штат Нью-Йорк: МакГроу-Хилл. стр. 111–112. ISBN 978-0-07-288008-3 .
^ Ричард Ауфманн, Вернон К. Баркер и Джоан Локвуд, 2007, Промежуточная алгебра с приложениями , Брукс Коул, стр. 6.
^ Майкл Дж. Каллинан, 2012, Переход к математике с доказательствами , Джонс и Бартлетт, стр. 44 и далее.
^ Вайсштейн, Эрик В. «Сет» . mathworld.wolfram.com . Проверено 20 августа 2020 г.
^ «Обозначение Set-Builder» . mathsisfun.com . Проверено 20 августа 2020 г.
^ Ирвин, Эндрю Дэвид; Дойч, Гарри (9 октября 2016 г.) [1995]. «Парадокс Рассела» . Стэнфордская энциклопедия философии . Проверено 6 августа 2017 г.
^ «Понимание последовательности» . Скала . Проверено 6 августа 2017 г.

[1] Розен, Кеннет (2007). Дискретная математика и ее приложения (6-е изд.). Нью-Йорк, штат Нью-Йорк: МакГроу-Хилл. стр. 111–112. ISBN 978-0-07-288008-3 .

[2] Ричард Ауфманн, Вернон К. Баркер и Джоан Локвуд, 2007, Промежуточная алгебра с приложениями , Брукс Коул, стр. 6.

[3] Майкл Дж. Каллинан, 2012, Переход к математике с доказательствами , Джонс и Бартлетт, стр. 44 и далее.

[4] Вайсштейн, Эрик В. «Сет» . mathworld.wolfram.com . Проверено 20 августа 2020 г.

[5] «Обозначение Set-Builder» . mathsisfun.com . Проверено 20 августа 2020 г.

[6] Ирвин, Эндрю Дэвид; Дойч, Гарри (9 октября 2016 г.) [1995]. «Парадокс Рассела» . Стэнфордская энциклопедия философии . Проверено 6 августа 2017 г.

[7] «Понимание последовательности» . Скала . Проверено 6 августа 2017 г.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

v т Это Теория множеств
Overview	Set (mathematics)
Axioms	Adjunction Choice countable dependent global Constructibility (V=L) Determinacy Extensionality Infinity Limitation of size Pairing Power set Regularity Union Martin's axiom Axiom schema replacement specification
Operations	Cartesian product Complement (i.e. set difference) De Morgan's laws Disjoint union Identities Intersection Power set Symmetric difference Union
Concepts Methods	Almost Cardinality Cardinal number (large) Class Constructible universe Continuum hypothesis Diagonal argument Element ordered pair tuple Family Forcing One-to-one correspondence Ordinal number Set-builder notation Transfinite induction Venn diagram
Set types	Amorphous Countable Empty Finite (hereditarily) Filter base subbase Ultrafilter Fuzzy Infinite (Dedekind-infinite) Recursive Singleton Subset · Superset Transitive Uncountable Universal
Theories	Alternative Axiomatic Naive Cantor's theorem Zermelo General Principia Mathematica New Foundations Zermelo–Fraenkel von Neumann–Bernays–Gödel Morse–Kelley Kripke–Platek Tarski–Grothendieck
Paradoxes Problems	Russell's paradox Suslin's problem Burali-Forti paradox
Set theorists	Paul Bernays Georg Cantor Paul Cohen Richard Dedekind Abraham Fraenkel Kurt Gödel Thomas Jech John von Neumann Willard Quine Bertrand Russell Thoralf Skolem Ernst Zermelo