3.3. Аксиоматика теории множеств. Операции над множествами
Используя аксиоматический подход, можно формально построить теорию множеств на основании следующих аксиом.
Аксиома существования. Существует по крайней мере одно множество.
Аксиома существования пустого множества. Существует такое множество Æ, что ни один элемент ему не принадлежит.
Аксиома объемности (экстенциональности). Если множества A и B составлены из одних и тех же элементов, то они совпадают (равны): A = B.
Аксиома объединения. Для произвольных множеств A и B существует множество, элементами которого являются все элементы множества A и все элементы множества B и которое никаких других элементов не содержит.
Из аксиом объемности и объединения следует, что для произвольных множеств A и B множество, удовлетворяющее условиям аксиомы объединения, единственно. Действительно, если были бы два таких множества C1 и C2, то они содержали бы одни и те же элементы (все элементы, принадлежащие множеству A, и все элементы множества B) и поэтому, согласно аксиоме объемности, C1 = C2 = C.
Единственное множество С, состоящее из всех тех элементов, которые принадлежат хотя бы одному из множеств А, В, называется объединением множеств А и В (обозначение – АÈВ). Символически это можно записать так:
Аналогично определяется объединение произвольной (в том числе бесконечной) совокупности множеств. Если совокупность содержит небольшое количество множеств, то их объединение описывается явно: AÈВÈСÈD и т. д. В общем случае используется обозначение
которое читается так: «объединение всех множеств A, принадлежащих совокупности S». Если же все множества совокупности занумерованы индексами, то используются другие варианты обозначений:
(для случая, когда S={A1, A2,…,Ak}),
(для случая, когда S – бесконечная совокупность и ее множества занумерованы подряд натуральными числами),
(для случая, когда набор индексов множеств задан множеством I).
Пример 3.2.
Обозначим через Nk множество всех натуральных чисел, делящихся на k и не равных k, а через Р – множество всех простых чисел (принято считать, что 1ÏР). Тогда
– множество всех составных, т.e. непростых, чисел.
Аксиома разности. Для произвольных множеств А и В существует множество, элементами которого являются те и только те элементы множества А, которые не являются элементами множества В.
Из аксиом объемности и разности следует, что для произвольных множеств А и В существует в точности одно множество, содержащее элементы множества А, не принадлежащие множеству В. Множество С, состоящее из всех тех и только тех элементов А, которые не содержатся в В называется разностью множеств A и В (обозначение АВ):
Операция разности, во-первых, строго двухместна (т.е. определена только для двух множеств), а во-вторых, не коммутативна: AB ¹ BA. Если AB = Æ, то AÍ B.
Аксиома степени. Для каждого множества А существует семейство множеств В(А) (булеан), элементами которого являются все подмножества Аi,
Аi Ì A, и только они.
С помощью операций объединения и разности, используя введенные аксиомы, определим еще три операции на множествах: пересечение, дополнение, симметрическая разность.
Пересечением множеств A и В (обозначение АÇВ) называется множество, состоящее из всех тех и только тех элементов, которые принадлежат и A, и В:
Аналогично определяется пересечение произвольной (в том числе бесконечной) совокупности множеств. Обозначения для пересечения системы множеств аналогичны приведенным выше обозначениям для объединения.
Пример 3.3.
Если все рассматриваемые множества являются подмножеством некоторого «универсального» множества V, то может быть определена операция дополнения. Дополнением (до U) множества А (обозначение A) называется множество всех элементов, не принадлежащих А (но принадлежащих U)
A = UA. Множество U должно быть либо задано, либо очевидно из контекста, в противном случае проще пользоваться выражением UA. Например, из определения М2 очевидно, что М2 – это множество натуральных чисел, больших 100. Запись же N без контекста, т. е. без указания U, неясна – то ли это множество отрицательных целых чисел, то ли множество положительных дробных чисел, то ли пустое множество натуральных чисел.
Система множеств, в которой все попарные пересечения множеств пусты, называется разбиением множества U всех элементов этих множеств, а множества такой системы называются классами или блоками разбиения. Всякий элемент U входит в один и только в один класс разбиения.
Симметрическая разность множеств А и В определяется выражением
Операции объединения, пересечения, разности и дополнения проиллюстрированы на рис. 3.2, результирующее множество каждой операции изображено заштрихованной областью.
Используя эти операции, можно выражать одни множества через другие, при этом сначала выполняется одноместная операция дополнения, затем пересечения и только затем операция объединения (разности). Для изменения этого порядка в выражении используют скобки.
Пример 3.5.
Рассмотрим операцию дополнения множества, являющегося пересечением множеств A и B. Ее результат совпадает с объединением дополнений этих множеств M = A Ç B = A È B; в этом можно убедиться с помощью диаграмм Эйлера (рис. 3.3).
Таким образом, множество можно задать выражением, в которое входят идентификаторы (указатели) множеств, операции и, быть может, скобки. Такой способ задания множества называется аналитическим.
Операции объединения, пересечения и дополнения часто называют булевыми операциями над множествами. Позднее будет пояснен смысл этого названия и рассмотрены соотношения между этими операциями.