Свойства операции объединения.

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

1. (коммутативность);

2. (А В) С=А (В С) (ассоциативность);

3. Если , то А В= А;

4. А Ø= А.

Док-во. Формулы, подобные формулам 1-2, обычно доказываются так. Берётся элемент, принадлежащий правой части равенства, и доказывается, что он принадлежит левой части. В результате для формулы 1, например, будет доказано, что . Затем берётся элемент, принадлежащий левой части, и доказывается, что он принадлежит правой части равенства; для формулы 1 это будет означать, что . Из включений и следует, что .

Итак, пусть . Это значит, что либо , либо , либо одновременно и . Во всех трех случаях . Включение доказано. Пусть теперь . Это значит, что либо , либо , либо одновременно и . Во всех трех случаях . Включение доказано. Следовательно, , что и требовалось доказать.

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

Задание. Самостоятельно доказать включения соответствующих множеств и изобразить диаграммы для формул 2-4.

Опр.1.2.3. Пересечением множеств А и В называется множество С, состоящее из элементов, принадлежащих одновременно и множеству А, и множеству В. Если множества А и В не имеют общих элементов, их пересечение равно пустому множеству; в этом случае множества А и В называются непересекающимися.

Пересечение множеств обозначается символами " " и " " (знак умножения): или С=АВ. Для примера, приведенного после опр.1.2.1, . Геометрически пересечение множеств представлено на рис. 3.

Свойства операции пересечения множеств.

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

5. (коммутативность);

6. (А В) С=А (В С) (ассоциативность);

7. Если , то А В= В;

8. А Ø=Ø.

Задание. Самостоятельно доказать включения соответствующих множеств и изобразить диаграммы для формул 5-8.

Опр. 1.2.4 пересечения множеств для большего числа множеств: Пересечением множеств А₁, А₂, А₃, …, А_n (обозначение ) называется множество, состоящее из элементов, входящих в каждое из множеств А₁, А₂, А₃, …, А_n.

Теор. 1.2.3. Для операций объединения и пересечения множеств справедливы законы дистрибутивности:

9. ;

10. .

Док-во: Докажем формулу 9. Пусть . Тогда либо (следовательно, и , т.е. ); либо (следовательно, одновременно, (Þ ) и (Þ ), т.е. ); либо одновременно и (в этом случае можно применить любое из приведённых выше рассуждений). Таким образом, доказано, что .

Пусть . Рассмотрим два случая. 1. Пусть .Тогда . 2. Пусть , но , т.е. одновременно и , и . Это возможно, только если одновременно и , и ; т.е. , откуда следует, что . Включение доказано.

Задание. Самостоятельно доказать формулу 10.

Опр. 1.2.5. Разностью множеств А и В называется множество А\В, содержащее те элементы множества А, которые не принадлежат множеству В.

Теор. 1.2.4. Операции разности и дополнения антидистрибутивны относительно операций объединения и пересечения:

11. ;

12. .

(Дополнение к объединению некоторых множеств равно пересечению их дополнений; дополнение к пересечению множеств равно объединению их дополнений. Другими словами, символ дополнения \ можно менять местами со знаками и , при этом один из этих знаков заменяется другим).

Док-во. Докажем формулу 11. Пусть . Это означает, что и , т.е. , . Следовательно, и , т.е. . Включение доказано.

Пусть . Это означает, что одновременно и (т.е. и ), и (т.е. и ). Так как и , то . Но , следовательно, . Включение доказано. Из справедливости доказанных включений следует справедливость формулы 11.

Задание. Самостоятельно доказать формулу 12 и обобщение формул 11, 12 на большее число множеств:

13. ; 14. .

1.3. Мощность множества.

Количество элементов в конечном множестве естественно характеризовать их числом. В этом смысле множество чисел {-2, 0, 3,8} и множество букв {с, х, ф, а} эквивалентны, так как они содержат одинаковое число элементов. Для бесконечных множеств такого простого правила сравнения количеств элементов в них нет; чтобы получить возможность описывать количество элементов в бесконечных множествах, введём следующие определения.

Опр. 1.3.1. Между множествами А и В установлено взаимно-однозначное соответствие, если каждому элементу множества А каким-либо образом сопоставлен единственный элемент множества В, при этом каждому элементу множества В сопоставляется единственный элемент множества А.

Опр. 1.3.2. Множества, между которыми можно установить взаимно-однозначное соответствие, называются равномощными (имеющими одинаковую мощность, эквивалентными). Равномощность множеств обозначается символом "~": А~В.

Так, для приведённых выше множеств взаимно-однозначное соответствие устанавливается соотношениями -2«с, 0«ф, 3«а, 8«х. Однако ценность опр. 1.8 эквивалентности множеств заключается в том, что оно применимо к любым, в том числе бесконечным, множествам. Так, рассмотрим множество N натуральных чисел и множество N2={ 2, 4, 6, …} четных чисел. Взаимно-однозначное соответствие между этими множествами устанавливается соотношениями n«2n, следовательно, эти множества равномощны: N~N2. Этот пример показывает, что собственное подмножество может быть равномощным всему множеству; естественно, это может быть только для бесконечных множеств.

Соотношение ~ эквивалентности множеств транзитивно: если А~В, В~С, то А~С. Взаимно-однозначное соответствие между элементами а множества А и с множества С устанавливается по цепочке а «в«с.

Опр. 1.3.4. Множество, эквивалентное множеству натуральных чисел N называется счётным множеством.

Другими словами, множество счётно, если его элементы можно перенумеровать всеми натуральными числами. Счётны множества N2 чётных натуральных чисел, множество нечётных чисел (соответствие n«2n-1), множество всех целых чисел {0,±1,±2,±3,±4,…} (соответствие 1«0, 2«-1, 3«1, 4«-2, 5«2, …; вообще n«(n-1)/2 для нечётных n и n«-n/2 для чётных n).

Равномощны множества точек любых двух отрезков [a,b] и [c,d] (соответствие можно установить, например, с помощью центрального проектирования; рис. 7). Так же можно доказать равномощность множеств точек любых двух интервалов. Множество точек интервала равномощно множеству точек всей прямой (рис. 8). Сложнее ответить на вопрос, равномощны ли множества точек отрезка и интервала. Положительный ответ на этот вопрос даёт следующая теорема:

Теор. 1.3.1. Если множество А равномощно подмножеству В₁ множества В, а множество В равномощно подмножеству А₁ множества А, то множества А и В равномощны.

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

Рассмотрим более подробно свойства счётных множеств и множеств мощности континуум.