Обозначение конструктора множеств

{\ Displaystyle \ {п \ в \ mathbb {Z} \ mid (\ существует к \ в \ mathbb {Z}) [п = 2к] \}}

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

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

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

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

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

${\ displaystyle \ {7,3,15,31 \}}$ - это набор, содержащий четыре числа 3, 7, 15 и 31 и ничего больше.
${\ Displaystyle \ {а, с, Ь \} = \ {а, б, с \}}$ - это набор, содержащий $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, \ точки, п \}}$ ${\ displaystyle i}$ ${\ Displaystyle 1 \ Leq я \ Leq п}$ ${\ Displaystyle \ {1, \ точки, п \}}$ ${\ Displaystyle [п]}$ ${\ displaystyle n = 0}$ ${\ Displaystyle [0] = \ {1, \ точки, 0 \}}$ ${\ displaystyle \ emptyset}$ ${\ Displaystyle \ {а_ {1}, \ точки, а_ {п} \}}$ ${\ displaystyle a_ {i}}$ ${\ Displaystyle 1 \ Leq я \ Leq п}$

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

${\ displaystyle \ {}$ Адреса на Пайн-стрит - это совокупность всех адресов на Пайн-стрит. ${\ displaystyle \}}$

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

Множества, определенные предикатом [ править ]

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

{\ Displaystyle \ {х \ середина \ фи (х) \}}

или же

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

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

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

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

{\ displaystyle \ {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)\}.

Символ ∈ здесь обозначает принадлежность к множеству , а символ обозначает логический оператор «и», известный как логическая конъюнкция . Эта запись представляет собой набор всех значений $x,$ которые принадлежат некоторому заданному набору $E,$ для которого предикат истинен (см. « Аксиома существования множества » ниже). Если является союзом , то иногда записывается с использованием запятой вместо символа . $\land$ $\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$

В общем, это не очень хорошая идея , чтобы рассмотреть наборы без определения домена, так как это будет представлять собой подмножество из всех возможных вещей , которые могут существовать , для которых предикат верен. Это легко может привести к противоречиям и парадоксам. Например, парадокс Рассела показывает, что выражение, хотя оно и выглядит хорошо сформированным как выражение построителя множества, не может определять множество, не вызывая противоречия. ^[7] $\{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]\}$ - это множество всех четных натуральных чисел . Знак означает «и», который известен как логическая связь . Знак ∃ означает «существует», что известно как количественная оценка существования . Так, например, читается как «существует x такой, что P ( x )». $\land$ $(\exists 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\mid \Phi (x)\}$ $\{\Psi (x)\mid \Phi (x)\},$

\{\Psi (x)\mid \Phi (x)\}=\{y\mid \exists (x),y=\Psi (x){\text{ and }}\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} \}$ создает набор пар, где каждая пара ставит целое число в соответствие с нечетным целым числом.

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

\{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 является рациональным числом с . В частности, оба набора равны множеству . $x^{2}=1$ $|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 Computing, где ключевое слово "for" возвращает список полученных переменных с использованием ключевого слова "yield". ^[8]

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

	Пример 1	Пример 2
Набор-строитель	$\{l\ \|\ l\in L\}$	$\{(k,x)\ \|\ k\in K\wedge x\in X\wedge P(x)\}$
Python	{ Л для л в L }	{( k , x ) для k в K для x в X, если P ( x )}
Haskell	[ l \| l <- ls ]	[( k , x ) \| k <- ks , x <- xs , p x ]
Scala	для ( l <- L ) получаем l	для ( k <- K ; x <- X, если P ( x )) вывести ( k , x )
C #	из l в L выберите l	из k в K из x в X, где P ( x ) select ( k , x )
SQL	ВЫБРАТЬ l ИЗ L_set	ВЫБРАТЬ k , x ИЗ K_set , X_set ГДЕ P ( x )

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

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

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

Заметки [ править ]

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

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

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

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

[4] "Исчерпывающий список символов теории множеств" . Математическое хранилище . 11 апреля 2020 . Проверено 20 августа 2020 .

[5] Weisstein, Эрик В. "Set" . mathworld.wolfram.com . Проверено 20 августа 2020 .

[6] "Set-Builder Notation" . mathsisfun.com . Проверено 20 августа 2020 .

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

[8] «Последовательность понимания» . Scala . Дата обращения 6 августа 2017 .

[1]