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

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

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

Наборы, определяемые перечислением

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

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

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

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

• ${\ 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 \}}$

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

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

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

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

или

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

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

Указание домена

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

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

или добавив его к сказуемому:

${\ displaystyle \ {x \ mid x \ in E {\ text {and}} \ Phi (x) \} \ quad {\ text {or}} \ quad \ {x \ mid x \ in E \ land \ Phi (Икс)\}.}$

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

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

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

Примеры

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

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

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

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

${\ Displaystyle \ {\ Пси (х) \ середина \ Фи (х) \} = \ {у \ середина \ существует (х), у = \ Пси (х) {\ текст {и}} \ Фи (х) \}}$.

Например:

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

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

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

Эквивалентные предикаты дают равные наборы

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

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

если и только если

${\ Displaystyle (\ forall т) [(т \ в А \ земля Р (т)) \ Leftrightarrow (т \ в В \ земля Q (т))]}$.

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

Например,

${\ Displaystyle \ {х \ 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).}$

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

Установить аксиому существования

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

${\ Displaystyle (\ forall E) (\ существует Y) (\ forall x) [x \ in Y \ Leftrightarrow x \ in E \ land \ Phi (x)].}$

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

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

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

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

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

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

	Пример 1	Пример 2
Набор-строитель	${\ Displaystyle \ {л \ | \ л \ в L \}}$	${\ Displaystyle \ {(к, х) \ | \ к \ в К \ клин х \ в Х \ клин Р (х) \}}$
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)

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

Смотрите также

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

Примечания