Расширение упорядоченного множества до полной решетки.

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

О п р е д е л е н и е  1. Реляционная система  называется подсистемой системы , если  и  (т.е. ).

О п р е д е л е н и е  2. Система  называется расширением системы , если существует подсистема  системы , изоморфная .

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

Теорема 1. Каждое упорядоченное множество можно погрузить в семейство всех подмножеств некоторого множества (упорядоченное отношение включения) и, значит, в некоторое полное атомарное булево кольцо.

Д о к а з а т е л ь с т в о.  Обозначим . Из транзитивности отношения  следует, что . Т.к. , то . Таким образом, , откуда .

Следовательно, функция  погружает  в семейство множеств , упорядоченное отношением . Это семейство, очевидно, можно расширить до семейства , где .

Расширение, описанное в теореме 1, не сохраняет, вообще говоря, граней, т.е. из равенства  (или ) не следует  (или  ).

Займемся теперь вопросом, можно ли расширить множество  до полной решетки с сохранением граней.

Пусть функция  погружает упорядоченную систему  в упорядоченную систему .

О п р е д е л е н и е  3. Погружение  сохраняет верхние грани, если для каждого множества  и каждой функции , для которой существует , существует также  и . Аналогично для нижних граней.

Построим теперь расширение упорядоченного множества до полной решетки с сохранением граней.

Пусть  - множество, упорядоченное отношением . Для произвольного множества  положим

,

.

Из этих определений непосредственно следует, что

(1),

 и  для любого   (2).

Действительно, по определению , поэтому .

Доказательство второго утверждения аналогично.

      (3)

Включение  следует из (2). Пусть . Тогда  и тем более , поскольку . Таким образом, .

Второе равенство доказывается аналогично.

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

Пара множеств  называется сечением упорядоченного множества , если  и .

Множество  называется нижним классом, а - верхним классом сечения.

Из этого следует, что     (4).

В самом деле, каждый элемент множества  находится в отношении  к каждому элементу множества . Далее, в силу (3) каждая пара вида  и каждая пара вида  являются сечениями. Любое сечение можно представить в любом из этих видов.

Наконец, по определению сечения, пара , где  является сечением (6).

Введем отношение порядка между сечениями: . Для проверки того, что отношение  здесь действительно - отношение порядка, докажем, что   (7).

Пусть  и . Если , то , а поэтому . Отсюда  и, значит, . Аналогично доказывается обратная к (7) импликация.

Обозначим через β - семейство всех сечений.

β - полная решетка (8).

Пусть . Обозначим :

, .

Сечение  является наименьшей верхней гранью множества £. Действительно, , следовательно,  для каждого .

Если  для каждого , то , а поэтому . Отсюда , и тогда .

Аналогично доказывается, что сечение  является наибольшей нижней гранью множества £.

(9) Функция  погружает  в β  с сохранением граней.

Доказательство. Из определений следует, что . Возьмем  в множестве . Тогда , а поэтому  для . Пусть сечение  таково, что  для . Тогда , а т.к. , то . Значит,  для любого , откуда следует, что . Поэтому , откуда  и . Таким образом,  в множестве β. Для нижней грани доказательство аналогично.

Из (9) следует

Теорема 2. Каждое упорядоченное множество  можно расширить с сохранением граней до полной решетки β.

Построенную выше решетку β назовем минимальным расширением упорядоченного множества .

Займемся более подробно случаем, когда  - булево кольцо.

Сначала заметим, что если  и  - произвольные подмножества упорядоченного множества , то

             (10)

Пусть теперь - решетка. Докажем, что если  и  - верхние классы двух сечений в , то  - множество всех элементов вида , где  для .

Действительно,  и, значит,  для . Кроме того, .

Аналогично доказывается, что если  и  - нижние классы двух сечений в , то  - множество всех элементов вида , где  для .

Из этих замечаний и равенств (10) получаем, что если - решетка и - два ее сечения, то

,

 (11).

Из определения граней в решетке β (смотреть доказательство утверждения 8) следует, что для любого упорядоченного множества и любых двух его сечений :

 (12),

 (13).

Наконец, пусть - булево кольцо и  для произвольного множества . Если  - сечение в , то  - также сечение в .

Доказательство (14) самостоятельно.