Нотация конструктора множеств

Использование фигурных скобок для указания множеств

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

Множество всех четных целых чисел ,
выраженное в нотации конструктора множеств.

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

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

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

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

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

или

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

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

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

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

${\displaystyle \{x\in E\mid \Phi (x)\},}$

или присоединив его к предикату:

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

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

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

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

Примеры

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

• ${\displaystyle \{x\in \mathbb {R} \mid x>0\}}$— это множество всех строго положительных действительных чисел , которые можно записать в интервальной нотации как . ${\displaystyle (0,\infty )}$
• ${\displaystyle \{x\in \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 \{n\in \mathbb {N} \mid (\exists k)[k\in \mathbb {N} \land n=2k]\}}$— это множество всех четных натуральных чисел . Знак обозначает «и», что известно как логическое соединение . Знак ∃ обозначает «существует», что известно как экзистенциальная квантификация . Так, например, читается как «существует x такой, что P ( x ) ». ${\displaystyle \land }$ ${\displaystyle (\exists x)P(x)}$
• ${\displaystyle \{n\mid (\exists k\in \mathbb {N} )[n=2k]\}}$— вариант обозначения того же множества четных натуральных чисел. Не обязательно указывать, что n — натуральное число, так как это подразумевается формулой справа.
• ${\displaystyle \{a\in \mathbb {R} \mid (\exists p\in \mathbb {Z} )(\exists q\in \mathbb {Z} )[q\not =0\land aq=p]\}}$— это множество рациональных чисел , то есть действительных чисел, которые можно записать в виде отношения двух целых чисел .

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

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

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

Например:

• ${\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 \{(t,2t+1)\mid t\in \mathbb {Z} \}}$ создает набор пар, где каждая пара ставит целое число в соответствие нечетному целому числу.

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

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

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

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

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

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

${\displaystyle (\forall t)[(t\in A\land P(t))\Leftrightarrow (t\in B\land Q(t))]}$.

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

Например,

${\displaystyle \{x\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 |x|=1}$ ${\displaystyle \{-1,1\}}$

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

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

${\displaystyle (\forall E)(\exists Y)(\forall x)[x\in Y\Leftrightarrow x\in E\land \Phi (x)].}$

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

В языках программирования

Похожая нотация, доступная в ряде языков программирования (в частности, в Python и Haskell ), — это списочное включение , которое объединяет операции отображения и фильтрации над одним или несколькими списками .

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

Того же самого можно добиться в Scala с помощью Sequence Comprehensions, где ключевое слово «for» возвращает список полученных переменных с помощью ключевого слова «yield». ^[6]

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

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

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

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

Примечания

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