Русская Википедия:Форма записи множества
Шаблон:Quote box В теории множеств и его приложениях к логике, математике и информатике форма записи множества — это математические обозначения для описания множества путём перечисления его Шаблон:Не переведено 5 или указания свойств, которым элементы множества должны удовлетворятьШаблон:Sfn.
Множества, задаваемые перечислением
Множество можно описать путём перечисления всех его элементов внутри фигурных скобок, как в следующих примерах:
- <math>\{ 7, 3, 15, 31\}</math> — это множество, содержащее четыре числа: 3, 7, 15 и 31 и ничего более.
- <math>\{a, c, b\}=\{a, b, c\}</math> — это множество, содержащее Шаблон:Mvar, Шаблон:Mvar и Шаблон:Mvar и ничего более (порядок элементов в множестве не рассматривается, только их присутствие).
Такое задание иногда называется «методом перечисления» для конкретного множестваШаблон:Sfn.
Если хотят указать множество, содержащее регулярную последовательность, может быть использовано многоточие, как показано в следующих примерах:
- <math>\{ 1, 2, 3, \ldots, 100 \}</math> — это множество целых чисел между 1 и 100 включительно.
- <math>\{1, 2, 3, \ldots\}</math> — это множество всех натуральных чисел.
- <math>\{\ldots,-2, -1, 0, 1, 2, \ldots\}= \{0, 1, -1, 2, -2, \ldots\}</math> — это множество всех целых чисел.
В множестве нет упорядочения (это объясняет верность равенства в последнем примере), но при использовании многоточия используется упорядоченная последовательность до (или после) многоточия, как удобный способ объяснения, какие элементы принадлежат множеству. Показывается несколько первых элементов последовательности, а последующее многоточие предполагает, что нужно применить самую простую интерпретацию для продолжения последовательности. Если справа от многоточия нет значения, предполагается, что последовательность бесконечна.
Так, <math>\{1, \dots, n\}</math> означает множество всех натуральных чисел <math>i</math>, таких что <math>1\leqslant i\leqslant n</math>. Другим обозначением для множества <math>\{1, \dots, n\}</math> является скобочное обозначение <math>[n]</math>. Небольшим исключением является случай <math>n=0</math>, в котором <math>[0] = \{1, \dots, 0\}</math> является пустым множеством <math>\emptyset</math>. Аналогично, <math>\{a_1, \dots, a_n\}</math> обозначает множество всех <math>a_i</math> для <math>1\leqslant i\leqslant n</math>.
В приведённых примерах каждое множество описывается перечислением его элементов. Не все множества можно описать таким образом, или, даже если и можно так описать, перечисление их элементов может быть слишком длинным или слишком сложным, чтобы использовать данный метод. По этой причине многие множества определяются свойствами, которые характеризуют элементы множества. Эта характеризация может быть задана неформально используя прозаичный язык, как в следующем примере.
- <math>\{</math> номера домов по проспекту Косыгина <math>\}</math> — это множество всех номеров домов по проспекту Косыгина.
Однако такой подход может привести к потере точности или двусмысленности. Так, список адресов по проспекту Косыгина может означать как список домов, так и список квартир в этих домах.
Определение множеств предикатами
Для записи множества могут использоваться предикаты, а не явное перечисление элементовШаблон:Sfn. В этой форме записи множества имеется три части: переменная, двоеточие или вертикальная черта в качестве разделителя и логический предикат. В этом случае есть переменная слева от разделителя и правило справа от него. Эти три части заключаются в фигурные скобки:
- <math>\{x \mid \Phi(x)\}</math>
или
- <math>\{x : \Phi(x)\}.</math>
Разделитель можно читать «такое что»Шаблон:R, «для которого», или «со свойством». Формула Шаблон:Math называется правилом или предикатом. Все значения переменной x, для которых выполняется предикат (то есть, он верен) принадлежат определяемому множеству. Все значения Шаблон:Math, для которых предикат не выполняется, множеству не принадлежат. Таким образом, <math>\{x \mid \Phi(x)\}</math> — это множество всех значений Шаблон:Math, для которых верна формула Шаблон:MathШаблон:R. Это может быть пустое множество, если никакое значение Шаблон:Math не удовлетворяет формуле.
Задание области определения
Область определения Шаблон:Math может появиться слева от вертикальной чертыШаблон:R :
- <math>\{x \in E \mid \Phi(x)\},</math>
или она может быть объединена с предикатом:
- <math>\{ x \mid x \in E \text{ и } \Phi(x)\}\quad\text{или}\quad\{ x \mid x \in E \land \Phi(x)\}.</math>
Символ ∈ означает здесь Шаблон:Не переведено 5, в то время как символ <math>\land</math> означает логический оператор «И», известный как конъюнкция. Это обозначение представляет множество всех значений Шаблон:Math, принадлежащих некоторому множеству Шаблон:Math, для которых предикат принимает значение true, то есть истина (см. параграф «Аксиома существования» ниже). Если <math>\Phi(x)</math> является конъюнкцией <math>\Phi_1(x)\land\Phi_2(x)</math>, то форма <math>\{x \in E \mid \Phi(x)\}</math> иногда записывается в виде <math>\{x \in E \mid \Phi_1(x), \Phi_2(x)\}</math>, используя запятую вместо <math>\land</math>.
В общем случае некорректно рассматривать множество без определения области определения, поскольку область определения может представлять подмножество всех возможных объектов, которые могут существовать, для которых предикат верен. Это может легко привести к противоречию и парадоксу. Например, парадокс Рассела показывает, что выражение <math>\{x ~|~ x\not\in x\}</math>, хотя и выглядит правильно составленным как выражение для определения множества, не может определить множество без получения противоречияШаблон:Sfn.
В случаях, когда множество E ясно определяется из контекста, его можно не задавать. В литературе принято, чтобы автор заранее указал область определения, а потом область при определении множеств не указывается. Например, автор может написать нечто вроде: «Если не указано противное, переменные принадлежат натуральным числам.»
Примеры
Следующие примеры иллюстрируют конкретные множества, определённые предикатами. В каждом случае область определения указана слева от вертикальной черты, в то время как правило находится справа от неё.
- <math>\{ x \in \mathbb{R} \mid x > 0\}</math> — это множество всех строго положительных вещественных чисел, что можно записать в интервальных обозначениях как <math>(0, \infty)</math>.
- <math>\{ x \in \mathbb{R} \mid |x| = 1 \}</math> — это множество <math>\{-1, 1\}</math>. Это множество можно определить также, как <math>\{x \in \mathbb{R} \mid x^2 = 1\}</math>; см. параграф «эквивалентные предикаты задают равные множества» ниже.
- Для каждого целого m мы можем определить <math>G_m = \{x \in \mathbb{Z} \mid x \geqslant m \} = \{ m, m + 1, m + 2, \ldots\}</math>. В качестве примеров: <math>G_3 = \{x \in \mathbb{Z} \mid x \geqslant 3 \} = \{ 3, 4, 5, \ldots\}</math> и <math>G_{-2} = \{ -2, -1, 0, \ldots\}</math>.
- <math>\{ (x,y) \in \mathbb{R} \times \mathbb{R} \mid 0 < y < f(x) \}</math> — это множество пар вещественных чисел, таких что y больше 0 и меньше f(x) для заданной функции f. Здесь декартово произведение <math>\mathbb{R}\times\mathbb{R}</math> означает множество всех упорядоченных пар вещественных чисел.
- <math>\{n \in \mathbb{N} \mid (\exists k) [k\in \mathbb{N}\land n = 2k] \} </math> — это множество всех чётных натуральных чисел. Знак <math>\land</math> стоит для обозначения операции «И», которая известна как конъюнкция. Знак ∃ обозначает «существует», который известен как квантор существования. Так, например, <math> (\exists x) P(x)</math> читается как «существует x, такое что P(x) …".
- <math>\{n \mid (\exists k \in \mathbb{N} ) [n = 2k] \} </math> — это другой вариант записи того же самого множества чётных натуральных чисел. Нет необходимости требовать, чтобы Шаблон:Math был натуральным числом, поскольку это следует из формулы в правой части.
- <math>\{a \in \mathbb{R} \mid (\exists p\in \mathbb{Z} )(\exists q\in \mathbb{Z} )[ q \not = 0 \land aq=p] \}</math> — это множество рациональных чисел, то есть это вещественные числа, которые можно записать как частное двух целых чисел.
Более сложные выражения в левой части
Расширение формы записи множеств заменяет единственную переменную Шаблон:Math выражением. Таким образом вместо <math>\{ x \mid \Phi(x)\}</math> мы можем иметь <math>\{ \Psi(x) \mid \Phi(x)\},</math>, что можно читать как
- <math>\{ \Psi(x) \mid \Phi(x)\}=\{y\mid\exists (x), y=\Psi(x)\text{ и }\Phi(x)\}</math>.
Например:
- <math>\{2 n \mid n \in \mathbb N\}</math>, где <math>\mathbb N</math> — множество всех натуральных чисел — это множество всех чётных натуральных чисел.
- <math>\{p/q \mid p,q \in \mathbb Z, q \not = 0 \}</math>, где <math>\mathbb Z</math> — множество всех целых чисел — это Шаблон:Math, множество всех рациональных чисел.
- <math>\{ 2 t + 1 \mid t \in \mathbb Z\}</math> — это множество нечётных целых.
- <math>\{ (t, 2 t + 1) \mid t \in \mathbb Z\}</math> создаёт множество пар, где каждая пара состоит из целого и соответствующего ему нечётного числа.
Если обратные функции можно явно указать, выражение слева может быть исключено посредством простой подстановки. Рассмотрим в качестве примера множество <math>\{ 2 t + 1 \mid t \in \mathbb Z\}</math>. Сделаем подстановку <math>u = 2t + 1</math>, откуда получаем <math> t = (u-1)/2</math>, затем заменим t в форме записи множества
- <math>\{ 2 t + 1 \mid t \in \mathbb Z\} = \{ u \mid (u- 1)/2 \in \mathbb Z\}.</math>
Эквивалентные предикаты задают равные множества
Два множества равны тогда и только тогда, когда они имеют те же элементы. Множества, определённые формой записи множества равны тогда и только тогда, когда равны их правила построения, включая указание области определения. То есть
- <math> \{ x \in A \mid P(x) \}=\{ x \in B \mid Q(x) \} </math>
тогда и только тогда, когда
- <math> (\forall t)[ (t \in A \land P(t)) \Leftrightarrow (t \in B \land Q(t))]</math>.
Поэтому, чтобы доказать равенство двух множеств, определённых формой записи множества, достаточно доказать эквивалентность их предикатов, включая области определения.
Например:
- <math> \{ x \in \mathbb{R}\mid x^2 = 1 \} = \{ x \in \mathbb{Q} \mid |x| = 1 \} </math>
Поскольку два предиката-правила логически эквивалентны:
- <math> (x \in \mathbb{R} \land x^2 = 1) \Leftrightarrow (x \in \mathbb{Q} \land |x| = 1).</math>
Эта эквивалентность имеет место, поскольку для любого вещественного числа x мы имеем <math>x^2 = 1</math> тогда и только тогда, когда x рационально и <math>|x|=1</math>. В частности, оба множества равны множеству <math>\{-1,1\}</math>.
Аксиома существования множества
Во многих формальных теориях множеств, таких как система Цермело — Френкеля, форма записи множества не является частью формального синтаксиса теории. Вместо этого имеется Шаблон:Не переведено 5, которая утверждает, что если Шаблон:Math – множество, а Шаблон:Math – формула из языка теории множеств, то существует множество Шаблон:Math, членами которого являются в точности элементы Шаблон:Math, удовлетворяющие условию Шаблон:Math:
- <math>(\forall E)(\exists Y)(\forall x)[x \in Y \Leftrightarrow x \in E \land \Phi(x)].</math>
Множество Шаблон:Math, полученное из данной аксиомы есть в точности множество, описанное в форме записи множества <math>\{ x \in E \mid \Phi(x)\}</math>.
Параллели в языках программирования
Шаблон:Основная статья Аналогичная нотация, доступная во многих языках программирования (особенно Python и Haskell) — это списковое включение, которое комбинирует операции map и Шаблон:Не переведено 5 над одним и более списком.
На языке Python скобки записи множества заменяются на квадратные скобки, круглые или фигурные скобки, для определения списка, генератора и набора объектов соответственно. Python использует синтакс английского языка. Haskell заменяет скобки записи множества квадратными скобками и использует математические символы, включая стандартную для записи множества вертикальную черту.
То же самое можно получить в Scala с помощью Sequence Comprehensions, где ключевое слово «for» возвращает список переменных, полученных с помощью ключевого слова «yield»Шаблон:R.
Рассмотрим следующие задания множеств в некоторых языках программирования:
| Пример 1 | Пример 2 | |
|---|---|---|
| Форма записи множества | \ l \in L\}</math> | \ k \in K \wedge x \in X \wedge P(x) \}</math> |
| 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 над любой монадой С с нулевым элементом.
Примечания
Литература
