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

34
Глава 1. ЭЛЕМЕНТЫ ТЕОРИИ МНОЖЕСТВ
Отметим, что антисимметричность не совпадает с несимметрично- стью. Действительно, отношение P = {(1, 2), (2, 3), (3, 2)} на множестве
A = {1, 2, 3} не симметрично (так как (1, 2) ∈ P , а (2, 1) /
∈ P ) и не анти- симметрично (поскольку 2 6= 3, но (2, 3) ∈ P и (3, 2) ∈ P ). Тождественное отношение id
A
является одновременно симметричным и антисимметричным.
Пример 1.5.4. Проверим, какими свойствами обла-
•
•
•
6
¡
¡
¡
¡
¡
¡
µ
-
±°
²¯
j
2 3
1
Рис. 1.10
дает отношение P ⊆ A
2
, A = {1, 2, 3}, изображенное на рис. 1.10. Составим матрицу отношения P :
[P ] =


0 1 1 0 1 1 0 0 0

 .
Так как в матрице [P ] на главной диагонали имеются ну- левые элементы, отношение P не рефлексивно. Несиммет- ричность матрицы [P ] означает, что отношение P не симметрично. Для проверки антисимметричности вычислим матрицу [P ∩ P
−1
] = [P ] ∗ [P ]
T
Имеем
[P ] ∗ [P ]
T
=


0 1 1 0 1 1 0 0 0

 ∗


0 0 0 1 1 0 1 1 0

 =


0 0 0 0 1 0 0 0 0

 .
Поскольку в полученной матрице все элементы, стоящие вне главной диа- гонали, нулевые, отношение P антисимметрично. Так как [P ◦ P ] = [P ]
(проверьте!), то P ◦ P ⊆ P , т. е. P является транзитивным отношением. ¤
Пример 1.5.5. Отношение < ­ {(x, y) | x, y ∈ Q и x < y} на множестве рациональных чисел Q не рефлексивно, не симметрично, антисимметрично и транзитивно. ¤
Пример 1.5.6. Рассмотрим отношение P = {(x, y) | x, y ∈ Z и x − y < 1}
на множестве целых чисел Z.
Так как x − x = 0 < 1 для любого x ∈ Z, отношение P рефлексивно.
Поскольку (2, 4) ∈ P , а (4, 2) /
∈ P , отношение P не симметрично. Заметим,
что если x − y < 1 и y − x < 1, то x = y, так как из x 6= y следует |x − y| > 1.
Таким образом, отношение P антисимметрично. Предположим теперь, что
(x, y), (y, z) ∈ P , т. е. x − y < 1 и y − z < 1. Имеем x 6 y и y 6 z, тогда
x 6 z, значит, x − z < 1, т. е. (x, z) ∈ P . Следовательно, отношение P
транзитивно. ¤

1.6. ОТНОШЕНИЯ ЭКВИВАЛЕНТНОСТИ И РАЗБИЕНИЯ
35
§ 1.6.
Отношения эквивалентности и разбиения.
Фактор-множества
Отношение P называется отношением эквивалентности (эквивалентно-
стью), если P рефлексивно, симметрично и транзитивно. Эквивалентности часто обозначают символами E и ∼ (тильда): x E y, x ∼ y.
Пример 1.6.1. 1. Отношение равенства x = y является эквивалентно- стью на любом множестве A, так как оно рефлексивно (x = x), симметрично
(x = y ⇒ y = x) и транзитивно (x = y, y = z ⇒ x = z).
2. Отношение подобия на множестве треугольников есть отношение эк- вивалентности.
3. На любом множестве P(U) отношение равномощности |A| = |B|
является отношением эквивалентности (см. § 1.4).
4. Отношение принадлежности к одной студенческой группе на множе- стве студентов НГТУ — отношение эквивалентности.
5. Рассмотрим множество M программ, вычисляющих некоторые функ- ции. Отношение E = {(x, y) | программы x и y вычисляют одну и ту же функцию} является эквивалентностью. ¤
Пусть E — эквивалентность на множестве A. Классом эквивалентно-
сти элемента x ∈ A называется множество E(x) ­ {y | x E y}. Клас- сы эквивалентности E будут также называться E-классами. Множество
A/E ­ {E(x) | x ∈ A} называется фактор-множеством множества A по от- ношению E.
Пример 1.6.2. 1. Для отношения равенства = на множестве A каждый
=-класс состоит только из одного элемента: =(x) = {x} для любого x ∈ A.
Таким образом, фактор-множество A/= имеет вид {{x} | x ∈ A} и, следова- тельно, биективно множеству A.
2. Для отношения принадлежности к одной студенческой груп- пе классом эквивалентности является множество студентов одной группы.
Фактор-множество множества студентов НГТУ по этому отношению экви- валентности представляет собой множество студенческих групп НГТУ. ¤
Предложение 1.6.1. Множество A/E является разбиением множе-
ства A. Обратно, если R = {A
i
} — некоторое разбиение множества A,
то можно задать соответствующее ему отношение эквивалентности E
по следующему правилу:
x E y ⇔ x, y ∈ A
i
для некоторого i.

36
Глава 1. ЭЛЕМЕНТЫ ТЕОРИИ МНОЖЕСТВ
Доказательство. Пусть E — отношение эквивалентности на множе- стве A; A/E — фактор-множество множества A по E. Так как в силу ре- флексивности отношения E выполнимо x ∈ E(x) для любого x ∈ A, то каждое множество из A/E непусто и ∪
x∈A
E(x) = A. Чтобы установить, что
A/E — разбиение множества A, осталось показать, что если E(x)∩E(y) 6= ∅,
то E(x) = E(y).
Пусть z ∈ E(x) ∩ E(y) и u ∈ E(x), т. е. (x, z), (y, z), (x, u) ∈ E. Так как отношение E симметрично, (z, x) ∈ E. Тогда из транзитивности отношения
E следует (y, u) ∈ E, т. е. u ∈ E(y). Таким образом, E(x) ⊆ E(y). Включение
E(y) ⊆ E(x) доказывается аналогично.
Предположим, что E — отношение на множестве A, соответствующее разбиению R = {A
i
}. Рефлексивность и симметричность E очевидны. Пусть теперь x E y и y E z. Тогда x, y ∈ A
i
, y, z ∈ A
j
, где A
i
, A
j
∈ R. Поскольку
y ∈ A
i
и y ∈ A
j
, то A
i
= A
j
. Следовательно, x, z ∈ A
i
и x E z. ¤
Таким образом, существует биекция между множеством всех отноше- ний эквивалентности на множестве A и множеством всех разбиений мно- жества A.
В любом классе E(x) эквивалентности E каждый элемент y ∈ E(x) свя- зан отношением E с любым элементом z ∈ E(x). Поэтому если E — эк- вивалентность на конечном множестве A, A/E = {E(x
1
), . . . , E(x
n
)},
E(x
i
) = {b
i
1
, . . . , b
i
m
i
}, i = 1, . . . , n, и множество A перенумеровано в следу- ющем порядке: b
1 1
, . . . , b
1
m
1
, b
2 1
, . . . , b
2
m
2
, . . . , b
n
1
, . . . , b
n
m
n
, то матрица [E] имеет блочно-диагональный вид:
[E] =
m
1
m
2
m
n
z}|{ z}|{
z}|{
m
1
n
m
2
n
m
n
n






1 0
1 0
1






,
где блоки 1 состоят из единиц, а остальные элементы равны 0.
Если же множество A перенумеровано произвольным образом:
A = {a
1
, . . . , a
n
}, E — отношение эквивалентности на A, то матрица
[E] = (e
ij
) приводится к блочно-диагональному виду некоторыми одновре-

1.7. ОТНОШЕНИЯ ПОРЯДКА
37
менными перестановками строк и столбцов. Элементы a
i
и a
j
эквивалентны по отношению E тогда и только тогда, когда i-я и j-я строки (а также столб- цы) матрицы [E] совпадают. Класс эквивалентности E(a
i
) состоит из элемен- тов a
j
, для которых e
ij
= 1.
Пример 1.6.3. Рассмотрим множество A = {1, 2, 3, 4, 5} с разбиением
R = {{1, 3, 5}, {2, 4}}, задающим отношение эквивалентности E с двумя E- классами {1, 3, 5} и {2, 4}. Матрица [E] имеет вид







1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1







.
По этой матрице легко определить, что класс E(3) равен {1, 3, 5}, так как в 3-й строке только e
31
, e
33
и e
35
равны 1. ¤
Пример 1.6.4. Рассмотрим геометрическое векторное пространство E
3
и множество направленных отрезков в нем. Направленные отрезки
−−−→
A
1
B
1
и
−−−→
A
2
B
2
называются эквивалентными:
−−−→
A
1
B
1
∼
−−−→
A
2
B
2
, если они имеют одина- ковые длину и направление. Отношение ∼ — это отношение эквивалентно- сти. Вектором (геометрическим вектором) −
→
a в E
3
называется класс экви- валентности направленных отрезков ∼ (
−→
AB) для некоторого
−→
AB. Фактор- множество множества направленных отрезков по отношению ∼ образует множество векторов пространства E
3
. ¤
§ 1.7.
Отношения порядка
Отношение эквивалентности является обобщением отношения равенства:
эквивалентные элементы считаются “равными”. Обобщением обычного отно- шения 6 служат отношения порядка.
Отношение P ⊆ A
2
называется предпорядком или квазипорядком, если
P рефлексивно и транзитивно.
Пример 1.7.1. Отношение P = {(1, 1), (2, 2), (3, 3), (1, 2), (2, 1), (2, 3),
(1, 3)} на множестве {1, 2, 3} является предпорядком (рис. 1.11). ¤

38
Глава 1. ЭЛЕМЕНТЫ ТЕОРИИ МНОЖЕСТВ
Отметим, что симметричный предпорядок является отношением эквива- лентности.
Отношение P ⊆ A
2
называется частичным по-
•
•
•
@
@
@
@
R
-
*
¼
m
¼
m
¸
m
K
2 1
3
Рис. 1.11
рядком, если P рефлексивно, транзитивно и анти- симметрично. Таким образом, частичный порядок —
это антисимметричный предпорядок. Частичный по- рядок обычно обозначается символом 6, а обратное ему отношение 6
−1
— символом >. Отношение > так- же является частичным порядком и называется двой-
ственным порядку 6. Используя отношение 6, определим отношение <,
называемое строгим порядком, по следующему правилу:
x < y ⇔ x 6 y и x 6= y.
Заметим, что отношение строгого порядка не является частичным порядком,
так как не выполняется условие рефлексивности (неверно, что x < x).
Пример 1.7.2. Частичным порядком является
•
•
•
- j
j j
¼
¼
¼
a
b
c
Рис. 1.12
обычное отношение 6 на множестве N. Действитель- но, это отношение рефлексивно (x 6 x), транзитив- но (x 6 y, y 6 z ⇒ x 6 z) и антисимметрично (x 6 y,
y 6 x ⇒ x = y). ¤
Пример 1.7.3. Отношение, изображенное на рис.
1.12, является частичным порядком, а отношение из примера 1.7.1 — нет. ¤
Пример 1.7.4. Отношение включения ⊆ на булеане P(U) образует ча- стичный порядок. ¤
Заметим, что в примерах 1.7.3 и 1.7.4 имеются элементы x и y, про ко- торые нельзя сказать, что x 6 y или y 6 x (например, при a = x, y = c
из примера 1.7.3). Такие элементы называются несравнимыми. Частичный порядок 6 ⊆ A
2
называется линейным порядком, если любые два элемен- та x и y из множества A сравнимы, т. е. x 6 y или y 6 x (линейным является частичный порядок из примера 1.7.2).
Непустое множество A, на котором зафиксирован некоторый частичный
(линейный) порядок, называется частично (линейно) упорядоченным мно-
жеством (сокращенно ч.у.м. или л.у.м.).
Пример 1.7.5. Пары hω; 6i, h[0, 1]; 6i с обычными отношениями 6 об- разуют линейно упорядоченные множества. ¤

1.7. ОТНОШЕНИЯ ПОРЯДКА
39
Пусть hA; 6i — частично упорядоченное множество. Определим на мно- жестве A
2
отношение Π условием
(a
1
, b
2
) Π (a
2
, b
2
) ⇔ a
1 6 a
2
и b
1 6 b
2
.
Отношение Π есть отношение частичного порядка. Оно называется отноше-
нием Парето. Пара hA
2
; Πi образует частично, но не линейно упорядоченное множество, если |A| > 1.
Элемент a ∈ A частично упорядоченного множества A = hA; 6i называ- ется максимальным (минимальным), если для всех x ∈ A из a 6 x (x 6 a)
следует x = a. Элемент a ∈ A называется наибольшим (наименьшим), если
x 6 a (a 6 x) для всех x ∈ A. Наибольший (наименьший) элемент ч.у.м. A
(если он существует) обозначается через max A (min A). Наибольший эле- мент часто называют единицей, а наименьший — нулем множества A. За- метим, что всякий наибольший элемент является максимальным, а всякий наименьший элемент — минимальным. Обратное утверждение, вообще гово- ря, неверно (см. пример 1.7.6). Всякое конечное ч.у.м. содержит как макси- мальные, так и минимальные элементы.
Пример 1.7.6. Частично упорядоченное множе-
•
•
•
³³
³³
³³
³³
1
PPP
PPP
PP
q i
i i
¸
¸
K
1 3
2
Рис. 1.13
ство h{1, 2, 3}; 6i, изображенное на рис. 1.13, имеет наибольший элемент 2, минимальные элементы 1, 3,
но не имеет наименьшего элемента. ¤
Пример 1.7.7. Линейно упорядоченное множе- ство h[0, 1); 6i имеет наименьший элемент 0, но не имеет наибольшего элемента. ¤
Пусть A = hA; 6i — ч.у.м., B — подмножество A. Элемент a ∈ A называ- ется верхней (нижней) гранью множества B и пишут B 6 a (соответственно
a 6 B), если b 6 a (a 6 b) для всех b ∈ B.
Пример 1.7.8. Рассмотрим ч.у.м. hR; 6i и интервал B = (0, 1]. Тогда любое число x > 1 является верхней гранью B, а любое число x 6 0 —
нижней гранью B. ¤
Элемент a ∈ A называется точной верхней гранью (супремумом) мно- жества B (обозначается sup B), если a — наименьшая из верхних граней множества B. Элемент a ∈ A называется точной нижней гранью (инфиму-
мом) множества B (обозначается inf B), если a — наибольшая из нижних граней множества B.

40
Глава 1. ЭЛЕМЕНТЫ ТЕОРИИ МНОЖЕСТВ
В примере 1.7.8 имеем sup B = 1, inf B = 0.
Линейный порядок 6 на множестве A называется полным, если каж- дое непустое подмножество множества A имеет наименьший элемент. Пара
hA; 6i, в которой отношение 6 является полным порядком на множестве A,
называется вполне упорядоченным множеством (сокращенно в.у.м.).
Пример 1.7.9. Пара hω; 6i является в.у.м., а пара h[0, 1]; 6i — нет,
поскольку, например, полуоткрытый интервал (1/2, 1], являющийся подмно- жеством [0, 1], не содержит наименьшего элемента. ¤
Определим отношение, на котором основано упорядочение слов в словарях.
Рассмотрим непустое множество символов X = {x, y, z, . . .}, называемое
алфавитом. Конечные наборы написанных друг за другом символов из X
называются словами (например, x, y, xy, yx, zxx, xyyz и т. д.). Элемент x
i
слова x
1
x
2
. . . x
n
называется его i-й координатой. Число n называется длиной
слова x
1
x
2
. . . x
n
. Множество слов алфавита X обозначим через W (X). При этом будем считать, что W (X) содержит слово Λ, не имеющее символов и называемое пустым словом. Длина пустого слова Λ по определению равна нулю. Заметим, что каждое слово x
1
x
2
. . . x
n
из W (X) взаимно однозначно соответствует упорядоченному набору hx
1
, x
2
, . . . , x
n
i из X
n
. Следовательно,
множество W (X) биективно множеству ∪
n∈ω
X
n
, и, значит, бесконечно.
Пусть 6 — отношение порядка на множестве X. Определим на множестве
W (X) отношение лексикографического порядка L по следующему правилу:
x
1
x
2
. . . x
m
L y
1
y
2
. . . y
n
⇔ (m 6 n и x
i
= y
i
для всех 1 6 i 6 m) или (суще- ствует i 6 m такое, что x
i
< y
i
, и для всех j < i выполняется x
j
= y
j
).
Утверждение 1.7.1. Если hX; 6i — л.у.м., то hW (X); Li — л.у.м.
Доказательство. Рефлексивность и транзитивность отношения L
очевидны.
Для проверки антисимметричности предположим,
что x
1
x
2
. . . x
m
L y
1
y
2
. . . y
n
и y
1
y
2
. . . y
n
L x
1
x
2
. . . x
m
. Так как отношение 6
антисимметрично, не существует i такого, что x
i
6= y
i
и x
j
= y
j
для всех
j < i. Тогда по определению отношения L получаем m 6 n, n 6 m, т. е.
m = n, и x
1
x
2
. . . x
m
= y
1
y
2
. . . y
n
. Покажем теперь, что любые два слова
ˆ
X = x
1
x
2
. . . x
m
и ˆ
Y = y
1
y
2
. . . y
n
сравнимы. Пусть i — максимальный индекс,
такой, что x
j
= y
j
для всех j < i. Если x
i
< y
i
или i = m + 1 6 n, то ˆ
X L ˆ
Y .
Если y
i
< x
i
или i = n + 1 6 m, то ˆ
Y L ˆ
X. Если же указанные случаи не выполняются, то m = n = i − 1 и ˆ
X = ˆ
Y . ¤

1.7. ОТНОШЕНИЯ ПОРЯДКА
41
Как показывает следующий пример, если |X| > 2, система hW (X); Li
не является в.у.м.
Пример 1.7.10. Рассмотрим в.у.м. hX; 6i, где X = {0, 1}, 6 = {(0, 0),
(0, 1), (1, 1)}. Бесконечное множество, состоящее из слов
1, 01, 001, . . . , 00 . . . 01, . . .
не имеет наименьшего элемента по отношению L. Следовательно, система
hW (X); Li не является в.у.м. ¤
Обозначим через W
n
(X) множество слов алфавита X, длина которых не превосходит n, через L
n
— ограничение отношения L на множество W
n
(X):
L
n
­ L ∩ (W
n
(X))
2
Утверждение 1.7.2. Если hX; 6i — в.у.м., то hW
n
(X); L
n
i — в.у.м.
для любого n ∈ ω.
Доказательство. В силу утверждения 1.7.1 достаточно показать,
что любое непустое подмножество Y множества W
n
(X) имеет наименьший элемент по отношению L
n
. Если Λ ∈ Y , то Λ является наименьшим эле- ментом. Предположим теперь, что Λ /
∈ Y . Рассмотрим множество Y
1
⊆ Y ,
состоящее из слов, у которых первая координата является наименьшей среди первых координат слов из Y . Если Y
1
содержит слово длины 1, то оно будет наименьшим элементом множества Y . В противном случае рассмотрим мно- жество Y
2
⊆ Y
1
, состоящее из слов, у которых вторая координата является наименьшей среди вторых координат слов из Y
1
. Если Y
2
содержит слово длины 2, то оно будет наименьшим элементом множества Y . В противном случае аналогично определим множество Y
3
и будем продолжать построение множеств Y
k
до тех пор, пока в Y
k
не найдется слово длины k, которое будет наименьшим элементом множества Y . По определению множества W
n
(X)
такое слово определится не более чем за n шагов. ¤
Пример 1.7.11. Рассмотрим множество букв русского алфавита, кото- рое обозначим через A. Определим на A полный порядок 6 в соответствии с обычным упорядочением букв по алфавиту. Пусть n — натуральное чис- ло, ограничивающее длину слов, употребляемых в русском языке, например
n = 1000. Отношение L
n
на множестве W
n
(A) определяет упорядочение слов,
по которому составляются словари. ¤

42
Глава 1. ЭЛЕМЕНТЫ ТЕОРИИ МНОЖЕСТВ
Рассмотрим частично упорядоченное множество hA; 6i. Говорят, что эле- мент y покрывает элемент x (обозначается x ≺ y), если x 6 y и не су- ществует такого элемента z, что x < z < y. Если множество A конечно,
частично упорядоченное множество hA; 6i можно представить в виде схе- мы, в которой каждый элемент изображается точкой на плоскости, и если
y покрывает x, то точки x и y соединяют отрезком, причем точку, соответ- ствующую x, располагают ниже y. Такие схемы называются диаграммами
Хассе. На рис. 1.14 показаны две диаграммы Хассе. Вторая диаграмма со- ответствует линейно упорядоченному множеству.
Пример 1.7.12. 1. Рассмотрим частично упорядо-
•
•
•
•
•
•
¡
¡
¡
@
@
@
¡
¡
¡
@
@
@
•
•
•
•
•
а
б
Рис. 1.14
ченное множество hP(A); ⊆i, где A = {1, 2, 3}. Множе- ство P(A) содержит восемь элементов: {0, {1}, {2}, {3},
{1, 2}, {1, 3}, {2, 3}, {1, 2, 3}}. На рис. 1.15a изображена диаграмма Хассе, соответствующая hP(A); ⊆i.
2. Пусть A = {1, 2, 3, 5, 6, 10, 15, 30}. Рассмотрим отношение частичного порядка 6 на множестве A, зада- ваемое по правилу: x 6 y ⇔ y делится на x. Диаграмма
Хассе для ч.у.м. hA; 6i изображена на рис. 1.15б.
3. На рис. 1.15в изображена диаграмма Хассе линейно упорядоченного множества h{0, 1, 2, 3, 4, 5, 6, 7}; 6i c обычным отношением порядка на мно- жестве натуральных чисел, не превосходящих семи. ¤
•
•
•
•
•
•
•
•
¡
¡
¡
¡
¡
¡
¡
¡
@
@
@
@
@
@
@
@
¡
¡
¡
¡
¡
¡
¡
¡
@
@
@
@
@
@
@
@
∅
{1}
{2}
{3}
{1,2}
{2,3}
{1,3}
{1,2,3}
•
•
•
•
•
•
•
•
¡
¡
¡
¡
¡
¡
¡
¡
@
@
@
@
@
@
@
@
¡
¡
¡
¡
¡
¡
¡
¡
@
@
@
@
@
@
@
@
1 2
3 5
6 10 15 30
•
•
•
•
•
•
•
•
0 1
2 3
4 5
6 7
а
б
в
Рис. 1.15