Отношение порядка. Упорядоченные множества

Определение 2.12. Бинарное отношение у?, заданное на множестве Л, называется отношением порядка, если оно обладает свойствами:

  • 1) рефлексивности (для любого a G А а р а);
  • 2) транзитивности (если а р Ь и с, то а (ре);
  • 3) антисимметричности (если apb и bра, то а = Ь).

Отношение порядка играет важную роль в математике, для него принято специальное обозначение «^». В этих обозначениях свойства рефлексивности, транзитивности и антисимметричности записываются следующим образом:

  • 1) а^а для всех а;
  • 2) если а^Ь и 6^с, то а ^с;
  • 3) если а ^ b и 6^ а, то а — Ь.

Запись а^Ь означает, что пара (а,6) принадлежит отношению порядка р) ((а, 6) G у? С А хА). Про элемент а при этом говорят, что он меньше либо равен (не превосходит) b или, что он содержится в Ь. Отношение (р-1, обратное к отношению порядка (р (ap~l Ь^гЬр а), само является отношением порядка. Порядок (^)-1 называют двойственным к ^ и обозначают символом Будем писать а<6, если а^b и афЪ. Таким образом, мы задали отношение строгого порядка, которое обладает только свойствами транзитивности и антисимметричности.

Определение 2.13. Частично упорядоченным множеством называется множество, на котором задано отношение порядка.

Таким образом, частично упорядоченное множество определяется двумя объектами: самим множеством А и определенным на нем отношением порядка - (А; ^). При этом на одном и том же множестве порядок можно задать различными способами, т. е. получить различные частично упорядоченные множества. В частности, таким образом получается так называемое двойственное частично упорядоченное множество (Л; (^)-1).

П р и м е р 2.7. Показать, что множество М = {а, 6, с, 0,1} с заданным на нем бинарным отношением Р = {(0,0), (0, а), (0,6), (0, с), (0,1), (а, а), (а, 1), (М), (М), (с, с), (с, 1), (1,1)} является частично упорядоченным множеством.

Отношение Р задано перечислением пар, следовательно, тот факт, что оно рефлексивно и антисимметрично очевиден. Транзитивность отношения Р означает, что (х, у) ? Р и (?у, z) ? Р=> (.х, z) ? Р для любых элементов х, /у, г из множества М. Если а; = 0, то при любых у, г? Л/ пара (0, г) ? Р. При х^0 отношению Р принадлежат только пары вида (х,х) и (ж, 1), в любом случае легко видеть, что транзитивность имеет место. Таким образом, отношение Р задает порядок на множестве М, превращая его в частично упорядоченное множество.

Пр и мер 2.8. Показать, что множество натуральных чисел N с определенным на нем отношением у?: apb^b делится на а без остатка, является частично упорядоченным множеством.

Достаточно убедиться, что данное отношение является отношением порядка. Очевидно, что отношение р рефлексивно. Если число b делится на число а, а с делится на 6, то с делится на а, т. е. отношение р транзитивно. Покажем антисимметричность отношения р. Если apb и b р а, то, Ь=ак и а = Ьт, где к и т целые числа. Откуда получаем равенство а = акт, значит кт= 1, что для целых чисел означает к = т= 1, следовательно, а = Ь. Таким образом, отношение у? является отношением порядка на множестве натуральных чисел, а система (N; (р) - частично у по ря д о че н н ы м м н оже ств о м.

Очевидно, что множество натуральных чисел N с обычным отношением порядка Д (а^6<4>6 — а^О) - это частично упорядоченное множество. Таким образом, мы имеем дело с одним и тем же множеством N. но с различными частично упорядоченными множествами: (N; и (М;Д.

С другой стороны, если на множестве А = {2,4, б, 10,60} отношение порядка определено так же, как в примере 2.8, то достаточно очевидно, что это частично упорядоченное множество устроено так же, как и множество в примере 2.7, в смысле отношения порядка. Фактически, если «переобозначить» элементы множества А (2<-»0, 4<->а, 6<->Ь, 10<-»с, 60 1), то получим упорядоченное множество из примера 2.7. Такое «переобозначение» можно сделать не единственным образом, но суть его состоит в том, что мы нашли взаимно однозначное соответствие между множествами А и М, причем такое, которое «сохраняет» отношение порядка. Таким образом, мы приходим к понятию изоморфизма упорядоченных множеств.

Пусть А и А' - два частично упорядоченных множества и д взаимно однозначное отображение А на А'. Отображение д называется сохраняющим порядок, если из того, что а ^ b (а, 6бЛ), следует, что д(а)^д(Ь).

Определение 2.14. Взаимно однозначное отображение g частично упорядоченного множества А на А! называется изоморфизмом, а сами частично упорядоченные множества А и А' изоморфными, если g(a)^g(b) тогда и только тогда, когда а^Ь (а, 6 ? А).

Между частично упорядоченными множествами (N; и (N; р) из примера 2.8 существует взаимно однозначное отображение у, которое сохраняет порядок. Таковым является тождественное отображение g(n) = n (п ? N). Действительно, из atpb (а, б? N и а делит 6), следует, что д(а) ^д(Ь) или а Д Ь. Но эти частично упорядоченные множества не являются изоморфными. Действительно, в частично упорядоченном множестве (N; сравнима любая пара элементов, т. е. для любых натуральных чисел т и п либо т Дп, либо п^т. А в частично упорядоченном множестве (N;<р) существуют пары несравнимых элементов, например, т = Ъ и п = 3 ((5,3)^у) и (3,5)&ф).

Изоморфизм частично упорядоченных множеств является отношением эквивалентности на некоторой совокупности частично упорядоченных множеств и разбивает эту совокупность на классы изоморфных между собой множеств. В том случае, когда нас интересует не природа элементов частично упорядоченных множеств, а только отношения порядка на них, можно отождествлять изоморфные между собой частично упорядоченные множества.

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

Определение 2.15. Частично упорядоченное множество (А; называется линейно упорядоченным, если в нем сравнимы любые два элемента, т. е. для любых а и b из А либо а ДЬ. либо 6Да.

Частично упорядоченное множество (N; линейно упорядочено.

В примерах 2.7 и 2.8 множества таковыми не являются. Действительно, в примере 2.8 натуральное число 2 несравнимо с любым натуральным нечетным числом, а в примере 2.7 - несравнимы между собой элементы а, Ъ, с.

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

Для линейно упорядоченных множеств, как для любого частично упорядоченного множества, применимо понятие отображения, сохраняющего порядок, и, в частности, понятие изоморфизма.

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

Определение 2.16. Элемент а частично упорядоченного множества А называется минимальным (наименьшим), если из b ^ а следует, что Ь=а. По аналогии элемент с частично упорядоченного множества А называется максимальным (наибольшим), если из с Ь следует, что Ь—с.

Определение 2.17. Линейно упорядоченное множество называется вполне упорядоченным, если любое его непустое подмножество имеет минимальный (наименьший) элемент.

Множество всех рациональных чисел по отношению к естественному порядку (^) является линейно упорядоченным, но не вполне упорядоченным, так как в нем нет минимального (и максимального) элемента.

Множество всех рациональных чисел отрезка [0, 1] (с естественным отношением порядка) имеет минимальный элемент - 0 и максимальный элемент - 1, но не является вполне упорядоченным множеством, так как, например, его подмножество положительных рациональных чисел наименьшего элемента не имеет.

Множество натуральных чисел N (с естественным отношением порядка) не имеет наибольшего элемента, но имеет наименьший элемент - 1. В силу того, что любое его непустое подмножество обладает наименьшим элементом, N является не только линейно упорядоченным, но и вполне упорядоченным множеством.

Ясно, что всякое (непустое) подмножество вполне упорядоченного множества само вполне упорядочено.

Частично упорядоченные множества можно изобразить графически (как бинарное отношение), но поскольку любое отношение порядка рефлексивно и транзитивно, то из соответствующей диаграммы удаляют все петли и транзитивно замыкающие дуги. Такие диаграммы, задающие частично упорядоченные множества, называются диаграммами Хассе. Диаграммы Хассе известны с конца XIX века, их применяли в генеалогии для задания родства.

П р и мер 2.9. Изобразить диаграммы Хассе, соответствующие упорядоченным множествам: (Л; и (Л; a ip bob делится на а без остатка.

Соответствующие диаграммы Хассе имеют вид

Рис. 5

Рис. 6

Очевидно, что эти два частично упорядоченных множества неизоморфны.

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ     След >