Файл: Учебник издание шестое Рекомендовано Министерством образования и науки Российской Федерации в качестве учебника для студентов высших технических учебных заведений.pdf

1.1. МНОЖЕСТВА И ОСНОВНЫЕ ОПЕРАЦИИ НАД НИМИ
11
Мы будем использовать следующие обозначения для числовых множеств:
N или ω — множество натуральных чисел, Z — множество целых чисел,
Q — множество рациональных чисел, R — множество вещественных чисел,
C — множество комплексных чисел.
Пример 1.1.1. Множество M арабских цифр можно задать двояко: пе- речислением — M = {0, 1, 2, . . . , 9} или посредством свойства —
M = {x | x — арабская цифра}. ¤
Пример 1.1.2. Множество нечетных чисел {±1, ±3, ±5, . . .} можно определить как {x | x = 2k + 1 для некоторого k ∈ Z}. ¤
Способ задания множества с помощью свойств таит некоторые опасно- сти, поскольку “неправильно” заданные свойства могут привести к проти- воречию. Приведем один из наиболее типичных теоретико-множественных парадоксов — парадокс Рассела. Рассмотрим множество всех множеств, ко- торые не являются своими собственными элементами: K ­ {M | M /
∈ M}.
Спросим теперь, является ли множество K своим элементом? Если K ∈ K,
то должно выполняться свойство, задающее множество K, т. е. K /
∈ K,
что приводит к противоречию. Если же K /
∈ K, то, поскольку выполняется свойство, задающее K, приходим к тому, что K ∈ K, а это противоречит предположению. Таким образом, не всякое свойство приводит к осмыслен- ному заданию множества. В конце настоящей главы мы рассмотрим систему аксиом теории множеств, исключающую подобные парадоксы.
Множество

12
Глава 1. ЭЛЕМЕНТЫ ТЕОРИИ МНОЖЕСТВ
Пример 1.1.3. Справедливы следующие включения: N ⊆ Z, Z ⊆ Q,
Q ⊆ R, R ⊆ C. ¤
Пример 1.1.4. Покажем, что множества M
1
­ {x | sin x = 1} и M
2
­
­ {x | x =
π
2
+ 2kπ, k ∈ Z} совпадают.
Действительно, если x ∈ M
1
, то x является решением уравнения sin x = 1.
Но это значит, что x можно представить в виде x =
π
2
+2kπ и поэтому x ∈ M
2
Таким образом, M
1
⊆ M
2
. Если же x ∈ M
2
, т. е. x =
π
2
+ 2kπ, то sin x = 1,
т. е. M
2
⊆ M
1
. Следовательно, M
1
= M
2
. ¤
Запись A ⊂ B или A B означает, что A ⊆ B и A 6= B (A не равно B),
и в этом случае будем говорить, что A строго включено в B, или является
собственным подмножеством B. Так, включения из примера 1.1.3 являют- ся строгими.
Заметим, что X ⊆ X; если X ⊆ Y и Y ⊆ Z, то X ⊆ Z; если X ⊆ Y
и Y ⊆ X, то X = Y .
Не следует смешивать отношение принадлежности ∈ и отношение вклю- чения ⊆. Хотя 0 ∈ {0} и {0} ∈ {{0}}, неверно, что 0 ∈ {{0}}, поскольку единственным элементом множества {{0}} является {0}.
Совокупность всех подмножеств множества A называется его булеаном
или множеством-степенью и обозначается через P(A) или 2
A
. Таким об- разом, P(A) ­ {B | B ⊆ A}.
Мы будем предполагать, что существует множество, не содержащее ни од- ного элемента, которое называется пустым и обозначается через ∅. Ясно,
что ∅ ⊆ A для любого множества A.
Пример 1.1.5. Если A = {1, 2, 3}, то
P(A) = {∅, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, A}. ¤
Множество, содержащее все элементы, находящиеся в рассмотрении, на- зывается универсальным или универсумом и обозначается через U. Рассмот- рим операции на булеане P(U). Если A, B ∈ P(U), то пересечение A ∩ B
и объединение A ∪ B множеств A и B определяются равенствами
A ∩ B ­ {x | x ∈ A и x ∈ B},
A ∪ B ­ {x | x ∈ A или x ∈ B}.

1.1. МНОЖЕСТВА И ОСНОВНЫЕ ОПЕРАЦИИ НАД НИМИ
13
Пересечение множеств A и B называется также их произведением и обозна- чается A · B, а объединение — суммой: A + B. Множество
A \ B ­ A − B ­ {x | x ∈ A и x /
∈ B}
называется разностью множеств A и B, множество
A ⊕ B ­ A ÷ B ­ (A \ B) ∪ (B \ A) —
кольцевой суммой, или симметрической разностью множеств A и B, а мно- жество A ­ U \ A — дополнением множества A в U (см. рис. 1.1, на котором изображены так называемые диаграммы Эйлера—Венна, наглядно поясня- ющие соотношения между множествами).
Пример 1.1.6. Докажем, что A \ B = A ∩ B.
Сначала установим, что A \ B ⊆ A ∩ B. Пусть x — произвольный элемент
A\B. Тогда по определению разности множеств имеем x ∈ A и x /
∈ B, отсюда
x ∈ A и x ∈ B, значит, x ∈ A ∩ B. Теперь покажем, что A ∩ B ⊆ A \ B. Если
x ∈ A ∩ B, то x ∈ A и x ∈ B, поэтому x ∈ A и x /
∈ B, значит, x ∈ A \ B.
На основании включений A \ B ⊆ A ∩ B и A ∩ B ⊆ A \ B делаем вывод, что
A \ B = A ∩ B. ¤
Аналогично примеру 1.1.6 устанавливаются следующие основные свой- ства операций объединения, пересечения и дополнения:
½¼
¾»
U
A
½¼
¾»
U
A
½¼
¾»
U
A
"!
#Ã
B
"!
#Ã
B
"!
#Ã
B
A ∪ B
A ∩ B
A \ B
A ⊕ B
A
½¼
¾»
U
A
½¼
¾»
U
A
"!
#Ã
B
Рис. 1.1

14
Глава 1. ЭЛЕМЕНТЫ ТЕОРИИ МНОЖЕСТВ
1. Ассоциативность операций ∪ и ∩:
(A ∪ B) ∪ C = A ∪ (B ∪ C), (A ∩ B) ∩ C = A ∩ (B ∩ C).
2. Коммутативность операций ∪ и ∩:
A ∪ B = B ∪ A, A ∩ B = B ∩ A.
3. Законы идемпотентности
A ∪ A = A, A ∩ A = A.
4. Законы дистрибутивности
A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C),
A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C).
5. Законы поглощения
A ∪ (A ∩ B) = A, A ∩ (A ∪ B) = A.
6. Законы де Моргана
A ∪ B = A ∩ B, A ∩ B = A ∪ B.
7. Законы нуля и единицы: положим 0 ­ ∅, 1 ­ U, тогда
A ∪ 0 = A, A ∩ 0 = 0, A ∪ 1 = 1, A ∩ 1 = A,
A ∪ A = 1, A ∩ A = 0.
8. Закон двойного отрицания
A = A.
Отметим, что на основании примера 1.1.6 операция \ выражается через операции ∩ и . По закону де Моргана и закону двойного отрицания справед- ливо соотношение A∪B = A ∩ B, т. е. операция ∪ также выражается через операции ∩ и
. По определению операция ⊕ тоже выражается через
∩ и
. Таким образом, любая из определенных операций над множествами выражается через операции ∩ и .

1.1. МНОЖЕСТВА И ОСНОВНЫЕ ОПЕРАЦИИ НАД НИМИ
15
Пересечение и объединение могут быть определены для любого мно- жества множеств A
i
, где индексы i пробегают множество I. Пересечение
∩ {A
i
| i ∈ I} и объединение ∪ {A
i
| i ∈ I} задаются равенствами
∩ {A
i
| i ∈ I} ­ {x | x ∈ A
i
для всех i ∈ I},
∪ {A
i
| i ∈ I} ­ {x | x ∈ A
i
для некоторого i ∈ I}.
Вместо ∩ {A
i
| i ∈ I} и ∪ {A
i
| i ∈ I} часто пишут соответственно ∩
i∈I
A
i
и ∪
i∈I
A
i
, а иногда просто ∩A
i
, ∪A
i
, если из контекста ясно, какое множество I
имеется в виду. Если I = {1, 2, . . . , n}, то используются записи
A
1
∩ A
2
∩ . . . ∩ A
n
, A
1
∪ A
2
∪ . . . ∪ A
n
,
а также
n
∩
i=1
A
i
и
n
∪
i=1
A
i
Множество {A
i
| i ∈ I} непустых подмножеств множества A называется
покрытием множества A, если A = ∪
i∈I
A
i
. Покрытие называется разбиени-
ем, если A
i
∩ A
j
= ∅ при i 6= j. Другими словами, множество {A
i
| i ∈ I}
непустых подмножеств множества A является его разбиением, если каждый элемент x ∈ A принадлежит в точности одному из подмножеств A
i
, каждое из которых не является пустым.
Предложение 1.1.1. Следующие условия эквивалентны:
(1) A ⊆ B; (2) A ∩ B = A; (3) A ∪ B = B; (4) A \ B = ∅; (5) A ∪ B = U.
Доказательство. (1) ⇒ (2). Так как A ∩ B ⊆ A, то достаточно пока- зать, что A ⊆ B влечет A ⊆ A ∩ B. Но если x ∈ A, то по условию x ∈ B,
и, следовательно, x ∈ A ∩ B.
(2) ⇒ (3). Так как A ∩ B = A, то A ∪ B = (A ∩ B) ∪ B. По закону поглощения и закону коммутативности имеем A ∪ B = B.
(3) ⇒ (4). Предположим, что A∪B = B. Так как A\B = A∩B, то по зако- ну де Моргана, закону ассоциативности, закону коммутативности и законам нуля и единицы имеем
A \ B = A ∩ (A ∪ B)A ∩ (A ∩ B) = (A ∩ A) ∩ B = 0 ∩ B = ∅.
(4) ⇒ (5). Предположим, что A \ B = ∅, т. е. A ∩ B = ∅. Тогда A ∩ B =
= 0 = 1. По закону де Моргана и закону двойного отрицания получаем
U = 1 = A ∩ B = A ∪ B = A ∪ B.

16
Глава 1. ЭЛЕМЕНТЫ ТЕОРИИ МНОЖЕСТВ
(5) ⇒ (1). Предположим, что A∪B = U и не выполняется условие A ⊆ B,
т. е. найдется элемент x такой, что x ∈ A и x /
∈ B. Тогда x /
∈ A и, значит,
x /
∈ A ∪ B, а это противоречит равенству A ∪ B = U. ¤
Упорядоченную последовательность из n элементов x
1
, x
2
, . . . , x
n
бу- дем обозначать через (x
1
, x
2
, . . . , x
n
) или hx
1
, x
2
, . . . , x
n
i. Здесь круглые или угловые скобки используются для того, чтобы указать на порядок, в ко- тором записаны элементы. Будем называть такую последовательность упо-
рядоченным набором длины n, кортежем длины n или просто n-кой. Длина кортежа x ­ hx
1
, x
2
, . . . , x
n
i обозначается через l(x). Элемент x
i
называ- ется i-й координатой кортежа x. В теории множеств кортежи кодируются с помощью операции взятия множества по двум элементам в соответствии со следующими правилами: h i ­ ∅, hx
1
i ­ x
1
, hx
1
, x
2
i ­ {{x
1
}, {x
1
, x
2
}},
hx
1
, x
2
. . . , x
n+1
i ­ hhx
1
, x
2
. . . , x
n
i, x
n+1
i.
Заметим, что две n-ки x = (x
1
, x
2
, . . . , x
n
) и y = (y
1
, y
2
, . . . , y
n
) равны
(x = y) тогда и только тогда, когда x
1
= y
1
, x
2
= y
2
, . . ., x
n
= y
n
Пример 1.1.7. Пары (1, 2) и (2, 1) не совпадают, хотя множества {1, 2}
и {2, 1} равны. ¤
Декартовым (прямым) произведением множеств A
1
, A
2
, . . ., A
n
называ- ется множество {(x
1
, x
2
, . . . , x
n
) | x
1
∈ A
1
, x
2
∈ A
2
, . . . , x
n
∈ A
n
}, обознача- емое через A
1
× A
2
× · · · × A
n
или
n
Q
i=1
A
i
. Если A
1
= A
2
= . . . = A
n
= A,
то множество A
1
× A
2
× . . . × A
n
называется n-й декартовой степенью мно-
жества A и обозначается через A
n
. Положим по определению A
0
­ {∅}.
Пример 1.1.8. Для множеств A = {1, 2} и B = {3, 4} имеем A × B =
= {(1, 3), (1, 4), (2, 3), (2, 4)}, B×A = {(3, 1), (3, 2), (4, 1), (4, 2)}, A
2
= A×A =
= {(1, 1), (1, 2), (2, 1), (2, 2)}. ¤
Пример 1.1.9 (шахматная доска). Рассмот-
6
-
y
x
0 1
1
Рис. 1.2
рим два множества
A = {a, b, c, d, e, f, g, h}
и B = {1, 2, 3, 4, 5, 6, 7, 8}. Тогда множеству пар (x, y) ∈ A × B соответствует множество кле- ток шахматной доски. ¤
Пример 1.1.10. Множество [0, 1]
2
равно мно- жеству {(a, b)| 0 6 a 6 1, 0 6 b 6 1}, которому со- ответствует множество точек на плоскости, имею- щих неотрицательные координаты, не превосходящие единицы (рис. 1.2). ¤

1.2. ОТНОШЕНИЯ. ФУНКЦИИ. ВЗАИМНО ОДНОЗНАЧНЫЕ СООТВЕТСТВИЯ
17
§ 1.2.
Отношения. Функции. Взаимно однозначные соответствия
Часто при решении задач необходимо выбирать элементы, связанные некоторым соотношением. Примерами таких связей между элементами мо- гут служить функциональные зависимости или отношение “меньше либо равно”.
Любое подмножество P прямого произведения A
1
× A
2
× . . . × A
n
на- зывается n-местным отношением или n-местным предикатом на множе- ствах A
1
, A
2
, . . . , A
n
. Другими словами, элементы x
1
, x
2
, . . . , x
n
(где x
1
∈ A
1
,
. . . , x
n
∈ A
n
) связаны соотношением P (обозначается P (x
1
, x
2
, . . . , x
n
)) тогда и только тогда, когда (x
1
, x
2
, . . . , x
n
) ∈ P .
При n = 1 отношение P является подмножеством множества A
1
и назы- вается унарным отношением или свойством.
Наиболее часто встречаются двухместные отношения (n = 2). В этом слу- чае они называются бинарными отношениями или соответствиями. Таким образом, соответствием P между множествами A и B является подмноже- ство множества A × B. Если P ⊆ A × B и (x, y) ∈ P , то пишут также x P y.
Отношение P ⊆ A
n
называется n-местным отношением (предикатом)
на множестве A.
Пример 1.2.1. Если A = {2, 3, 4, 5, 6, 7, 8}, то бинарное отношение
P = {(x, y) | x, y ∈ A, x делит y и x 6 3} можно записать в виде P = {(2, 2),
(2, 4), (2, 6), (2, 8), (3, 3), (3, 6)}. ¤
Пример 1.2.2. Рассмотрим отношение P = {(x, y) | x, y ∈ R, x 6 y}
на множестве R. Тогда запись x P y означает, что x 6 y, и в качестве имени
(обозначения) этого отношения можно взять сам символ 6. ¤
Пример 1.2.3 (ход ладьи). Рассмотрим множество шахматных клеток
S = A × B из примера 1.1.9. Определим бинарное отношение C на мно- жестве S по следующему правилу: (c
1
, c
2
) ∈ C тогда и только тогда, когда
c
1
, c
2
∈ S и ладья может пройти с клетки c
1
на клетку c
2
одним ходом на пустой доске (напомним, что ладья за один ход может изменить либо горизонтальную координату, либо вертикальную, но не обе координаты од- новременно). Нетрудно заметить, что
C = {(c
1
, c
2
) | c
1
= (s
1
, t
1
), c
2
= (s
2
, t
2
), s
1
, s
2
∈ A, t
1
, t
2
∈ B,
и (s
1
= s
2
и t
1
6= t
2
) или (s
1
6= s
2
и t
1
= t
2
)}. ¤