1.2.     ПОНЯТИЯ ТЕОРИИ МНОЖЕСТВ

Понятие «множество» относится к исходным, фундаментальным понятиям математики. Принято считать, что такие понятия не определяются. Всякое определение содержит другие понятия, логически предшествующие определяемому, поэтому, по крайней мере, первое определение должно содержать неопределяемые понятия. В качестве исходных выбираются понятия, в понимании которых не возникает существенных разногласий, т.е. возможные разногласия не нарушают правильности ни одного положения теории.

Определение. Под множеством S понимают любое собрание определенных и различимых между собой объектов, мыслимое как единое целое. Эти объекты называются элементами множества S.

Это определение принадлежит немецкому математику Г. Кантору (1845 – 1918гг.). Существенным является то, что собрание различных объектов представляется как один объект. Что касается самих предметов, которые могут входить в множество, то относительно них существует значительная свобода.

Объекты, образующие множество, называются элементами множества. Обычно множества обозначают прописными буквами латинского алфавита: A, B, C, …; а элементы множеств – строчными буквами: a, b, c, … .

Если объект х является элементом множества М, то говорят, что х принадлежит М:

х Π М.

В противном случае говорят, что х не принадлежит М:

х Ï  М.

Пример 1

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

Определение. Множество А называется подмножеством множества В, если всякий элемент из А является элементом В (обозначают). Если А является подмножеством В и В не является подмножеством А, то А называют истинным, строгим, собственным подмножеством В (обозначают ).

Определение. Множество, не содержащее элементов, называется пустым и обозначается Æ. Пустое множество является подмножеством любого множества.

Определение. Множество U, для которого все рассматриваемые множества являются его подмножеством, называется универсальным.

Определение. Множества А и В,  состоящие из одних и тех же элементов, являются равными. Равенство множеств обозначают:

А=В,

если множества не равны, то

А¹В.

Для равных множеств справедливо:

 и

Множества могут задаваться следующими способами:

1) перечислением элементов, т. е. списком своих элементов:

М = {a1, a2, …, ak};

2) характеристическим предикатом (заданием свойств, которыми должны обладать элементы множества):

М = {x | P(x)};

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

M = { x | x=f}.

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

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

Характеристический предикат – это условие, выраженное в форме логического выражения или процедуры, возвращающей логическое значение. Если для данного элемента условие выполнено, то он принадлежит определяемому множеству, в противном случае – не принадлежит.

Порождающая процедура – это процедура, которая порождает объекты, являющиеся элементами определяемого множества. Бесконечные множества (содержащие бесконечное число элементов) задаются характеристическим предикатом или порождающей процедурой.

Пример 2

1) М = {7, 14, 23, 34} – перечисление элементов множества.

2)  – характеристический предикат.

Определение. Мощностью конечного множества А называется число его элементов. Мощность множества обозначают:

|A|.

Пример 3

, |Æ| = 0; |{Æ}| = 1.

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

Определение. Множество всех подмножеств множества М называется булеаном множества М и обозначается В(М). При этом множество М называется универсумом (универсальным) и обозначается I.

Если множество М содержит n элементов, то множество В(М) содержит 2n элементов. Используется также обозначение множества-степени множества М в виде 2М.

Пример 4

I = {a, b, c}, B(I) = { Æ, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c}}.

Геометрически множества можно представить с помощью диаграмм Эйлера-Венна. Диаграмма состоит из прямоугольника, ограничивающего всю диаграмму, он представляет универсальное множество U. Внутри универсального множества строят фигуры, представляющие множества, чаще всего круги.

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

Для получения новых множеств из уже существующих рассматриваются операции над множествами.

Определение. Объединением множеств А и В называется множество , все элементы которого являются элементами хотя бы одного из множеств А, В (рис. 1.1):

Определение. Пересечением множеств А и В называется множество , элементы которого принадлежат одновременно как множеству А, так и множеству В (рис. 1.2):

Определение. Разностью множеств А и В называется множество , состоящее из элементов, принадлежащих множеству  А и не принадлежащих множеству В (рис. 1.3):

Определение. Симметрической разностью множеств А и В называется множество , состоящее из элементов этих множеств, которые принадлежат либо только множеству А, либо только множеству В (рис. 1.4):

Справедливо следующее равенство: .

Определение. Дополнением (абсолютным) множества А называется множество , содержащее элементы универсума, которые не принадлежат множеству А (рис. 1.5):

.

Пример 5

С помощью диаграмм Эйлера-Венна докажем тождество:

.

Рассмотрим левую часть соотношения  и выполним действия по порядку:

1) найдем пересечение множеств В и С () (рис. 1.6, а);

2) найдем объединение полученного множества  с множеством А  (рис. 1.6, б).

Рассмотрим правую часть соотношения :

1) найдем объединение множеств А и В  (рис. 1.6, в);

2) найдем объединение множеств А и С  (рис. 1.6, г);

3) найдем пересечение двух последних множеств  и   (рис. 6, д).

В обоих случаях (см. рис. 1.6, б, д) получаем равные множества. Следовательно, исходное соотношение справедливо.

Используя рассмотренные операции над множествами, можно выражать одни множества через другие, при этом сначала выполняется одноместная операция дополнения, затем пересечения и только потом – операция объединения (разности). Для изменения порядка выполнения операций в выражении используют скобки. Рассмотрим основные тождества алгебры множеств. Рассмотрим произвольные множества  А, В, и С, для которых справедливы следующие соотношения (табл. 1.16).

Таблица 1.16

Объединение

Пересечение

1. Коммутативность объединения

1. Коммутативность пересечения

2. Ассоциативность объединения

2. Ассоциативность пересечения

3. Дистрибутивность объединения относительно пересечения

3. Дистрибутивность пересечения относительно объединения

4. Законы действия с пустым и универсальным множествами

4. Законы действия с пустым и универсальным множествами

5. Закон идемпотентности объединения

5. Закон идемпотентности пересечения

6. Закон де Моргана

6. Закон де Моргана

7. Закон поглощения

7. Закон поглощения

8. Закон склеивания

8. Закон склеивания

9. Закон Порецкого

9. Закон Порецкого

10. Закон двойного дополнения

Пример 6

Доказать следующее тождество:

.

Решение

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

Используем равносильности алгебры множеств:

1) используя соотношение 3 (см. табл. 1.16),  получим:

;

2) используя соотношение 4 (см. табл. 1.16),  получим:

;

3) используя соотношение 4 (для пересечения) (см. табл. 1.16),  получим:

.

Построим соответствующие диаграммы Эйлера-Венна:

1) найдем  (рис. 1.7, а);

2) найдем  (рис. 1.7, б);

3) определим объединение множеств  и  (рис. 1.7, в).

Из рисунка 1.7, в видно, что

.

Определение. Упорядоченная пара <x, y> есть совокупность, состоящая из двух элементов х и у, расположенных в определенном порядке. Две пары <x, y>, <u, v> считаются равными тогда и только тогда, когда x = u, y = v. Аналогично определяется упорядоченное n элементов х1,, хn  и обозначается:

<x1,, xn>.

Определение. Декартовым или прямым произведением множеств X и Y называется множество , состоящее из всевозможных упорядоченных пар <x, y>, таких, что , то есть

.

Определение. Прямым произведением множеств Х1, Х2, …, Хn называется множество , состоящее из всех упорядоченных выборок из n элементов <x1, …, xn> таких, что . Если Х12=…Хn, то пишут:

.

Пример 7

Рассмотрим два множества X = {1, 2, 3} и Y = {а, b}. Найдем их декартовы произведения:

;

.

Пример 8

Даны Х – множество точек отрезка [0, 2], Y – множество точек отрезка [1, 4]. Тогда  – множество точек прямоугольника  с вершинами в точках (0, 1), (0, 4), (2, 1), (2, 4).

Пример 9

Представьте заштрихованные области диаграммы Эйлера-Венна (рис. 1.8, а) максимально компактным аналитическим выражением, в котором используется минимальное количество операций и букв.

Решение

На рис. 1.8, б изображена диаграмма Эйлера-Венна, заштрихованные области которой соответствуют выражению:

A È C È D.

На рис. 1.8, в изображена диаграмма Эйлера-Венна, заштрихованные области которой соответствуют выражению:

(D Ç C) È B.

Чтобы получить необходимое множество (см. рис. 1.8, а) необходимо вычесть из первого аналитического выражения второе. В результате получим:

(A È C È D) ((D Ç C) È B).