Множества

Определение

Множество — это совокупность однозначно определённых объектов, называемых его элементами. Например,

$A=\{2,4,6\}$A={2,4,6}

а запись $4\in A$4∈A означает, что 4 принадлежит $A$A. Напротив, $5\notin A$5∈/A.

Порядок и повторения не меняют множество: $\{2,4,6\}${2,4,6}, $\{6,4,2\}${6,4,2} и $\{2,2,4,6\}${2,2,4,6} обозначают одно и то же множество. Важно только то, какие элементы входят в совокупность.

Как задать множество

Можно перечислить его элементы:

$B=\{a,e,i,o,u\}$B={a,e,i,o,u}

или определить их свойством:

$C=\{n\in\mathbb{N}\mid n<5\}=\{0,1,2,3,4\}$C={n∈N∣n<5}={0,1,2,3,4}

Здесь используется соглашение $0\in\mathbb{N}$0∈N. Вертикальная черта читается «таких, что». Свойство должно однозначно решать, принадлежит ли объект множеству.

Пустое множество, равенство и мощность

Пустое множество, обозначаемое $\varnothing$∅, не содержит элементов. Его нельзя путать с $\{\varnothing\}${∅}, где есть один элемент — само пустое множество.

Два множества равны, если у них в точности одинаковые элементы. Для конечного множества $A$A его мощность $|A|$∣A∣ — число элементов. Если $A=\{2,4,6\}$A={2,4,6}, то $|A|=3$∣A∣=3.

Включение и подмножества

Запись $A\subseteq B$A⊆B означает, что каждый элемент $A$A также принадлежит $B$B. Например,

$\{2,4\}\subseteq\{1,2,3,4\}${2,4}⊆{1,2,3,4}

Принадлежность и включение — разные отношения: $2\in A$2∈A сравнивает объект с множеством, а $A\subseteq B$A⊆B — два множества.

Каждое множество включено в себя, а пустое множество включено в любое множество.

Три основные операции

Пусть $A=\{1,2,3\}$A={1,2,3} и $B=\{3,4\}$B={3,4}.

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

Если задано универсальное множество $U$U, дополнение $A$A в $U$U равно $U\setminus A$U∖A. Без явно выбранного универсального множества выражение «дополнение $A$A» неполно.

Диаграммы помогают, но не определяют

Диаграмма Венна изображает множества областями. Перекрытие показывает пересечение, а совокупность областей — объединение. Это средство рассуждения, а не определение: доказательство должно возвращаться к условиям принадлежности.

Чтобы показать $A\cap B\subseteq A$A∩B⊆A, возьмём произвольный элемент $x\in A\cap B$x∈A∩B. По определению пересечения $x\in A$x∈A и $x\in B$x∈B; следовательно, $x\in A$x∈A. Включение доказано.

Зачем нужна эта абстракция

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

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

Итог

Множество определяется своими элементами: принадлежность связывает объект с множеством; включение сравнивает множества; объединение, пересечение и разность создают новые множества.

Учебные источники

• ACM/IEEE-CS/AAAI — Computer Science Curricula 2023, Mathematical and Statistical Foundations
• National University of Singapore — CS1231S, Discrete Structures
• Australian National University — MATH1005, Discrete Mathematical Models