§ 39. Конечные структуры

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

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

Напомним вкратце некоторые определения.

Упорядоченное множество. Упорядоченное множество — это множество на котором определено отношение порядка Оно обозначается Рассматриваемые в этом параграфе отношения порядка (если не уточнено) не строгие.

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

Рис. 175

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

Частично упорядоченное множество. Частично упорядоченное множество — это упорядоченное множество, не являющееся линейно упорядоченным.

Цепь. Цепь — это линейно упорядоченная часть упорядоченного множества.

Пример (рис. 175). Введем отношение порядка: если Так как не все элементы сравнимы (например, , то множество вершин частично упорядочено. Подмножества цепи.

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

Например, на рис. 175 элементы минимальные, а максимальные.

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

Например, упорядоченное множество на рис. 175 не обладает ни наименьшим (так как несравнимы), ни наибольшим (так как несравнимы) элементами. Упорядоченное подмножество обладает наибольшим элементом а наименьшего элемента нет. Множество на рис. 176 обладает как наименьшим элементом А, так и наибольшим элементом В.

Миноранта (мажоранта). Рассмотрим упорядоченное подмножество А упорядоченного множества с введенным в отношением порядка.

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

Рис. 176.

Говорят, что А минорируется (мажорируется) в Например, на рис. 175 В — миноранта мажоранта — мажоранта — миноранта

Заметим, что если У — миноранта (мажоранта) то он является наименьшим (наибольшим) элементом А.

Нижняя (верхняя) грань. Обозначим через множество минорант (мажорант) подмножества Если допускает наибольший (наименьший) элемент У, то У называют нижней (верхней) гранью А. В частности, если А обладает наименьшим (наибольшим) элементом У, то он и является нижней (верхней) гранью А.

Например, на рис. множество минорант для подмножества Так как наибольший элемент то нижняя грань А. Аналогично верхняя грань

Максимальная цепь. Цепь С называется максимальной, если она не содержится строго ни в какой другой цепи.

Пр и мер 1. Граф на рис. 177 можно рассматривать как множество с отношением порядка: если Цепи максимальные, цепи не максимальные.

Пример 2. Рассмотрим множество делителей числа 36, упорядоченное отношением делит X,» (рис. 178). Цепь максимальная, так как для любого элемента из можно найти элемент из С, не сравнимый с ним. Очевидно, что не максимальная цепь.

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

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

Рис. 177.

Рис. 178.

Пример 1. Упорядоченное множество на рис. 179 — верхняя полуструктура. Действительно,

Это не нижняя полуструктура, так как не обладает нижней гранью. Если на рис. 179 изменить направление стрелок на обратное, то для упорядоченного таким образом множества справедливо обратное утверждение.

Рис. 179.

Пример 2. Любая цепь является одновременно верхней и нижней полуструктурой, как, например, множество на рис. 179. То же справедливо для множества на рис. 178.

Пример 3. Множество подмножеств из упорядоченное по включению, — одновременно верхняя и нижняя полуструктура. Действительно, если то

Структуры. Упорядоченное множество, являющееся одновременно верхней и нижней полуструктурой, называют структурой, или решеткой.

Примеры структур: упорядоченное множество на рис. 180; множество всех подмножеств множества

(рис 181); множество делителей числа 36, упорядоченное отношением делимости (рис. 178).

Рис. 180

Рис. 181

Подструктуры. Пусть структура и подмножество А упорядочено введенным в отношением порядка.

Рис. 182

Рис. 183.

Назовем А подструктурой структуры если для любых двух элементов верхняя и нижняя грани

принадлежат А, т. е.

или

Примеры подструктур: подструктура структуры (рис. 182); подструктура структуры где (рис. 183);

множество

— подструктура структуры делителей числа 36 (рис. 184), а множество

— не подструктура этой структуры (рис 185), так как и, более того, в В не существует верхней грани для в силу того, что множество его мажорант не обладает наименьшим элементом в В;

Рис. 184

Рис. 185

подмножество (рис. 186)

— не подструктура структуры так как и , однако легко убедиться, что С — структура, множество упорядоченное по включению, не является подструктурой структуры так как оно вообще не структура (не является ни верхней, ни нижней подструктурой)

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

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

Будем рассматривать теперь как операции на множестве

Тогда свойство множества быть структурой эквивалентно условию

Операции можно рассматривать как отображения которые каждой паре из сопоставляют соответственно из эти операции — внутренние законы композиции.

Рис. 186

Для любых элементов справедливы следующие соотношения

Об аксиоматической теории структур см Г. Биркгоф, Теория структур, ИЛ, 1952.

Двойственность. Из формул (39 20) - (39 27) вытекает, что любая формула, относящаяся к структурам, имеет двойственную, которая получается из нее, если произвести замены: Например, формула

двойственна формуле

Модулярные структуры. Для любых элементов структуры справедливо

Докажем теперь свойство, называемое свойством «слабой дистрибутивности»

Предварительно докажем

где X — произвольный элемент По определению нижней грани и так как А В, то поэтому так как наиботьшая из минорант для Аналогично

В силу определения верхней грани и из (39.32) имеем

или

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

Элемент мажорирует элементы и следовательно, и их верхнюю грань:

что и требовалось доказать. В силу двойственности

Если примем то и в силу (39.31)

Определение Говорят, что структура модулярна, если для любых ее трех элементов имеем

Замечание. Если два из элементов равны между собой, то это соотношение выполняется для любой структуры (свойство поглощения).

Пример: Рассмотрим структуру на рис 187 и проверим для нее (39.40). Легко видеть, что верхняя, нижняя грань для любой пары элементов Как уже отмечалось, достаточно рассмотреть тройки различных элементов, два из которых сравнимы. В каждой такой тройке присутствует либо либо О, так как любые два из элементов несравнимы.

Рис. 187

Для определенности рассмотрим тройки с и проверим

Так как для любого

то имеем

т. е.

и структура модулярная.

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

Рассмотрим, например, структуру на рис 188, а) максимальные цепи Изображая их, как на рис. 188,5), и стирая стрелки, получаем диаграмму Хассе (рис 188, в). На рис 189—191 приведены другие примеры диаграмм Хассе.

Дистрибутивные структуры. Структура дистрибутивна, если выполнено условие

или двойственное ему условие

Например, структура, представленная диаграммой Хассе на рис. 192, дистрибутивна. Действительно,

так как

Теорема. Всякая дистрибутивная структура модулярна.

Рис. 188.

В самом деле, для любых элементов дистрибутивной структуры выполняется

Если

то

так как

Теорема. Всякая подструктура дистрибутивной структуры дистрибутивна.

Пусть любые элементы подструктуры структуры Тогда

Структуры с дополнениями. Дополнение. Рассмотрим структуру содержащую «нулевой» элемент О, являющийся нижней гранью и «универсальный» элемент являющийся верхней гранью Элемент называют дополнением элемента X, если

(кликните для просмотра скана)

Например, для структуры на рис 193 имеем

а элементы структуры на рис. 194 не обладают дополнениями.

Теорема. Если элемент А дистрибутивной структуры обладает дополнением, оно единственно.

Рис. 193

Рис. 194

Предположим противное, т. е. что два дополнения Л:

откуда

Покажем, что

По предположению

и можно записать

Аналогично

Итак,

Структура с дополнениями. Говорят, что структура с дополнениями, если:

1) она обладает нулевым элементом и универсальным элементом

2) каждый элемент из обладает по крайней мере одним дополнением.

Например, структура на рис. 195 является структурой с дополнениями:

Структура на рис. 190 также является структурой с дополнениями, в то время как структура на рис. 194 не будет таковой.

Рис. 195.

Рис. 196.

Булевы структуры. Дистрибутивная структура с дополнениями называется булевой.

Например, на рис 196 диаграммой Хассе представлена такая структура. Действительно,

и легко проверить, что она дистрибутивна

Теорема Каждый элемент булевой структуры обладает одним и только одним дополнением.

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

Теорема II. Для каждого элемента X булевой структуры справедливо

Это следствие теоремы

Теорема III. Для любых двух элементов булевой структуры выполняются соотношения.

Так как эти соотношения двойственны, то достаточно проверить одно из них. Для этого достаточно показать, что

Действительно,

Аналогично

Примеры Структура на рис. 197 дистрибутивна, но не является структурой с дополнениями, поэтому она не булева.

Структура подмножеств, упорядоченных по включению, булева, если дополнение для определить как

Формулы (39 66) и (39 67) принимают вид

— известные в теории множеств формулы де Моргана

На рис 198—201 приведены

соответственно

Теорема IV. Всякая конечная булева структура представляется как структура подмножеств (по включению) некоторого множества и обратно

Рис. 197

Рис. 198

Рис. 199

Утверждение следует из того, что свойства (39 72) выражают то же самое, что и свойства, с помощью которых определяется дистрибутивная структура с дополнениями, а именно:

Рис. 200

Рис. 201

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

Подструктуры булевой структуры. Всякая подструктура булевой структуры называется булевой подструктурой для если она содержит и обладает свойствами булевой структуры.

Например, подмножества (см. рис. 203)

множества

образуют булеву подструктуру булевой структуры на рис. 202.

Гиперкуб. Рассматривая рис. 199 и 200, легко заметить, что это — квадрат и куб (вообще говоря, ромб и параллелепипед). По аналогии принимаем, что на рис. 201 представлен гиперкуб порядка 4, а на рис. 198 — гиперкуб порядка 1. Назовем точку гиперкубом порядка 0, отрезок — гиперкубом порядка 1, квадрат — гиперкубом порядка 2, куб — гиперкубом порядка 3 и т. д.

Рис. 202.

Рис. 203.

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

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

(так как каждое ребро учитывалось при подсчете дважды). Очевидно, что число граней (гиперкубов порядка 2) гиперкуба порядка подсчитывается аналогично:

Вообще число гиперкубов порядка в гиперкубе порядка равно

Таким образом, гиперкуб на рис. 201 содержит 8 кубов, 24 квадрата, 32 отрезка, 16 вершин.

Векторные структуры. Пусть заданы конечных множеств

Предположим, что они линейно упорядоченные:

Определим отношение доминирования для элементов

Полагаем

если все элементы -выборки в левой части меньше или равны соответствующим элементам -выборки в правой части и по крайней мере в одном случае имеет место строгое неравенство.

Рис. 204.

Рис. 205.

Тогда становится структурой относительно введенного отношения и называется векторной структурой.

Пример такой структуры приведен на рис. 204:

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

Лексикографические векторные структуры. Это — векторные структуры с линейным порядком (как слова в словаре). Рассмотрим следующее отношение доминирования. Считаем, что

-выборка доминирует -выборку , если первые элементов (считая слева) этих выборок совпадают, а элемент первой выборки больше (в смысле заданного порядка) элемента второй выборки. Например, (3, 5, 7, 2, 5) доминирует доминирует если буквы упорядочены, как в русском алфавите.

Другой пример лексикографической векторной структуры дает система счисления с основанием 10; например, 35 725 больше 35 719. На рис. 205 изображена диаграмма Хассе трехмерной лексикографической векторной структуры, образованной числами в двоичной записи.

УПРАЖНЕНИЯ

(см. скан)

(см. скан)

(см. скан)