Множества

Множества

Основные понятия и обозначения, связанные с множествами и операциями над ними:

Понятие множества появилось в математике сравнительно недавно, в конце 19-го века, в связи с работами Кантора (сравнение мощностей множеств), о которых пойдет речь дальше. Некоторое время назад этот язык пытались внедрить в школьное преподавание, объясняя ученикам, что у уравнения $$x^2\hm+1\hm=0$$ есть множество решений (впрочем, пустое), что множество решений системы уравнений есть пересечение множеств решений каждого из них (а для "совокупности" уравнений - объединение), что в множестве $$\{2,2,3\}$$ не три элемента, а два, и оно равно множеству $$\{2,3\}$$, что $$\varnothing$$, $$\{\varnothing\}$$ и $$\{\varnothing,\{\varnothing\}\}$$ - это три совершенно разных множества и т.д. Но все равно большинство школьников так и не поняло, почему множество решений уравнения $$x^2\hm=4$$ можно записывать как $$\{-2,2\}$$, а множество решений уравнения $$x^2\hm=-4$$ нельзя записывать как $$\{\varnothing\}$$ (а надо писать $$\varnothing$$ ). Отметим кстати еще два расхождения: в школе натуральные числа начинаются с единицы, а в некоторых книжках - с нуля (мы тоже будем называть нуль натуральным числом). Кроме того, иногда вместо $$\subset$$ пишут $$\subseteq$$, используя $$\subset$$ для собственных подмножеств (вместо нашего $$\subsetneq$$ ).

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

1.Старейший математик среди шахматистов и старейший шахматист среди математиков - это один или тот же человек или (возможно) разные?

2. Лучший математик среди шахматистов и лучший шахматист среди математиков - это один или тот же человек или (возможно) разные?

3. Каждый десятый математик - шахматист, а каждый шестой шахматист - математик. Кого больше - математиков или шахматистов - и во сколько раз?

4. Существуют ли такие множества $$A$$, $$B$$ и $$C$$, что $${A\cap B}\hm\ne \varnothing$$, $$A\cap C\hm=\varnothing$$ и $$(A\cap B)\setminus C\hm=\varnothing$$?

5. Какие из равенств (а) $$(A\hm\cap B)\hm\cup C \hm= (A\hm\cup C)\hm\cap (B\hm\cup C)$$ ; (б) $$(A\hm\cup B)\hm\cap C \hm= (A\hm\cap C)\hm\cup (B\hm\cap C)$$ ; (в) $$(A\hm\cup B)\setminus C \hm= (A\setminus C)\hm\cup B$$ ; (г) $$(A\hm\cap B)\setminus C \hm= (A\setminus C)\hm\cap B$$ ; (д) $$A\setminus (B\hm\cup C) = (A\setminus B)\hm\cap (A\setminus C)$$ ; (е) $$A\setminus (B\hm\cap C) = (A\setminus B)\hm\cup (A\setminus C)$$ верны для любых множеств $$A,B,C$$?

6. Проведите подробное доказательство верных равенств предыдущей задачи, исходя из определений. (Докажем, что множества в левой и правой частях равны. Пусть $$x$$ - любой элемент левой части равенства. Тогда... Поэтому $$x$$ входит в правую часть. Обратно, пусть...) Приведите контрпримеры к неверным равенствам.

7. Докажите, что симметрическая разность ассоциативна: $${A\bigtriangleup(B\bigtriangleup C)}\hm= {(A\bigtriangleup B)\bigtriangleup C}$$ для любых $$A$$, $$B$$ и $$C$$. (Указание: сложение по модулю $$2$$ ассоциативно.)

8. Докажите, что $$(A_1\hm\cap\ldots\hm\cap A_n)\hm\bigtriangleup (B_1\hm\cap\ldots\hm\cap B_n)\hm\subset (A_1\hm\bigtriangleup B_1)\hm\cup\ldots\hm\cup(A_n\hm\bigtriangleup B_n)$$ для любых множеств $$A_1,\dots,A_n$$ и $$B_1,\dots,B_n$$.

9.Докажите, что если какое-то равенство (содержащее переменные для множеств и операции $$\cap$$, $$\cup$$, $$\setminus$$ ) неверно, то можно найти контрпример к нему, в котором множества пусты или состоят из одного элемента.

10. Сколько различных выражений для множеств можно составить из переменных $$A$$ и $$B$$ с помощью (многократно используемых) операций пересечения, объединения и разности? (Два выражения считаются одинаковыми, если они равны при любых значениях переменных.) Тот же вопрос для трех множеств и для $$n$$ множеств. (Ответ в общем случае: $$2^{2^n-1}$$.)

11. Тот же вопрос, если используются только операции $$\cup$$ и $$\cap$$. (Для двух и трех переменных это число несложно подсчитать, но общей формулы для $$n$$ переменных не известно. Эту задачу называют также задачей о числе монотонных булевых функций от $$n$$ аргументов.)

12. Сколько существует подмножеств у $$n$$ - элементного множества?

13. Пусть множество $$A$$ содержит $$n$$ элементов, а его подмножество $$B$$ содержит $$k$$ элементов. Сколько существует множеств $$C$$, для которых $$B\hm\subset C\hm\subset A$$?

14. Множество $$U$$ содержит $$2n$$ элементов. В нем выделено $$k$$ подмножеств, причем ни одно из них не является подмножеством другого. Каково может быть максимальное значение числа $$k$$? (Указание. Максимум достигается, когда все подмножества имеют по $$n$$ элементов. В самом деле, представим себе, что мы начинаем с пустого множества и добавляем по одному элементу, пока не получится множество $$U$$. В ходе такого процесса может появиться не более одного выделенного множества; с другой стороны, можно подсчитать математическое ожидание числа выделенных множеств по линейности; вероятность пройти через данное множество $$Z\hm\subset U$$ минимальна, когда $$Z$$ содержит $$n$$ элементов, поскольку все множества данного размера равновероятны.)

Число элементов

Число элементов в конечном множестве $$A$$ называют также его мощностью и обозначают $$|A|$$ (а также $$\#A$$ ). (Вскоре мы будем говорить о мощностях и для бесконечных множеств.) Следующая формула позволяет найти мощность объединения нескольких множеств, если известны мощности каждого из них, а также мощности всех пересечений.

Теорема 1. Формула включений и исключений.$$|A\cup B| =|A|+|B|-|A\cap B|;\\ |A\cup B \cup C| =|A|+|B|+|C|-\\ {}-|A\cap B|-|A\cap C|-|B\cap C|+\\ {}+|A\cap B\cap C|;$$ вообще $$|A_1\cup\ldots\cup A_n|$$ равно$$\sum_{i}|A_i| - \sum_{i<j}|A_i \cap A_j| + \sum_{i<j<k} |A_i \cap A_j \cap A_k| - \ldots$$

Доказательство. Это утверждение несложно доказать индукцией по $$n$$, но мы приведем другое доказательство. Фиксируем произвольное множество $$U$$, подмножествами которого являются множества $$A_1, \dots, A_n$$.

Характеристической функцией множества $$X\hm\subset U$$ называют функцию $$\chi_X$$, которая равна $$1$$ на элементах $$X$$ и $$0$$ на остальных элементах $$U$$. Операции над подмножествами множества $$U$$ соответствуют операциям с их характеристическими функциями. В частности, пересечению множеств соответствует произведение характеристических функций: $$\chi_{A\cap B}(u)\hm=\chi_{A}(u)\chi_{B}(u)$$. Дополнению (до $$U$$) соответствует функция $$1-\chi$$, если $$\chi$$ - характеристическая функция исходного множества.

Число элементов множества можно записать как сумму значений его характеристической функции:$$|X|=\sum_{u} \chi_{X}(u).$$ Объединение $$A_1\cup\ldots\cup A_N$$ можно записать как дополнение к пересечению дополнений множеств $$A_i$$ ; в терминах характеристических функций имеем$$\chi_{A_1\cup\ldots\cup A_n}= 1 - (1-\chi_{A_1})\ldots (1-\chi_{A_n}).$$ Раскрыв скобки в правой части, мы получим$$\sum_{i}\chi_{A_i}-\sum_{i<j}\chi_{A_i}\chi_{A_j}+ \sum_{i<j<k}\chi_{A_i}\chi_{A_j}\chi_{A_k}-\ldots$$ и просуммировав левую и правую часть по всем элементам $$U$$ (обе они есть функции на $$U$$ ), получим формулу включений и исключений.

15. Докажите, что $$|A_1\bigtriangleup\ldots\bigtriangleup A_n|$$ равно

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

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

Вот несколько примеров использования этого принципа.

16. На окружности выбраны 1000 белых точек и одна черная. Чего больше - треугольников с вершинами в белых точках или четырехугольников, у которых одна вершина черная, а остальные три белые? (Решение: их поровну, поскольку каждому четырехугольнику соответствует треугольник, образованный тремя его белыми вершинами.)

17. Каких подмножеств больше у $$100$$ - элементного множества: мощности $$57$$ или мощности $$43$$? (Указание: $$57\hm+43\hm=100$$.)

18. Докажите, что последовательностей длины $$n$$, составленных из нулей и единиц, столько же, сколько подмножеств у множества $$\{1,2,\dots,n\}$$. (Указание: каждому подмножеству $$X\hm\subset\{1,2,\dots,n\}$$ соответствует " характеристическая последовательность", на $$i$$ - м месте которой стоит единица, если и только если $$i\hm\in X$$.)

19. Докажите, что последовательностей нулей и единиц длины $$n$$, в которых число единиц равно $$k$$, равно числу $$k$$ - элементных подмножеств $$n$$ - элементного множества.

Это число называется числом сочетаний из n по k и обозначается $$C_n^k$$ в русских книжках; в иностранных обычно используется обозначение $$\binom{n}{k}$$.

20. Докажите, что $$C_n^k\hm=C_n^{n-k}$$.

21. Докажите, что $$C_n^0\hm+C_n^1\hm+\ldots\hm+C_n^n\hm=2^n$$.

22. Пусть $$U$$ - непустое конечное множество. Докажите, что подмножеств множества $$U$$, имеющих четную мощность, столько же, сколько имеющих нечетную мощность. (Указание: фиксируем элемент $$u\hm\in U$$ и объединим в пары подмножества, отличающиеся только в точке $$u$$.

23. Докажите, что $$C_n^0\hm-C_n^1\hm+C_n^2\hm-\ldots\hm+(-1)^nC_n^n\hm=0$$. (Указание: как это связано с предыдущей задачей?)

24. Докажите формулу бинома Ньютона:$$(a+b)^n= C_n^0 a^n + C_n^1 a^{n-1}b + \ldots+C_n^k a^{n-k}b^{k}+\ldots+C_n^n b^n.$$

25. Докажите, что способов расстановки скобок (указывающих порядок действий) в неассоциативном произведении из $$n$$ элементов столько же, сколько способов разбить выпуклый $$(n+1)$$ - угольник на треугольники непересекающимися диагоналями. (Для произведения трех множителей есть два варианта $$(ab)c$$ и $$a(bc)$$ ; с другой стороны, есть два способа разрезать четырехугольник на два треугольника, проведя диагональ. Для произведения четырех сомножителей и для пятиугольника имеется по $$5$$ вариантов.)

Равномощные множества

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

Для конечных множеств это означает, что в них одинаковое число элементов, но определение имеет смысл и для бесконечных множеств. Например, отрезки $$[0,1]$$ и $$[0,2]$$ равномощны, поскольку отображение $$x\hm\mapsto 2x$$ осуществляет искомое соответствие.

26. Докажите, что любые два интервала $$(a,b)$$ и $$(c,d)$$ на прямой равномощны.

27. Докажите, что любые две окружности на плоскости равномощны. Докажите, что любые два круга на плоскости равномощны.

28. Докажите, что полуинтервал $$[0,1)$$ равномощен полуинтервалу $$(0,1]$$.

Несколько более сложна такая задача: доказать, что интервал $$(0,1)$$ и луч $$(0,+\infty)$$ равномощны. Это делается так. Заметим, что отображение $$x\hm\mapsto 1/x$$ является взаимно однозначным соответствием между $$(0,1)$$ и $$(1,+\infty)$$, а $$x\hm\mapsto (x-1)$$ - взаимно однозначным соответствием между $$(1,+\infty)$$ и $$(0,+\infty)$$, поэтому их композиция $$x\hm\mapsto (1/x)-1$$ является искомым взаимно однозначным соответствием между $$(0,1)$$ и $$(0,+\infty)$$.

Вообще, как говорят, отношение равномощности есть отношение эквивалентности. Это означает, что оно рефлексивно (каждое множество равномощно самому себе), симметрично (если $$A$$ равномощно $$B$$, то и $$B$$ равномощно $$A$$ ) и транзитивно (если $$A$$ равномощно $$B$$ и $$B$$ равномощно $$C$$, то $$A$$ равномощно $$C$$ ). Свойством транзитивности мы только что воспользовались, взяв луч $$(1,+\infty)$$ в качестве промежуточного множества.

Еще несколько примеров:

Мы продолжим этот список, но сначала полезно доказать несколько простых фактов о счетных множествах (равномощных множеству натуральных чисел).