Глава 1. Введение в теорию множеств.

1.1. Основные определения.

Понятие множества принадлежит к числу фундаментальных неопределяемых по­нятий математики.

Множество — это любая определенная со­вокупность объектов.

Элементы - объекты, из которых составлено множество.

Элементы множества различны и отличимы друг от друга.

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

Существуют две проблемы в вопросах понятия элемента множества и его принадлежности

1) проблематична отличимость элементов. Например, символы о и а, ко­торые встречаются на этой странице, — это один элемент множества А (в смысле они оба являются буквами) или два разных элемента (потому что это разные буквы)?

2)  проблематична возможность (без дополнительных усилий) ука­зать, принадлежит ли данный элемент данному множеству. Например, является ли число 86958476921537485067857467 простым?

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

Класс (се­мейство) множеств - множество, элементами которого являются множества.

Пустое множество – множество, не содержащее элементов. Обозначение: ø.

Обычно в конкретных рассуждениях элементы всех множеств берутся из неко­торого одного, достаточно широкого множества U (своего для каждого случая), которое называется универсальным множеством (или универсумом).

Задание множеств

Существует три наиболее распространенных способа задания множеств:

1) перечисление элементов: ;

2) характеристический предикат:  (это некоторое условие, выраженное в форме логического утверждения или процедуры, возвращающей логическое значение. Если для данного элемента условие выполнено, то он принадле­жит определяемому множеству, в противном случае — не принадлежит)

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

Пример: Требуется задать множество натуральных чисел от 10 до 17.

1. М: ={10,11,12,13,14,15,16,17};

2. M:={ };

3. M: = { }.

Перечислением можно задавать только конечные множества. Бесконечные множе­ства задаются характеристическим предикатом или порождающей процедурой.

Пример:

N: = { n | n: = 0; while true do begin n: = n + 1; writeln n; endwhile }.

Парадокс Рассела: Пусть Y - множество всех множеств, не содержащих себя в качестве элемента, т.е. . Тогда невозможно ответить на вопрос о принадлежности .

Доказательство: Пусть Y   Y, но это означает, что Y содержит само себя, а по условию Y - множество всех множеств, не содержащих себя в качестве элемента, т.е. Y  Y. Пусть Y  Y, тогда Y  Y по условию, т.к. не содержит себя. Получается неустранимое логическое противоречие, которое известно как парадокс Рассела.

Данный парадокс известен также как парадокс брадобрея (или цирюльника) и будет рассмотрен в разделе парадоксов исчисления высказываний.

Операции над множествами

Множество А содержится в множестве В (множество В включает множество А), если каждый элемент А есть элемент В:

.

В этом случае А называется подмножеством В, В — надмножеством А.

Множество А называется собственным подмножеством множества В, если  и .

Если множество  не является собственным подмножеством множества , имеет место следующее обозначение:  (  является подмножеством  и может быть совпадающим с ним).

Каково бы ни было множество  выполняются следующие два свойства:

1) ;

2) ø

Два множества равны, если они являются подмножествами друг друга:

.

Мощность множества М обозначается как |М|. Для конечных множеств мощ­ность — это число элементов. Например, | ø | = 0, но |{ ø }| == 1. Если , то множества  и  называются равномощными.

 

Каковы бы ни были два множества  и  между ними возможны следующие операции:

1. Пересечение.

2. Объединение.

 

3. Разность.

4. Дополнение (отрицание).

Операция дополнения подразумевает некоторый универсум (универсальное множество) : .

5. Симметрическая разность

Здесь помимо самих операций приведены диаграммы Эйлера (в некоторой литературе[1] принято название Эйлера-Вена), иллюстрирующие операции над мно­жествами. Сами исходные множества изображаются фигурами (в данном случае овалами), а результат графически выделяется (в данном случае для выделения использована штриховка).

Разбиения и покрытия

Пусть  — некоторое семейство подмножеств множества , .

Семейство  называется покрытием множества , если каждый элемент  принадлежит хотя бы одному из .

.

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

 ø.

Дизъюнктное покрытие  называется разбиением множества М.

Пример

Пусть М: ={1,2,3}. Тогда {{1,2}, {2,3}, {3,1}} является покрытием, но не разби­ением; {{1}, {2}, {3}} является разбиением (и покрытием), а семейство {{1}, {2}} является дизъюнктным, но не является ни покрытием, ни разбиением.

 

Булеан - множество всех подмножеств множества М: .

Теорема о булеане: Для любого конечного множества  выполняется

.

Доказательство:

База индукции: пусть М = ø, тогда  и  = {ø}. Поскольку  и |{ ø }|  то условие теоремы выполняется.

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

 и .

При этом  и ø. По индукционному предположению  и . Следовательно,

.

Теорема доказана.

 

Пересечение, объединение и разность подмножеств множества U (универсума) являются подмножествами множества U. Множество всех подмножеств множе­ства U с операциями пересечения, объединения, разности и дополнения образует алгебру подмножеств множества U.