Материал: baldin_kv_red_matematika_dlia_gumanitariev

Например, в качестве U можно взять множество N (заметим, что в некоторых монографиях оно начинается не с единицы, а с нуля).

Z = {z [ N | z < 6}, т. е. Z = {1, 2, , 4, 5}.

Для сокращения записи в математике используют кванторы всеобщности, существования, существования и единственности [17]:

; — квантор всеобщности (перевернутая первая буква английского слова All);

' — квантор существования (перевернутая первая буква английского слова Exists);

'! — квантор существования и единственности. Например, запись (;х [ Х) Р(х) означает: для всех х из

множества Х справедливо Р(х); запись ('у [ Y) R(у) — существует у из множества Y такое, что справедливо R(у); запись ('!z [ Z) М(z) — существует единственное z из множества Z такое, что справедливо M(z).

Операциинадмножествами[5,26]

Пусть задано универсальное множество U. Множество всех его подмножеств есть 2U. Заданы также множества Х и Y, причем Х [ 2U и У [ 2U.

Дополнением множества Х называется множество Х элементов множества U, которые не принадлежат Х:

Х = {х [ U | х Х}.

Графически операции над множествами (рис. 1.1) можно изображать с помощью кругов Эйлера (диаграмм Венна):

Пересечение (X > Y) двух множеств Х и Y состоит из элементов, принадлежащих обоим этим множествам (рис. 1.2):

X > Y={x | x [ X и x [ Y}

Объединение (Х < Y) двух множеств Х и Y состоит из элементов, которые принадлежат хотя бы одному из множеств Х и У (рис. 1. ):

16

U

U

X У

Рис. 1.2

Х < Y

U

X У

Рис. 1.3

X < Y={x | x [ X или x [ Y}

Разность (Х\Y) двух множеств Х и Y состоит из элементов, принадлежащих X, но не принадлежащих Y (рис. 1.4):

X\Y = {x | x [ X и x Y}

17

Х\Y

U

XУ

Рис. 1.4

Аналогично определяется разность (Y\Х) множеств Y и Х

(рис. 1.5):

Y\X = {y | y [ Y и y X}

Y\Х

U

X

Рис. 1.5

Симметрическая разность (ХDУ) множеств Х и Y состоит из элементов, которые принадлежат ровно одному из множеств

Х и Y (рис. 1.6):

XDY=(X\Y) < (Y\X)=(X < Y)\(X > Y)

ХDY

U

X

Рис. 1.6

18

Теперь рассмотрим конкретный числовой

Пример.

Дано множество: Х = {-5, 0, , 17, 28, , 100}. Y = {-7, 0, 5, 17, , 108}.

Х> Y = {0, 17, }.

Х< Y = {-7, -5, 0, , 5, 17, 28, , 100, 108}. Х\Y = {-5, , 28, 100}.

Y\Х = {-7, 5, 108}.

ХDY = {-7, -5, , 5, 28, 100, 108}.

Мощностьмножеств

Число элементов в конечном множестве Х называют его мощностью и обозначают |X| или #Х.

Например, X = {5, 12, 2 , 111}, |X| = 4.

Если известны мощности множеств Х и Y, то можно найти мощность их объединения по формуле:

|X < Y| = |X| + |Y| – |X > Y|.

В общем случае имеем [5]:

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

Если между двумя множествами можно установить взаимно однозначное соответствие, то в них одинаковое количество элементов.

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

Рассмотрим пример осуществления этого принципа. Каких подмножеств больше у 100-элементного множества:

мощности 60 или мощности 40.

19

Используем понятие числа сочетаний из n элементов по k (они отличаются только составом элементов) (более подробно в п. 1.2). Число сочетаний находится по формуле

где n! = 1 2 … n (читается n факториал). В нашем случае имеем:

Поэтому у 100-элементного множества одинаковое количество подмножеств мощности 60 и 40 элементов.

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

Для конечных множеств это означает, что в них одинаковое количество элементов.

Но это определение годится и для бесконечных множеств. Например, отрезки [0,1] и [0,10] равномощны, так как отображение х 10х дает нужное соответствие. [5,8].

Можно также доказать, что интервал (0,1) и луч (0, +`) равномощны. Искомое взаимно однозначное соответствие име-

Так же доказывается, что множество бесконечных последовательностей цифр 0, 1, 2, равномощно множеству бесконечных последовательностей цифр 0 и 1.

Тот факт, что множество Х равномощно (эквивалентно) множеству Y записывается так: X~Y (|X| = |Y|).

Множество называется счетным, если оно равномощно множеству натуральных чисел (N).

Например, множество целых чисел (Z) равномощно N, т. е.

Z~N.

Доказывается (см. [5]):

1) подмножество счетного множества конечно или счетно;

20