Дискретная математика. Теория множеств

1. Дискретная математика.

Теория множеств
1

2. Теория множеств

Множества
Операции над множествами
Упорядоченные множества
Соответствия
Отображения и функции
Отношения
2

3. Множества. Основные понятия

Множество - совокупность определенных,
вполне различаемых объектов,
рассматриваемых как целое.
Элемент множества отдельный объект множества.
Пустое множество множество не содержащее элементов.
Универсальное множество (универсум)
U - множество содержащее все возможные
элементы в рамках заданного рассмотрения
Мощность множества |M|
количество элементов множества.
3

4. Способы задания множеств

Перечисление элементов
М = {a1, a2, a3, …, ak}
M9 = {1, 2, 3, 4, 5, 6, 7, 8, 9}
Выделение определяющего свойства
M = {x | P(x)}
M9 = {n | n & n < 10}
Определение порождающей процедуры
M = {x | x = f}
M9 = {n | for n from 1 to 9 write n}
4

5.

Глава 1. Теория множеств
1.1. Множество и его мощность
Георг Кантор в конце 19 века создал современную теорию множеств.
• Множество состоит из элементов.
• «Множество есть многое, мыслимое как единое».
• Множество может быть конечным или бесконечным.
• Множества можно сравнивать по «мощности».
Способы задания множеств.
• Конечное множество можно задать перечислением его элементов.
{5, 2, 3} – множество из трех элементов
{} – пустое множество
• Множество можно задать предикатом (характеристической функцией)
{x | x - четно} – множество четных чисел
{f | f : N N} – множество функций из N в N, где N – мн-во натуральных чисел
• Конечное или счетное множество можно задать алгоритмом порождения.
{f1 = f2 = 1; fn+2 = fn + fn+1} – множество чисел Фибоначчи
Способ задания множеств с помощью предикатов – самый общий,
но и самый ненадежный (может приводить к парадоксам).
Кубенский А.А. Дискретная математика.
Глава 1. Теория множеств.
5

6.

Обозначения и понятия «наивной» теории множеств.
a A
a есть элемент A, принадлежит A
a A
a не принадлежит A
A B
A есть подмножество B: (x A) (x B)
пустое множество
Парадоксы «наивной» теории множеств.
«Парадокс брадобрея»
Брадобрей бреет тех и только тех жителей деревни, которые не бреются сами.
Бреет ли брадобрей себя самого?
«Парадокс самопринадлежности»
Назовем множество «правильным», если оно не содержит самого себя в качестве
элемента. Правильно ли множество всех правильных множеств?
Пусть M = { X | X X }
Тогда: M M
M M; M M
M M
Способы преодоления парадоксов.
Ограничиться только «конструктивно порождаемыми» множествами.
Ограничиться только подмножествами хорошо известных «универсальных» множеств.
Кубенский А.А. Дискретная математика.
Глава 1. Теория множеств.
6

7.

Операции над множествами.
Операции можно выполнять над множествами, если они принадлежат
одному и тому же универсуму
A B
A B
Объединение множеств
Пересечение множеств
A\B
A=U\A
Разность множеств
Дополнение до универсума
AˣB
Прямое произведение
Кубенский А.А. Дискретная математика.
Глава 1. Теория множеств.
7

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

Объединением множеств А и В называется
множество, состоящее из всех тех и только
тех элементов, которые принадлежат хотя бы
одному из множеств А или В.
Свойства
рефлексивность
коммутативность
ассоциативность
свойство 0
свойство 1
А А=A
А В=В А
А (В С) = (А В) С = А В С
А =А
А U=U
А
А В
В
8

9. Объединение N множеств

Операция объединения может быть
распространена на N множеств. Тогда
записывают:
С
А1
...
А2
АN
n
или C
k 1
A
k
9

10. Пример операции объединения

ПРИМЕР 1: {1,2,3}
{2,3,4}= {1,2,3,4}
ПРИМЕР 2: А – множество компонентов резисторов,
В – множество компонентов диодов, тогда
объединение А и В – это множество С
компонентов, которые являются либо резисторами
либо диодами
А
B
10

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

A A A
A A B
B A B
11

12. Объединение N множеств

Операция объединения может быть
распространена на N множеств. Тогда
записывают:
С
А1
...
А2
АN
n
или C
k 1
A
k
12

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

Пересечением множеств А и В называется
множество, состоящее из всех тех и только тех
элементов, которые принадлежат как
множеству А, так и множеству В.
Свойства
рефлексивность
коммутативность
ассоциативность
свойство 0
свойство 1
А А=A
А В=В А
А (В С) = (А В) С = А В С
А =
А U=А
А
А В
В
13

14. Операция пересечения или умножения

ОПРЕДЕЛЕНИЕ: если даны два множества А и В, то
пересечением их будет называться множество С, которое
будет состоять из элементов принадлежащих
одновременно множеству А и множеству В.
С А В
С=А В
Знак пересечения
14

15. Пример операции пересечения

ПРИМЕР:
{1,2,3}
{2,3,4} ={2, 3}
А
С
В
15

16. СЛЕДСТВИЯ операции пересечения

1.
2.
3.
A A A
( A B) A
( A B) B
Для некоторой пары множеств может оказаться, что их пересечение
равно пустому множеству. НАПРИМЕР А={1,2,3} В={4,5,6}, то пересечение
А с В равно пустому множеству.
А
В
А В
16

17. Непересекающиеся множества

Множества, пересечение которых,
является пустым множеством называются
непересекающимися.
ПРИМЕР 1: А – множество целых положительных
чисел, В – множество целых отрицательных
чисел. А и В – непересекающиеся множества.
ПРИМЕР 2: А – множество людей старше 20 лет,
В – множество людей младше 15 лет.
17

18. Пересечение N множеств

Операция пересечения может быть
распространена на N множеств. Тогда
записывают
А А ... А
или С A
С
1
2
N
n
k 1
а
с
k
в
н
18

19. Разность

Разностью множеств А и В называется
множество, состоящее из всех тех и только тех
элементов, которые принадлежат множеству А
и не принадлежат множеству В.
Свойства
А\ =А
А\U=
свойство 0
свойство 1
\А=
U\А=A
А
А\В
В
19

20. Вычитание множеств

ОПРЕДЕЛЕНИЕ: Разностью множеств А и
В называется совокупность тех элементов
множества А, которые не являются
элементами множества В.
B
А\В
A
Обозначение разности
20

21. Варианты вычитания множеств

1
2
3
А
В
А
В
А
В
21

22. Симметричная разность или кольцевая сумма

ОПРЕДЕЛЕНИЕ: Симметричной разностью множеств А и
В называется совокупность тех элементов множества А и
В, которые не являются одновременно элементами
множества А и В.
А Вили
Обозначение кольцевой суммы
А В
А
В
22

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

Симметрической разностью множеств А и В
называется множество, состоящее из всех тех
и только тех элементов, которые принадлежат
объединению множеств А и В, и не
принадлежат их пересечению.
Свойства
коммутативность
ассоциативность
свойство 0
свойство 1
А/В=В/А
А / (В/С) = (А/В) / С = А / В / С
А/ =А
А/U=A
В
А
23

24. Симметричная разность или кольцевая сумма

ОПРЕДЕЛЕНИЕ: Симметричной разностью множеств А и
В называется совокупность тех элементов множества А и
В, которые не являются одновременно элементами
множества А и В.
А Вили
Обозначение кольцевой суммы
А В
А
В
24

25. Дополнение

Дополнением множества А до универсального
множества называется множество, состоящее
из всех тех и только тех элементов, которые
принадлежат универсальному множеству, и не
принадлежат множеству А.
Свойства
А =U A
инволютивность
А =
A
A =А
U
A
A
25

26. Сравнение множеств

Два множества равны между собой,
если они состоят из одних и тех же
элементов
Свойства: для любых трех множеств X, Y, Z верно
рефлексивность
X = X;
коммутативность
транзитивность
X = Y Y = X;
(X = Y) & (Y = Z) X = Z.
(идемпотентность)
Множество X является подмножеством
множества Y, если любой элемент множества
X принадлежит и множеству Y.
X Y, если x X и x Y;
Свойства:
рефлексивность
транзитивность
свойства 0 и 1
X Y, если X Y и X Y
X X
X Y & Y Z, X Z
Y U
26

27. Границы множества

Если множество конечно и состоит из
элементов, сравнимых между собой, то
существуют наибольший и наименьший
элементы такого множества.
Если множество бесконечно и состоит из
элементов, сравнимых между собой, то
существуют границы этого множества:
верхняя и нижняя.
S = {x R| a<x<b}
S = ]a,b[
a = inf S
('инфинум)
b = sup S
(супр'емум)
27

28. Теорема о границах

Если В А, то inf В inf А; sup В sup А.
Доказательство:
Пусть b' B и b' = inf B; т.к. В А b' А.
Пусть a' A и a' = inf A; при этом
если a' = b', то b' = a'=inf А;
а
если a' b', то b' = inf B > a'=inf А.
Пусть b" B и b" = sup B; т.к. В А b" А.
Пусть a" A и a" = sup A; при этом
b" = a", то a"=sup А = b"=sup B;
а
b" a", то a"=sup А > b".
если
если
A
a'
b'
b" a"
28

29.

Мощность множеств. Сравнение мощностей.
Два множества называются равномощными, если существует взаимнооднозначное
соответствие между элементами первого и второго множеств.
|M|, card M
|A| = |B|
- обозначения для мощности множества
- множества A и B – равномощны.
Определение: Конечные множества A и B равномощны тогда и только тогда, когда они имеют
одинаковое число элементов. Это число называется мощностью конечного множества.
N - множество всех натуральных чисел и нуля
E - множество всех четных неотрицательных чисел
E N, |E| = |N|, соответствие: x N
2x E
Множество M бесконечно тогда и только тогда, когда оно равномощно своему собственному
подмножеству: A M, A M, |A| = |M|. Можно считать это определением бесконечности.
Определение: Множество называется счетным, если оно равномощно множеству N.
Размещение постояльцев в межзвездной гостинице Ийона Тихого.
Определение: |A| < |B|, если |A| |B|, но существует C B такое, что |A| = |C|.
Кубенский А.А. Дискретная математика.
Глава 1. Теория множеств.
29

30.

Сравнение мощностей.
Часто можно определить, что два множества равномощны, пользуясь определением
равномощности непосредственно.
Пусть M
Утверждение:
- счетное множество. Рассмотрим множество M 2 = M2
множества M и M2 – равномощны.
Доказательство: счетное множество можно «пересчитать», то есть построить соответствие
его элементов элементам множества N. «Пересчитаем» элементы множества M2.
M = { m1, m2, m3, … }
M2 = { m11, m21, m31, …
m12, m22, m32, … }
= { m11, m12, m21, m22, m31, m32, … }
Аналогично можно показать, что для любого k множество M k будет также счетным.
Утверждение:
множество M M – счетно.
m11, m21, m31, …, mn1, …
m12, m22, m32, …, mn2, …
m13, m23, m33, …, mn3, …
…
m1k, m2k, m3k, …, mnk, …
Нумерация «в столбик» не получается. Применим
«диагональную нумерацию».
m11, m21, m12,
m31, m32, m13,
…
Кубенский А.А. Дискретная математика.
Глава 1. Теория множеств.
30

31.

31

32.

Сравнение мощностей (продолжение).
Определение: Мощность множества всех вещественных чисел называется
мощностью континуума.
Мощностью континнума обладает любой отрезок или интервал на вещественной оси,
например, (0, 1). Как это доказать?
Эквивалентные преобразования интервалов:
сдвиг (x x+α); растяжение (x αx); инверсия (x 1/x).
(0, 1)
(сдвиг)
(инверсия)
(-0.5, 0.5)
(разбиение)
(-∞, -2) [0] (2, ∞)
(-0.5, 0) [0] (0, 0.5)
(сдвиг, слияние)
(-∞, ∞)
Пользоваться определением для сравнения мощностей не всегда удобно.
Пример: попробуйте доказать, опираясь только на определение, что мощность множества
чисел отрезка [0, 1] равна мощности континуума.
Кубенский А.А. Дискретная математика.
Глава 1. Теория множеств.
32

33.

Сравнение мощностей (продолжение).
Теорема (без доказательства): пусть A' A и B' B таковы, что |A'| = |B| и
|B'| = |A|. Тогда множества A и B равномощны, то есть |A| = |B|.
A
A'
B
B'
С помощью этой теоремы легко доказать, что множество мощности континнума объединенное
с конечным числом элементов имеет мощность континнума
(будем коротко говорить (континуум) + (конечное) = (континуум)),
поскольку интервал плюс конечное число точек легко погрузить в другой интервал
Кубенский А.А. Дискретная математика.
Глава 1. Теория множеств.
33

34.

Сравнение мощностей (продолжение).
Аналогично, (континуум) + (счетное) = (континуум),
поскольку счетное число точек, например, вида 1/i, все лежат на отрезке [0, 1].
(
)
(
)
Упражнение: доказать, что (континуум) (континуум) = (континуум),
Вопрос: верно ли, что (счетное) = (континуум) ?
Кубенский А.А. Дискретная математика.
Глава 1. Теория множеств.
34

35.

Теорема Кантора.
Для каждого множества A можно рассмотреть множество всех его подмножеств.
Такое множество называется булеаном исходного множества и обозначается 2A.
Теорема: если множество A – конечно, то |2A| = 2|A|.
Доказательство: индукцией по количеству элементов множества.
1.
2.
|A| = 0 2A = { } |2A| = 1 = 2|A|.
|A| = k+1 выберем первый элемент и составим всевозможные подмножества из
остальных элементов, по индукционному предположению их будет 2k.
Кроме этих подмножеств, можно получить еще столько же, добавив в
уже имеющиеся множества первый элемент. Всего получится 2 * 2k = 2k+1.
С точки зрения теории множеств целое число k – это класс всех множеств элементов мощности k.
k
Тогда 2 – множество мощности 2k.
Только что доказанная теорема является обоснованием обозначения 2A для конечных множеств.
Существуют ли бесконечные множества неодинаковой мощности?
Кубенский А.А. Дискретная математика.
Глава 1. Теория множеств.
35

36.

Доказательство теоремы Кантора
Теорема (Г.Кантор): если множество A – счетно, то |2A| > |A|.
Занумеруем элементы счетного множества A:
a1, a2, a3, …, an, …
Тогда любое подмножество множества A – выборка номеров элементов – может быть
представлена последовательностью из нулей и единиц, например:
a1, a3, a5, …, a2k+1, …
Пустое множество
будет представлена последовательностью 1, 0, 1, 0, 1, 0,…
будет представлено последовательностью 0, 0, 0, 0, 0, 0,…
Очевидно, что множество всех бесконечных последовательностей нулей и единиц – бесконечно.
Допустим, что это множество – счетно.
b11, b21, b31, …, bn1, …
b12, b22, b32, …, bn2, …
b13, b23, b33, …, bn3, …
…
b1k, b2k, b3k, …, bnk, …
…
Построим «диагональную» последовательность
b11
b22
b33
1-b11,
bkk
1-b22,
1-b33,
…
1-bkk,
…
Очевидно, что она отличается от любой из занумерованных последовательностей, например,
от последовательности с номером k: b1k, b2k, b3k, …, bnk, …
она заведомо отличается в k-м элементе: bkk 1-bkk.
Полученное противоречие доказывает теорему.
Кубенский А.А. Дискретная математика.
Глава 1. Теория множеств.
36

37.

Доказательство теоремы Кантора (продолжение)
Теорема (Г.Кантор): для любого множества A мощность его булеана больше мощности
самого множества: |2A| > |A|.
Доказательство проводится по той же схеме от противного:
пусть некоторое множество A равномощно своему булеану
|A| = |2A|
Тогда существует взаимнооднозначная функция такая, что a A
(a) A
Построим множество D A D = { b | b (b) }
Тогда очевидно, что не существует такого d, что (d) = D,
так как невозможно ответить на вопрос «верно ли, что d D?»
Если d D, то d (d) = D
Если d D = (d) , то d D
Полученное противоречие доказывает теорему.
Заметим, что каждой последовательности из нулей и единиц соответствует вещественное
число из диапазона [0, 1]
1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0…
0,110001001100…
При этом существует лишь счетное число пар последовательностей, которым соответствует
одно и то же рациональное число.
1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0…
1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1…
Кубенский А.А. Дискретная математика.
Глава 1. Теория множеств.
0,110001
2N = C
37

38.

Некоторые следствия теоремы Кантора
1.
Поскольку 2N = C, то C > N. (N – мощность счетного множества, C – мощность континуума)
2.
Существует бесконечно много бесконечных множеств с различными мощностями.
Например, построим следующую цепочку мощностей множеств:
‫א‬0 = N, ‫א‬1 = 2N = C, ‫א‬2 = 2C , …
В этой цепочке каждая следующая мощность больше предыдущей (последовательность
трансфинитных кардинальных чисел).
Гипотеза континуума: не существует бесконечного несчетного множества, имеющего
мощность, меньшую мощности континуума.
Обозначение: для любых двух множеств A и B обозначим через AB множество всех всюду
определенных функций из B в A. AB = { f | f : B A }
Согласуются ли два определения для обозначения 2A ?
1.
2A – множество всех подмножеств множества A.
2.
2A – множество всех функций из A в 2 = {0, 1}.
Очевидно, да, поскольку каждой такой функции соответствует подмножество всех элементов
множества A, имеющих образ 1, и наоборот, каждому подмножеству A можно сопоставить
функцию, отображающую элементы этого подмножества в 1, а остальные – в 0.
Кубенский А.А. Дискретная математика.
Глава 1. Теория множеств.
38

39.

Декартово произведение множеств
Декартово произведение множеств:
A B
=
{ (a, b) | a A, b B }
Степень множеств:
A A
=
A2
An = A A ... A
n раз
An – это множество всех кортежей вида (a1, a2,... an), где все ai принадлежат A.
Согласуется ли это обозначение с введенным ранее обозначением MN для множества всех
всюду определенных функций из N в M?
Согласно этому определению An = { f | f : {1,2,…,n} A }
Всякая такая функция f ставит в соответствие каждому числу из интервала [1, n] элемент
множества A, то есть i ai. Таким образом, функция f может быть представлена набором
из n элементов множества A. Так что множество всех таких функций – это множество всех
кортежей вида (a1, a2,... an).
Кубенский А.А. Дискретная математика.
Глава 1. Теория множеств.
39