Пример 1.21

1. Если X={1,2,3,4,5}, то множество {{1,2}, {3}, {4,5}} будет его разбиением.   

2. Если X – множество студентов университета, то разбиениями будут множество факультетов или множество студенческих групп.

Утверждение 1.6. Всякое разбиение множества X определяет на X отношение эквивалентности  тогда и только тогда, когда из x, y   следует, что x, y принадлежат одному подмножеству разбиения.

Доказательство. Всякое разбиение, согласно определению, задает отношение принадлежности к подмножеству разбиения. Следовательно, остается доказать, что это отношение есть эквивалентность.

1) Рефлексивность: x, x  , так как x принадлежит какому-то одному подмножеству.

2) Симметричность: пусть x, y принадлежат одному подмножеству, тогда из x, y   следует, что y, x принадлежат этому же подмножеству, т.е. y, x  .

3) Транзитивность: Пусть x, y  , тогда x, y  X_t, и пусть y, z  , тогда y, z X_s.  Так как  y  X_t  и  y  X_s, то X_t  = X_s, тогда z X_t, следовательно,  x, z  .

Утверждение 1.7. Всякое отношение эквивалентности  определяет разбиение множества X на классы эквивалентности относительно этого отношения.

Доказательство. Согласно утверждению 1.5, каждый элемент x принадлежит некоторому классу эквивалентности [x] относительно . Покажем, что любые два класса либо не пересекаются, либо совпадают. Действительно, пусть z принадлежит разным классам, то есть z  [x] и z  [y], тогда  x, z   и y, z  , то есть [x] = [z], [y] = [z]. Следовательно, [x] = [y], так как они состоят из одних и тех же элементов.

Фактор-множеством X_/ множества X по отношению эквивалентности  называется совокупность классов эквивалентности элементов этого множества

1.5. Отношение частичного порядка

           Упорядоченные множества

           Точная верхняя и точная нижняя грани упорядоченных множеств

           Диаграммы Хассе

           Изоморфизм множеств

           Классы бинарных отношений, не являющиеся эквивалентностью или частичным порядком

 

Упорядоченные множества

Отношением частичного порядка на множестве  называется бинарное отношение  (предшествует), являющееся одновременно рефлексивным, антисимметричным и транзитивным на этом множестве. Множество , на котором задано отношение порядка , записывается как пара (,  ).

Пример 1.22

1. Отношение "меньше или равно"  ()  на множестве действительных чисел является отношением частичного порядка (R, ). Это отношение также называют отношением естественного числового порядка.

2. На множестве подмножеств некоторого универсального множества U отношение включения A   B есть отношение частичного порядка (2^U, ).

3. Иерархическая схема подчинения в учреждении на множестве должностей есть отношение частичного порядка.

Отношением линейного порядка на множестве  называется отношение частичного порядка, если для любых  элементов  x, y    имеем  x   y или y   x.

Пример 1.23

1. В примере 1.22 первое отношение является отношением линейного порядка, второе отношение не является линейным порядком.

2. Отношение Парето  (П)  – отношение частичного порядка. Суть его в следующем. Пусть на  задано отношение частичного порядка . На множестве ² =    определим отношение П следующим образом:

П   a, b, c, d  a, c    и b, d  .

Иначе говоря, <a, b> П <c, d> тогда и только тогда, когда a   c и b   d.

Замечание. Под отношением частичного порядка интуитивно понимается "предшествование", "предпочтение", "приоритет" и т.п.

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

Элементы x и y упорядоченного множества (X,  )  называются сравнимыми по отношению порядка , если x   y или y   x. В противном случае они называются несравнимыми.

Заметим, что если все элементы некоторого множества сравнимы по заданному на нем бинарному отношению, то это множество по этому отношению линейно упорядоченно.

Поскольку в упорядоченном множестве (A,  ), в общем случае, существуют несравнимые элементы, то  подмножества B  A могут быть либо частично упорядочены, либо линейно упорядочены, либо неупорядочены относительно порядка   множества A. Если подмножество B упорядочено, то говорят, что его порядок   _B  индуцирован исходным порядком     на всем множестве A.  

 

Точная верхняя и точная нижняя грани упорядоченных множеств

Пусть (A, ) – упорядоченное множество. Элемент a  A называется наибольшим (наименьшим) элементом множества A, если для всех x  A выполняется  отношение x   a (a   x).

Элемент b  A называется максимальным (минимальным) элементом множества A, если для всех x  A выполняется одно из условий:  x   b   (b   x) или x и b не сравнимы.

Утверждение 1.8. Наибольший элемент множества, если он существует, является единственным.

Доказательство. Действительно, положим, что элементы a и a' – наибольшие элементы упорядоченного множества  (A, ), тогда для каждого x  A выполняется  x   a  и  x   a'. В частности,  a'   a  и  a   a'. Поскольку отношение    антисимметрично, то из соотношений  a'   a  и  a   a', следует равенство   a' = a.

Утверждение 1.9. Наименьший элемент множества, если он существует, является единственным.

Доказательство аналогично доказательству утверждения 1.8.

Пусть (A, ) – упорядоченное множество и B  A . Элемент a  A называется верхней  (нижней) гранью множества B, если для всех x  B выполняется отношение  x   a    (a   x).

Наименьший (наибольший) элемент всех верхних (нижних) граней  множества B называют точной верхней (точной нижней) гранью B. Точную верхнюю и точную нижнюю грани множества B обозначают соответственно через  sup B и inf B.

Пример 1.24.  Рассмотрим множество Z²  точек плоскости с целочисленными координатами, заданными в некоторой прямоугольной декартовой системе координат, на котором определено отношение П   (см. пример 1.23 2).

1. Пусть P  Z² – множество рассматриваемых течек, ограниченное треугольником OAB, где O  <0,0>, A  <0,5>, B  <5,0>. Это множество будет, множеством  упорядоченных пар с индуцированным порядком П, то есть  (P, П) = {<0,0>, <0,1>, <0,2>, <0,3>, <0,4>, <0,5>. <1,0>, <1,1>, <1,2>, <1,3>, <1,4>, <2,0>, <2,1>, <2,2>, <2,3>, <3,0>, <3,1>, <3,2>, <4,0>, <4,1>, <5,0>} (рис. 1.3).

В этом множестве: 1) наименьшим элементом будет точка  <0,0>;  2) максимальными элементами будут точки  <0,5>, <1,4>, <2,3>, <3,2>, <4,1>, <5,0>;  3) наибольшего элемента нет.

Рис. 1.3. Множество Р

 

Рис. 1.4. Множество F

 

2. Пусть  F  Z² – множество рассматриваемых течек, ограниченное трапецией ABCD, где A  <0,5>, B  <5,0>, C  <0,3>, D  <3,0>. Это множество будет, множеством  упорядоченных пар с индуцированным порядком П, то есть (F, П) = {<0,3>,<0,4>, <0,5>, <1,2>. <1,3>, <1,4>, <2,1>, <2,2>, <2,3>, <3,0>, <3,1>, <3,2>, <4,0>, <4,1>, <5,0>}  (рис. 1.4).

В этом множестве: 1) наименьшего и наибольшего элементов нет; 2) минимальными элементами будут точки <0,3>, <1,2>, <2,1>, <3,0>; 3) максимальными элементами будут точки  <0,5>, <1,4>, <2,3>, <3,2>, <4,1>, <5,0>;  4) точной нижней гранью и точной верхней гранью множества F будут соответственно точки <0,0> и <5,5>, то есть inf F = <0,0>, sup F = <5,5>. Эти точки являются элементами множества  Z², но не принадлежат множеству F.

Диаграммы Хассе

Если  x  (предшествует) y и x  y, то пишут: x  (строго предшествует)  y.

Говорят, что элемент y покрывает элемент x, если x   y, и не существует такого элемента u, что x   u   y. В общем же случае, если x  y, то либо y покрывает x, либо существуют такие элементы  x₁, x₂,..., x_i, x_i+1,...,x_n, что x = x₁   x₂ ...  x_i   x_i+1 ...  x_n = y, где x_i+1 покрывает x_i для всех i.

 

Рис. 1.5. Диаграммы частично упорядоченных множеств

 

Для иллюстрации частичного порядка на множестве  используют схемы, которые называются диаграммами Хассе. В этих диаграммах элементы множества изображают в виде точек на плоскости. В самом низу изображают наименьший элемент, если он существует и принадлежит множеству, либо минимальные элементы, выше располагают элементы, покрывающие элементы предыдущего ряда и т.д., причем, если y покрывает x, то точки, им соответствующие, соединяют отрезками. На   рис. 1.5 показаны диаграммы Хассе двух множеств, причем рис. 1.5,б соответствует линейно упорядоченному множеству.