Определение 2
Множество
называется строго частично упорядоченным,
если выполняются условия:
а) для любого
неверно, что
(антирефлексивность);
б) для любых влечет x<y и y<z влечет x<z (транзитивность);
в) для любых не могут одновременно выполняться соотношения x<y и y<x.
Всякое отношение частичного порядка естественным образом порождает отношение строгого порядка.
Теорема 3
Если
есть отношение частичного порядка, то
отношение
является отношением строгого порядка
на А.
Доказательство
а) Высказывание
ложно, так как ложно второе утверждение
конъюнкции
,
значит, ложно x<x.
б) Пусть x<y и y<z, это значит, истинно высказывание
Из первого и третьего членов этой
коньюнкции следует
.
Осталось доказать, что
.
Допустим, x=z,
тогда получаем
,
то есть x=y,
но по условию
.
Это противоречие и доказывает, что x<z.
в) Допустим, что выполняется конъюнкция
,
то есть
,
но первый и третий член коньюнкции
влекут x=y.
Противоречие. Значит соотношения x<y
и y<x не
могут выполняться одновременно.
Теорема доказана.
Верно и обратное утверждение.
Любой строгий частичный порядок порождает естественным образом просто частичный порядок.
Теорема 4
Пусть на множестве А
задано отношение строго частичного
порядка <,
тогда отношение
является отношением частичного порядка.
Доказательство
Проверим выполнение всех трех условий, определяющих отношение частичного порядка.
а)
–
эта дизъюнкция истинна, так как истинен
ее второй член х=х,
поэтому
.
б) Пусть
,
это значит,
,
что равносильно
.
Отсюда следует:
,
то есть
,
что и означает
.
в) Пусть
,
тогда
.
Это равносильно
.
Первый, второй и третий члены этой дизъюнкции ложны. Первый по свойству в) определения строгого порядка, второй и третий по свойству а). Остается равенство х=у.
Теорема доказана.
§8. Линейно упорядоченные множества. Лексикографический порядок
Как отмечали мы в предыдущем параграфе, есть частично упорядоченные множества, в которых любые два элемента сравнимы, а есть множества, где существуют несравнимые элементы. Это различие подчеркивается следующим определением.
Определение 1
Частично упорядоченное множество
называется линейно упорядоченным,
если выполняется условие:
г) для любых
.
Для строгого порядка это условие принимает вид:
г) для любых
.
Основной целью этого параграфа является изучение так называемых лексикографических порядков, которые в последнее время находят приложение в информатике и в различных разделах математического моделирования.
Определение 2
Пусть
и
–
линейно упорядоченные множества.
Определим на
бинарное отношение следующим образом:
.
Введенное отношение называется отношением лексикографического порядка.
Теорема 3
Если
и
–
линейно упорядоченные множества, тогда
множество
также линейно упорядочено.
Доказательство
Проверим выполнение всех четырех условий линейной упорядоченности.
а) Рефлексивность. Очевидно, что
,
так как выполняется второе условие
дизъюнкции в определении лексикографического
порядка:
.
б) Транзитивность. Пусть
и
.
Если
,
то
и
,
если же
,
то
,
и снова
.
Теперь пусть
,
тогда
и
,
следовательно,
и
,
что и завершает доказательство
транзитивности.
в) Антисимметричность. Пусть
и
.
Из определения лексикографического
порядка получаем
и
,
то есть
.
Из второго "слагаемого"
дизъюнкции в определении лексикографического
порядка теперь получаем
и
.
Следовательно,
.
г) Сравнимость любых двух элементов
множества
.
Пусть
.
Так как
–
линейно упорядоченное множество, то
для элементов
выполнено одно из трех условий:
, тогда ;
,
тогда
;
.
В этом случае для элементов
возможно одно из двух:
, тогда ;
, тогда .
Таким образом, сравнимость, а вместе с ней и вся теорема, доказана.
Таким образом, если
–
линейно упорядоченное множество, то на
множестве
естественным образом также возникает
линейный порядок – лексикографический.
По индукции лексикографический порядок
определяется на множестве
и по индукции же доказывается, что этот
порядок – линейный.
Проиллюстрируем вышеизложенные конструкции примером.
Пусть
.
Расположим в лексикографическом порядке
возрастания элементы множества
:
.