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

Частично упорядоченные множества ) и(Y, ) изоморфны, если чуществует биекция, сохраняющая отношение порядка, т.е.таких, что, выполняется .

Пример. Рассмотрим множествоTточек горизонтальной прямой, упорядоченное отношениемL– “лежит левее или совпадает”, и множество действительных чиселRс введенным на нем отношением порядка “”. Тогда (T,L) изоморфно(R,) и, решив задачу на множествеR, мы иллюстрируем решение с помощью множестваT, так как структура этих множеств одинакова.

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

Пример. Рассмотрим частично упорядоченное множество (X,) из 1.2.7. Так каксостоит изэлементов, то его булеанB(X)содержитэлементов – подмножеств множестваX. Выберем из них 4 подмножества следующим образом: сопоставим каждому элементуподмножество B(X), включающее те и только те элементыy, которые являются делителями элементаx:

.

Получим множество B(X), где , , , . Частично упорядоченные множества (X,) и () изоморфны (рис. 1.10).

Доказательство теоремы. Пусть задано произвольное упорядоченное множество).Построим подмножество B(X)с помощью соответствия: каждому элементусопоставимx} и обозначим.

Покажем, что соответствие является биекцией, т.е. выполняются условияа–гопределения биекции из 1.2.1. Условияа–ввыполняются согласно способу построения множестваF: каждый элементимеет единственный прообраз, а каждый элементмножестваFимеет прообраз. Покажем, что этот прообраз – единственный. Предположим противное: существует два различных элемента, имеющие одинаковые прообразыи, т.е., но.

В силу рефлексивности отношения порядка “” имеем:

a  a  b.

Аналогично,

b  b  a.

Так как отношение порядка антисимметрично, получим , что противоречит нашему предположению. Следовательно, различные элементыимеют различные прообразы:, а отображениеявляется биекцией.

Докажем, что биекция сохраняет порядок, т.е. еслииa b, то. Согласно определению включения множеств достаточно показать, чтовыполняется.

Возьмем произвольный элемент . Тогдаx a, ноa b, поэтомуx b(в силу транзитивности отношения порядка) и. Доказано включение.

Итак, построенное отображение B(X)является биекцией, сохраняющей отношение порядка. Следовательно, частично упорядоченные множества (X,) и () изоморфны. Теорема доказана.

1.2.10. Решение задач 5,6 контрольной работы № 1

Задача 5. На множестве задано бинарное отношение:делится на. Представить отно-шениеR различными способами; выяснить, какими свойствами оно обладает; является ли отношениеRотношением эквивалентности или отношением порядка.

Решение. ОтношениеRможно задать перечислением всех элементов:

.

Наглядно представить отношение Rможно с помощью графика (рис. 1.11,а), схемы (рис. 1.11,б), графа (рис. 1.12,а), матрицы отношения (рис. 1.12,б).

Выясним, какими свойствами обладает отношение.

Покажем, что отношение рефлексивно. При условие “делится на 3” принимает вид– делится на 3 (выполняется при любых значениях ).

Проверим, является ли отношение симметричным. Пусть делится на 3 (т.е.). Составим паруи для нее проверим характеристическое свойство отношения:

Очевидно, чтоделится на 3, аделится на 3 по условию, следовательно,делится на 3, т.е.. Отношение симметрично.

Проверим, является ли отношение транзитивным. Пусть и, т.е.делится на 3 иделится на 3. Будет ли делиться на 3 выражение , т.е. будет ли? Преобразуемделится на 3, т.к. первые два слагаемых делятся на 3 по условию и третье слагаемоеделится на 3. Значит, и отношение транзитивно.

Отношение Rобладает свойствами рефлексивности, симметричности, транзитивности, следовательно, является отношением эквивалентности. На графе отношенияR(рис. 1.12,а) хорошо видны классы эквивалентности – это подмножества {1,4}, {2,5}, {3} множестваХ.

Задача 6. Дано множествои отношениеделитель. Показать, что отношениеRявляется отношением порядка. Построить диаграмму Хассе частично упорядоченного множества. Существуют ли в множествеXнаибольший и наименьший элементы? Существуют ли несравнимые элементы?

Решение. Покажем, что отношениеRрефлексивно, антисимметрично и транзитивно.

Рефлексивность имеет место, так как любое число является своим делителем, т.е. .

Пусть одновременно выполняются условия: и. Тогда. Действительно,означает, чтоx– делительy, т.е. найдется целое числоmтакое, что. Одновременно найдется целое числоnтакое, что. Отсюдаи. Последнее равенство выполняется приили, но все элементы множестваX– положительные числа, и второй случай невозможен. Следовательно,, т.е., и отношениеRантисимметрично.

Пусть и, значит, найдутсяZтакие, что,. Тогда, гдеZ. Следовательно,xявляется делителемzи. ОтношениеRтранзитивно.

Отношение R рефлексивно, антисимметрично и транзитивно, т.е. является отношением порядка. Построим диаграмму Хассе частично упорядоченного множества. На нижнем (первом) уровне диаграммы поместим элементы, не имеющие других делителей, кроме себя (и). На втором уровне – элементы, не имеющие других делителей, кроме себя и элементов нижнего уровня (и). Оставшийся элементделится на себя, на все элементы второго и первого уровней – помещаем его на третий уровень. Соединяем отрезком элементы соседних уровней, если элемент нижнего уровня является делителем элемента соседнего верхнего уровня. Диаграмма Хассе построена (рис. 1.13). Пара элементовтогда и только тогда, когда двигаясь по диаграмме только вверх, мы можем пройти от элементаxдо элементаy.

По диаграмме Хассе легко обнаружить несравнимые элементы: 4 и 3; 2 и 3. Наибольшим элементом является (для всехвыполнено условие “xявляется делителем 12”). Наименьшего элемента нет, но есть два минимальных:и.