Спец.гл.мат-ки_Ч.1_УП
.pdf
21
G = {(x, y) x, y X , x > y} ;
L = {(x, y) x, y X , x ≤ y} ;
M = {(x, y) |
|
x, y X ,(x − y) делится на 3}; |
||
|
||||
K = {(x, y) |
|
|
|
x, y X , x2 + y2 ≤ 20} . |
|
|
|||
Отношение R на множестве Х называется рефлексивным, если для всех x X выполняется условие (x, x) R . Среди при-
веденных выше отношений рефлексивными являются отношение L (т.к. неравенство x ≤ x справедливо при всех x X ) и отношение М (т.к. разность x − x = 0 делится на 3, значит, пара (x, x) принадлежит отношению М при всех x X ).
Отношение R на множестве Х называется антирефлексивным, если условие (x, x) R не выполняется ни при одном
x X . Примером антирефлексивного отношения является отношение G (неравенство x > x не выполняется ни при каких значениях х, следовательно, ни одна пара (x, x) не принадлежит
отношению G). Отметим, что отношение К не является рефлексивным (52 + 52 > 20 (5,5) K) и не является антирефлексив-
ным (12 + 12 ≤ 20 (1,1) K ) .
Отношение R на множестве Х называется симметричным, если из условия (x, y) R следует ( y, x) R . Симметричными
являются отношения М (если x − y делится на 3, то и y − x де-
лится на 3) и К (если x2 + y2 ≤ 20 , то и y2 + x2 ≤ 20 ).
Отношение R на множестве Х называется несимметричным, если для любых x, y X из условия (x, y) R следует
( y, x) R . Несимметричным является отношение G, т.к. условия x < y и y < x не могут выполняться одновременно (только одна из пар (x, y) или ( y, x) принадлежит отношению G).
Отношение R на множестве Х называется антисиммет-
ричным, |
если для любых x, y X из условия (x, y) R и |
( y, x) R |
следует x = y . Антисимметричным является отноше- |
22
ние L, т.к. из одновременного выполнения x ≤ y и y ≤ x следует x = y .
Отношение R на множестве Х называется транзитивным, если для любых x, y, z R из одновременного выполнения усло-
вий (x, y) R и ( y, z) R следует (x, z) R . Отношения G, L, M являются транзитивными, а отношение К нетранзитивно: если x = 3, y = 2, z = 4, то 32 + 22 ≤ 20 и 22 + 42 ≤ 20 , но 32 + 42 ≥ 20 ,
то есть выполняются условия (x, y) K и ( y, z) K , но
(x, z) K .
1.2.5 Отношения эквивалентности
Рассмотрим три отношения: M, S, H. Отношение М описано в 1.2.4. Отношение S введем на множестве X всех треугольников следующим образом: этому отношению принадлежат пары треугольников такие, что площадь треугольника x равна площади треугольника y.
Отношение Н действует на множестве жителей г. Томска и содержит пары (x, y) такие, что х и у носят шляпы одинакового
размера.
Свойства этих трех отношений приведены в таблице 1.3, где Р означает рефлексивность, АР – антирефлексивность, С – симметричность, АС – антисимметричность, НС – несимметричность, Т – транзитивность отношения. В качестве упражнения проверьте правильность заполнения таблицы, пользуясь определениями свойств бинарных отношений.
Таблица 1.3 − Свойства отношений
Отношение |
Р |
АР |
С |
АС |
НС |
Т |
М |
+ |
– |
+ |
– |
– |
+ |
S |
+ |
– |
+ |
– |
– |
+ |
H |
+ |
– |
+ |
– |
– |
+ |
Мы видим, что отношения обладают одинаковыми свойствами, поэтому их относят к одному типу.
23
Определение. Отношение R на множестве Х называется отношением эквивалентности, если оно обладает свойствами рефлексивности, симметричности, транзитивности.
Таким образом, отношения M, S, H являются отношениями эквивалентности на соответствующих множествах Х. Важной особенностью отношений эквивалентности является то, что они разбивают все множество Х на непересекающиеся подмножества – классы эквивалентности.
Определение. Классом эквивалентности, порожденным элементом x X , называется подмножество [x] множества Х,
для элементов которого выполняется условие |
|
(x, y) R, y X . |
Таким образом, класс эквивалентности [x] = {y |
|
y X,(x, y) R} . |
|
||
Так, отношение М разбивает множество |
|
X = {1,2,3,4,5,6,7} |
на три класса эквивалентности: [1] = {1,4,7}, [2] = {2,5}, [3] = {3,6} .
Класс, порожденный элементом 4, совпадает с классом [1]; [5] =
=[2], [3] = [6], [7] = [1].
Классы эквивалентности образуют систему непустых непересекающихся подмножеств множества Х, в объединении дающую все множество Х – т.е. образуют разбиение множества Х
(см. 1.1.6).
Отношение эквивалентности обозначают « ≡ », поэтому определение класса эквивалентности можно записать так:
[x] = {y y X , x ≡ y}.
Множество различных классов эквивалентности множества X по отношению R называется фактор-множеством и обозна-
чается X R . Так, для отношения M фактор-множество состоит из трех элементов:
X M = {[1],[2],[3]}.
Теорема 1. Пусть R – отношение эквивалентности на множестве X и X R − совокупность всех различных классов эквива-
лентности по отношению R. Тогда X R − разбиение множества
X.
24
Доказательство. По условию теоремы R – отношение эквивалентности, т.е. рефлексивно, симметрично и транзитивно.
Покажем, |
что X |
|
R = {K1, K2 ,..., Kr } − разбиение множества X, |
|
|||
т.е. |
|
|
|
а) Ki X , Ki ≠ ; |
|||
б) r |
Ki = X ; |
||
i=1 |
|
|
|
в) Ki ∩ K j = , i ≠ j, i, j = 1, r .
Условие а выполняется по определению класса эквивалентности и по свойству рефлексивности, т.к. x [x] для любого
x X .
Условие б выполняется, так как каждый элемент множества
X попадает в какой-либо класс эквивалентности и [x] = X .
|
|
в докажем методом «от |
x X |
|
Условие |
противного». Пусть |
|
Ki |
= [x] и K j |
= [ y] – разные классы эквивалентности (т.е. Ki и |
|
K j |
отличаются хотя бы одним элементом). Покажем, что они не |
||
пересекаются. |
Предположим противное: |
найдется элемент |
|
z X такой, что z Ki и z K j . По определению класса эквивалентности z ≡ x и z ≡ y . По свойствам симметричности и транзитивности отношения R имеем: (x ≡ z и z ≡ y) (x ≡ y) – отсюда следует равенство множеств Ki и K j .
Действительно, возьмем произвольный элемент a Ki : a [x] a ≡ x a ≡ y a K j в силу произвольности a следует Ki K j .
Возьмем произвольный элемент b K j : b [ y] b ≡ y b ≡ x b Ki − в силу произвольности b следует K j Ki . По определению равенства множеств Ki = K j .
Условие в доказано: если классы эквивалентности не совпадают, то они не пересекаются.
25
Следовательно, фактор-множество X R является разбиени-
ем множества X. |
|
|
|
|||
|
Теорема 2. Всякое разбиение множества X порождает на X |
|||||
отношение эквивалентности. |
|
|
||||
|
Доказательство. |
Пусть {X1, X 2 ,..., X r } − разбиение мно- |
||||
жества X. Рассмотрим на X отношение R = {(x, y) |
|
найдется |
||||
|
||||||
X i ,i = |
|
: x X i и y X i } . |
|
|
||
1, r |
|
|
||||
|
Покажем, что R – отношение эквивалентности. |
|
|
|||
|
Рефлексивность |
отношения R следует из |
|
условия |
||
r |
X i = X . Каждый элемент множества X попадает в одно из |
|||||
i=1 |
|
|
|
|
|
|
множеств X i ,i = 1, r , поэтому
x X X i ,i = 1, r: x X i (x, x) R .
Покажем, что отношение R симметрично. Пусть (x, y) R . Это означает, что
Xi ,i = 1, r :x X i и y X i y X i иx X i ( y, x) R .
Покажем, что R транзитивно. Пусть (x, y) R |
и ( y, z) R . |
Тогда найдется множество X i :x X i и y X i и |
множество |
X j : y X j и z X j . Но так как различные блоки разбиения не пересекаются, а y X i ∩ X j , то X i = X j . Следовательно, (x, z) R и R транзитивно.
Отношение R обладает свойствами рефлексивности, симметричности, транзитивности, т.е. является отношением эквивалентности. Теорема доказана.
1.2.6 Отношения порядка
Рассмотрим отношения G, L из 1.2.4, отношение Q из 1.2.2 и отношение включения V на множестве всех подмножеств целых чисел (B(Z) – булеан множества Z):
V = {( X ,Y ) X ,Y B (Z) , X Y}.
26
Таблица 1.4 − Свойства отношений
Отношение |
Р |
АР |
С |
АС |
НС |
Т |
G |
– |
+ |
– |
– |
+ |
+ |
L |
+ |
– |
– |
+ |
– |
+ |
Q |
+ |
– |
– |
+ |
– |
+ |
V |
+ |
– |
– |
+ |
– |
+ |
Мы видим, что по свойствам эти отношения разделились на два типа.
Определение. Отношение R на множестве Х, обладающее свойствами рефлексивности, антисимметричности, транзитивности, называется отношением порядка на множестве Х (обо-
значается « »).
Определение. Отношение R на множестве Х, обладающее свойствами антирефлексивности, несимметричности, транзитивности, называется отношением строгого порядка.
Таким образом, отношения L, Q, V являются отношениями порядка на соответствующих множествах, а отношение G – отношением строгого порядка.
1.2.7 Частично упорядоченные множества
Если на множестве X введено отношение порядка , то получен новый объект (X , ) – частично упорядоченное множест-
во. Так, различные частично упорядоченные множества (N, ≤) и (N, ) можно получить, рассматривая на множестве N натуральных чисел отношения сравнения « ≤ » ( x ≤ y – x меньше или
равно y и делимости « » ( x y − x является делителем y). Сло-
во «частично» используется потому, что не все элементы множества могут быть сравнимы между собой. Для частично упорядоченного множества (N, ) несравнимы элементы 2 N и 3 N, так как ни один из них не является делителем другого.
27
Если все элементы множества сравнимы между собой, мы имеем линейный порядок, например, (N, ≤ ) – линейно упорядоченное множество.
1.2.8 Диаграммы Хассе
Для наглядного представления частично упорядоченного множества (X , R) используют диаграмму Хассе – граф отноше-
ния R без петель и транзитивно замыкающих дуг.
Пусть X = {1, 2,3, 4} . Рассмотрим на множестве X отноше-
ния порядка « ≤ « и |
« «. Получим два частично упорядочен- |
|
ных множества (X, ≤ ) и (X, ), различия которых наглядно от- |
||
ражают их диаграммы Хассе (рис.1.9). |
|
|
4 |
4 |
|
3 |
|
|
2 |
2 |
3 |
1 |
1 |
|
а) б)
Рис. 1.9 − Диаграммы Хассе частично упорядоченных множеств (X, ≤ ) (а) и (X, ) (б)
Определение. Элемент |
w X |
называется наибольшим |
|
элементом частично упорядоченного множества (X , ), если |
|||
x X x w. Элемент |
u X |
называется |
максимальным |
элементом частично упорядоченного множества |
(X , ), если в |
||
множестве X нет элемента y такого, что u y.
Элемент w = 4 является наибольшим и одновременно максимальным для (X, ≤ ) (рис. 1.9,а). В частично упорядоченном множестве (X, ) есть два максимальных u1 = 4 и u2 = 3 , но нет наибольшего (рис. 1.9,б).
28
Аналогично определяются понятия наименьшего и минимального элементов частично упорядоченного множества.
Теорема. Всякое частично упорядоченное множество имеет не более одного наибольшего элемента.
Доказательство. Пусть (X , ) – частично упорядоченное множество. Теорема утверждает, что если в множестве (X , )
имеется наибольший элемент, то он единственный. Предположим противное: пусть имеется два различных наибольших элемента w X и w′ X . Тогда по определению наибольшего
элемента w w′ и w′ w, откуда в силу антисимметричности отношения порядка « » следует w′ = w − противоречие, что и доказывает теорему.
1.2.9 Изоморфизм частично упорядоченных множеств
Частично упорядоченные множества (X , ) и (Y, ′) изоморфны, если существует биекция ϕ : X → Y , сохраняющая отношение порядка, т.е. x1, x2 X таких, что x1 x2 , выполняет-
ся ϕ (x1) ′ ϕ (x2 ), ϕ (x1 ),ϕ (x2 ) Y .
Пример. Рассмотрим множество T точек горизонтальной прямой, упорядоченное отношением L – «лежит левее или совпадает», и множество действительных чисел R с введенным на нем отношением порядка «≤». Тогда (T,L) изоморфно (R, ≤) и, решив задачу на множестве R, мы иллюстрируем решение с помощью множестваT, таккакструктура этихмножестводинакова.
Теорема. Всякое частично упорядоченное множество изоморфно некоторому подмножеству его булеана, упорядоченному отношением включения.
Пример. Рассмотрим частично упорядоченное множество (X, ) из 1.2.7. Так как X = {1, 2,3, 4} состоит из n = 4 элементов,
то его булеан B(X) содержит 24 = 16 элементов – подмножеств множества X. Выберем из них 4 подмножества следующим образом: сопоставим каждому элементу x X подмножество
29
Sx B(X), включающее те и только те элементы y, которые являются делителями элемента x:
Sx = {y y X , y x} .
Получим множество F = {S1, S2 , S3 , S4} B(X), где S1 = {1} ,
S2 = {1,2}, S3 = {1,3}, |
S4 = {1,2,4} . Частично |
упорядоченные |
|
множества (X, ) и ( F, ) изоморфны (рис. 1.10). |
|||
4 |
|
S4 |
|
2 |
3 |
S2 |
S3 |
1 |
|
S1 |
|
а) |
|
б) |
|
Рис. 1.10 − Диаграммы Хассе изоморфных частично упорядоченных множеств
(X, ) (а) и ( F, ) (б)
Доказательство теоремы. Пусть задано произвольное упорядоченное множество (X , ). Построим подмножество F B(X) с помощью соответствия: каждому элементу x X
сопоставим f (x) = Sx = {y y X , y x} и обозначим F = {Sx}x X . Покажем, что соответствие f : X → F является биекцией,
т.е. выполняются условия а – г определения биекции из 1.2.1. Условия а – в выполняются согласно способу построения мно-
жества F: каждый элемент x X |
имеет единственный прообраз |
f (x) = Sx , а каждый элемент Sx |
множества F имеет прообраз |
x X . Покажем, что этот прообраз – единственный. Предполо-
жим противное: существует два различных элемента |
a,b X , |
имеющие одинаковые прообразы f (a) и f (b) , т.е. |
a ≠ b , но |
Sa = f (a) = f (b) = Sb . |
|
В силу рефлексивности отношения порядка « » имеем:
a a a Sa a Sb a b.
30
Аналогично,
b b b Sb b Sa b a.
Так как отношение порядка антисимметрично, получим a = b , что противоречит нашему предположению. Следовательно, различные элементы Sa , Sb F имеют различные прообразы: f (a) ≠ f (b) a ≠ b , а отображение f : X → F является би-
екцией.
Докажем, что биекция f : X → F сохраняет порядок, т.е.
если a,b X и a b, то f (a) = Sa Sb = f (b) . Согласно определению включения множеств достаточно показать, что x Sa выполняется x Sb .
Возьмем произвольный элемент x Sa . Тогда x a, но a b, поэтому x b (в силу транзитивности отношения порядка) и x Sb . Доказано включение Sa Sb .
Итак, построенное отображение f : X → F B(X) является биекцией, сохраняющей отношение порядка. Следовательно, частично упорядоченные множества (X, ) и ( F, ) изоморфны. Теорема доказана.
1.2.10 Решение задач 5,6 контрольной работы № 1
Задача 5. На множестве X = {1,2,3,4,5} задано бинарное отношение R X X : R = {(x, y) x, y X ,(x + 2 y) делится на 3} .
Представить отношение R различными способами; выяснить, какими свойствами оно обладает; является ли отношение R отношением эквивалентности или отношением порядка.
Решение. Отношение R можно задать перечислением всех элементов:
R = {(1,1),(2,2),(3,3),(4,4),(5,5),(1,4),(4,1),(5,2),(2,5)}.
Наглядно представить отношение R можно с помощью графика (рис. 1.11,а), схемы (рис. 1.11,б), графа (рис. 1.12,а), матрицы отношения (рис. 1.12,б).
Выясним, какими свойствами обладает отношение.