В.Н. Нефедов - Алгебра множеств, бинарные отношения в примерах и задачах, страница 9

Из определения ≺ следует, что ≼  ≺.Упражнение 4.1. Доказать, что отношение строгого порядка ≺ намножестве A является антисимметричным и транзитивным.Решение. Антисимметричность следует из утверждения 3.1 (см.тему №3). Покажем транзитивность. Пусть x, y, z  A , x ≺ y , y ≺ z .Покажем, что x ≺ z . Из x ≺ y , y ≺ z следует, что x ≼ y , y ≼ z , откуда(используем транзитивность ≼) x ≼ z .

Тогда, если предположить невыполнение условия x ≺ z , то получаем, что x  z . Однако, из условий: x  z , x ≼ y , y ≼ z , в силу антисимметричности ≼, получаем, чтоx  y , а это противоречит условию x ≺ y .Пусть A – частично упорядоченное множество, a, b  A . Назовемсегментом множество [a, b]  {x  A | a ≼ x ≼ b} . Например, в соответствии со схемой, приведенной на рис.4.1 (см. пример 4.4) [курьер, директор]={курьер, главбух, директор}.Замечание 4.1. Пусть A – частично упорядоченное множество сзаданным на нем бинарным отношением частичного (линейного) порядка ≼.

Тогда любое его подмножество B также частично (линейно)упорядочено бинарным отношением частичного (линейного) порядка≼  B 2 (используя утверждение 3.1, а также задачу 3.6, докажите рефлексивность, антисимметричность, транзитивность бинарного отношения ≼  B 2 ; а в случае линейного порядка ≼ докажите сравнимостьлюбых двух элементов из B по ≼  B 2 ). Для простоты обозначений,для произвольных элементов x, y  B в случае x, y  ≼  B 2 краткопишем x ≼ y .Пусть A – частично упорядоченное множество. Элемент a  Aназывается максимальным (минимальным) по ≼ на множестве A , если55x  A из того, что a ≼ x ( x ≼ a ) следует, что a  x . Элемент a  Aназывается наибольшим (наименьшим) по ≼ на множестве A , еслиx  A x ≼ a ( a ≼ x ).

Следующее утверждение очевидно.Утверждение 4.1. Пусть A – частично упорядоченное множество.Элемент a  A является максимальным (минимальным) по ≼ намножестве A , тогда и только тогда, когда не существует элементаx  A такого, что a ≺ x ( x ≺ a ).Пример 4.9. В примере 4.4 минимальными элементами будут сотрудники предприятия, которые не имеют никого в своем подчинении(обозначены кружками или овальными рамками), а наименьшие элементы отсутствуют. В этом же примере единственным максимальным, атакже наибольшим элементом является директор.Пример 4.10.

В примере 4.3 единственным минимальным, а такженаименьшим элементом является множество  , а единственным максимальным, а также наибольшим элементом – множество U .Пример 4.11. В примерах 4.1, 4.2 отсутствуют минимальные, максимальные, наименьшие, наибольшие элементы.Утверждение 4.2. Пусть A – частично упорядоченное множество,a – наибольший (наименьший) элемент на множестве A . Тогда a –единственный максимальный (минимальный) элемент на A .Доказательство.

Будем проводить рассуждения для наибольшегоэлемента a (для наименьшего элемента a рассуждения аналогичны).Докажем, что элемент a является максимальным. Действительно, длялюбого элемента x  A такого, что a ≼ x , имеем: a ≼ x , x ≼ a (используем то, что a – наибольший элемент на A ), откуда в силу антисимметричности ≼, выполняется a  x . Пусть теперь a1 – еще один максимальный элемент на A . Тогда из того, что a – наибольший элементна A , имеем: a1 ≼ a , откуда, используя то, что a1 – максимальныйэлемент на A , получаем, что a1  a .Пусть A – частично упорядоченное множество, x, y  A . Будемговорить, что y покрывает x , если (а) x ≺ y ; (б) не существует эле56мента z  A такого, что x ≺ z ≺ y .Пример 4.12.

Натуральные числа упорядочены естественным образом по возрастанию: 1  2  3  4  5  ... . В этом примере 5 покрывает 4; 4 покрывает 3. Однако, 5 не покрывает 3, поскольку 3  4  5 .Пример 4.13. Рассмотрим отношение  на множестве действительных чисел [0;1] . В этом примере не существует x, y  [0;1] таких,что y покрывает x . Предположим, например, что число 1 покрываетчисло x  [0;1] . Тогда x  1 , откуда x  ( x  1) / 2  1 , а это противоречит тому, что 1 покрывает x .Частично упорядоченные конечные множества.

ДиаграммыХассе. Основным утверждением этого раздела являетсяУтверждение 4.3. Пусть A – частично упорядоченное конечноемножество. Тогда для любых элементов x, y  A для того, чтобы выполнялось условие x ≺ y необходимо и достаточно, чтобы нашлись:k  2 , x1 , x2 ,..., xk  A такие, что x  x1 ≺ x 2 ≺…≺ xk  y , и при этомi  {2,..., k} x i покрывает xi 1 .Идея доказательства. Возможны два случая: (а) y покрывает x ив этом случае доказываемое утверждение выполняется при k  2 , x  x1 ≺ x2  y ; (б) y не покрывает x . В случае (б) z  A : x ≺ z ≺ y.Далее, отдельно рассматриваем две пары элементов: x, z и z, y .

Теперь уже возможны четыре случая: z покрывает (или не покрывает) x ;y покрывает (или не покрывает) z . В любом из случаев покрытиячасть требуемой последовательности оказывается найденной. В противных случаях найдутся очередные промежуточные элементы. Например,в случае, когда z не покрывает x и y не покрывает z , z1 , z 2  A : x ≺≺ z1 ≺ z ≺ z 2 ≺ y . В последнем случае отдельно рассматриваем уже четыре пары элементов: x , z1 ; z1 , z ; z , z 2 ; z 2 , y . Поскольку, в силутранзитивности ≺ (см. упражнение 4.1), последовательность выделяемых таким образом элементов множества A состоит из попарно различных членов, то, в силу конечности A , указанный процесс генериро57вания новых членов последовательности не является бесконечным и нанекотором этапе получим конечную последовательность элементовмножества A , удовлетворяющую нашим требованиям.Утверждение 4.3 позволяет представить любое частично упорядоченное конечное множество A в виде наглядной схемы, называемойдиаграммой Хассе.

Элементы из A изображаются точками (маленькимикружочками), расположенными на схеме в соответствии со следующимправилом. Если элемент y покрывает элемент x , то точка, изображающая x , располагается ниже точки, изображающей y , и при этом этиточки соединяются прямолинейным отрезком. Таким образом, в силуутверждения 4.3, x ≺ y равносильно тому, что на диаграмме найдетсяломаная линия, «восходящая» от x к y (т.е. при движении по этой ломаной от точки x к точке y будем всегда подниматься вверх).Используя диаграмму Хассе, соответствующую некоторому конечному множеству A , с заданным на нем отношением частичного порядка ≼ , нетрудно перечислить все упорядоченные пары, принадлежащиебинарному отношению ≼, а также определить минимальные и максимальные элементы. Действительно, в силу утверждений 4.1, 4.3, минимальным элементам соответствуют точки, не связанные прямолинейными отрезками с другими точками, находящимися ниже их (шуточноговоря: у них «ножек нет»).

А максимальным элементам будут соответствовать точки, не связанные прямолинейными отрезками с другимиточками, находящимися выше их (шуточно говоря: у них «рожек нет»).Пример 4.14. Примером диаграммы Хассе является схема подчиненности на множестве должностей предприятия (см. рис 4.1).Упражнение 4.2. Диаграмма Хассе, соответствующая частичномупорядку ≼, заданному на множестве A  {a, b, c, d , e, f , g , h, i} , представлена рис.4.2. Определить все упорядоченные пары, принадлежащие≼, минимальные и максимальные элементы, а также сегмент [a, b] .58bgfdiechaРис.4.2Решение. По определению частичного порядка, бинарное отношение ≼ является рефлексивным, а следовательно, ему принадлежат всепары вида x, x , где x  A . Другие пары, принадлежащие ≼, определяем из диаграммы Хассе, используя соединения элементов прямолинейными отрезками и транзитивность ≼.

Например, для элемента aимеем: a ≺ i ; a ≺ i ≺ f  a ≺ f ; a ≺ i ≺ g  a ≺ g ; a ≺ i ≺ f ≺ b  a ≺ b , откуда следует, что этому частичному порядку принадлежатпары: a,i , a, f , a, g , a, b . Действуя аналогичным образом, получаем следующее множество упорядоченных пар, принадлежащих ≼:{ a, a , b, b ,..., i, i , a,i , a, f , a, g , a, b , c, i , c, g , c, f ,c,b , d , g , d , b , e, f , e, b , f , b , g , b , h, i , h, f , h, g ,h,b , i, g , i, f , i,b } . При этом b – максимален на A ; a, c, d , e, h– минимальны; [a, b]  {x  A | a ≼ x ≼ b}  {a, b, f , g , i} .Утверждение 4.4. Пусть A – конечное частично упорядоченноемножество, a  A . Тогда найдутся элементы a0 , b0  A такие, что a0 –минимален на A , b0 – максимален на A и при этом a0 ≼ a ≼ b0 .Доказательство.

Докажем существование a0 (для b 0 рассуждениеаналогично). Если a – минимален на A , то полагаем a0  a и приэтом a 0 ≼ a . В противном случае, найдется a1  A : a1 ≺ a . Если a1 –минимален на A , то полагаем a0  a1 и при этом a0  a1 ≺ a . В про59тивном случае, найдется a2  A : a 2 ≺ a1 .

Если a 2 – минимален на A ,то полагаем a0  a 2 и при этом a 2 ≺ a1 ≺ a  a0  a 2 ≺ a (см. упражнение 4.1). В противном случае переходим к рассмотрению элементаa 3 ≺ a 2 и т.д. Далее возможны два случая. Либо на некотором k -омэтапе (где k  3 ) мы получим конечную последовательность элементовa1 ,..., ak таких, чтоa k ≺ a k 1 ≺…≺ a1 ≺ a ,(4.1)и при этом a k минимален на A . Тогда, в силу транзитивности ≺ (см.упражнение 4.1), используя (4.1), получаем a k ≺ a , т.е. в этом случаеможно положить a0  a k . Либо для любого номера k  1 элемент a kуказанной последовательности не является минимальным на A . Однако, этот случай противоречит конечности множества A , поскольку, всилу транзитивности ≺ (см. упражнение 4.1), из (4.1) следует, что всечлены этой последовательности попарно различны.Утверждение 4.5.

Пусть A – конечное частично упорядоченноемножество, и множество минимальных (максимальных) элементов наA состоит из единственного элемента a0 . Тогда a0 является наименьшим (наибольшим) элементом на A .Доказательство. Будем рассматривать случай, когда a0 – единственный минимальный элемент (случай, когда a0 – единственный максимальный элемент, рассматривается аналогично).