2.23. Отношение порядка

Существуют отношения, которые определяют порядок расположения элементов множества. Так, мы можем вводить понятия «больше», «меньше», «раньше», «позже» и т.д. Задав эти отношения, можно расположить элементы, например, в порядке возрастания, убывания их значений и др. Такое расположение элементов называют введением отношения порядка на некотором множестве , а множество с заданным на нём отношением порядка называют упорядоченным множеством. Если любые два элемента множества и находятся в отношении порядка или , то такое множество называется линейно упорядоченным множеством. Различают отношение нестрогого и строгого порядка. Допустим, что на некотором множестве задано бинарное отношение : , .

Отношение будем называть отношением нестрогого порядка, если оно обладает следующими свойствами:

- рефлексивности , или в инфиксной форме , в префиксной форме , в постфиксной форме ;

- антисимметричности

,

или в инфиксной форме ,

в префиксной форме ,

в постфиксной форме ;

- транзитивности

,

или в инфиксной форме ,

в префиксной форме ,

в постфиксной форме .

Отношение нестрогого порядка называют ещё частичным порядком. Множество с отношением частичного порядка называется частично упорядоченным.

Отношение будем называть отношением строгого порядка, если оно обладает следующими свойствами:

- антирефлексивности

или в инфиксной форме ,

в префиксной форме ,

в постфиксной форме ;

- несимметричности ,

или в инфиксной форме ,

в префиксной форме ,

в постфиксной форме

,

- транзитивности.

Элементы и называются сравнимыми, если имеет место или ( или ). Будем говорить, что элемент предшествует элементу , или элемент следует за элементом , если имеет место (или .

2.24. Изоморфизм отношений

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

.

Это свойство называется согласованностью отображения с отношениями . Такое отображение называется морфизмом. При этом если отображение сюрьективно, то оно называется гомоморфизмом, если инъкктивно, то мономорфизмом, если биективно, то изоморфизмом. Если отображение является изоморфизмом, то говорят, что множество изоморфно множеству , или множество изоморфно вкладывается в множество .

Теорема 2.2

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

Доказательство

Рассмотрим любое произвольное множество . Зададим на нём отношение частичного порядка , . Рассмотрим на множестве множество подмножеств . Элементы образуются следующим образом. Для каждого рассматривается такое подмножество элементов, , которые находятся с элементом в отношении : . В подмножестве рассмотрим элемент и образуем подмножество таких элементов , которые находятся в отношении с элементом : . В подмножестве возьмём элемент и создадим множество таких элементов , которые находятся в отношении с элементом : , и т.д. На множествах и зададим отображение , такое, что , , ,… . Так как . Тогда , т.е. имеется согласование отображения с отношением и отношением включения .

2.25. Решётки

Рассмотрим некоторое множество с отношением частичного порядка : , . В множестве рассмотрим подмножество . Если найдётся такой элемент , такой, что для любого справедливо (или ), то элемент называется мажорантой множества . Аналогично, если , что для справедливо , то элемент называется минорантой множества . Рассмотрим множество мажорант . Если в множестве имеется такой элемент , что для любого другого элемента справедливо , то такой элемент называют точной верхней гранью множества : . Точная верхняя грань обозначается как объединение: . Этот элемент называется единичным и обозначается «1». Аналогично, если , что для справедливо , то элемент называют ночной нижней гранью множества : .Точная нижняя грань обозначается как пересечение . В точной нижней и точной верхней гранях обозначения объединения и пересечения не имеют ничего общего с теоретико-множественными операциями объединения и пересечения. Если множество упорядочено отношением включения и для двух элементов и существует и , то это объединение и пересечение, как теоретико-множественные операции, можно рассматривать как точную верхнюю и точную нижнюю грани.

Если множество упорядочено отношением , то для элементов и , для которых в качестве пересечения рассматривается минимальный элемент , а в качестве объединения – максимальный элемент .

Определение 2.1.

Решёткой называется частично упорядоченное множество, для любых элементов которых и имеется объединение (или точная верхняя грань) и пересечение (или точная нижняя грань).

Примеры решёток.

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

2. Пусть множество натуральных чисел. Определим на множестве отношение частичного порядка следующим образом. Будем считать, что , если является делителем . Тогда наименьшее общее кратное, а наибольший общий делитель.

3. Рассмотрим множество , упорядоченное отношением включения. Для каждого множества существует множество , элементами которого являются подмножества и только они. Такое множество называется булеаном этого множества. Множество при этом называется универсумом и обозначается «1». Рассмотрим образование булеана от универсума :

.

Число элементов булеана , т.е. его мощность, составит , где мощность универсума. Система с отношением включения является решёткой. В качестве точной верхней и нижней граней выступают теоретико-множественные операции объединения и пересечения элементов множества .