Покрывающее отношение

Диаграмма Хассе из набора мощности из трех элементов, частично упорядоченное по включению .

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

Определение [ править ]

Позвольте быть набор с частичным порядком . Как обычно, пусть будет отношение на такое, что если и только если и .${\ displaystyle X}$${\ displaystyle \ leq}$${\ displaystyle <}$${\ displaystyle X}$${\ Displaystyle х <у}$${\ displaystyle x \ leq y}$${\ Displaystyle х \ neq y}$

Позвольте и быть элементами .${\ displaystyle x}$${\ displaystyle y}$${\ displaystyle X}$

Затем накрывает , пишется , если и нет такого элемента , что . Эквивалентно, покрывает, если интервал является двухэлементным набором .${\ displaystyle y}$ ${\ displaystyle x}$${\ displaystyle x \ lessdot y}$${\ Displaystyle х <у}$${\ displaystyle z}$${\ Displaystyle х <г <у}$${\ displaystyle y}$${\ displaystyle x}$ ${\ Displaystyle [х, у]}$${\ Displaystyle \ {х, у \}}$

Когда говорят, что это прикрытие . Некоторые авторы также используют термин покрытие для обозначения любой такой пары в отношении покрытия.${\ displaystyle x \ lessdot y}$${\ displaystyle y}$${\ displaystyle x}$${\ Displaystyle (х, у)}$

Примеры [ править ]

• В конечном линейно упорядоченном множестве {1, 2, ..., n }, i + 1 покрывает i для всех i от 1 до n - 1 (и других покрывающих отношений нет).
• В булевой алгебре из множества мощности из множества S , подмножество B из S охватывает подмножество A из S , если и только если В получается из А путем добавления одного элемента не в A .
• В решетке Юнга , образованном перегородками всех неотрицательных целых чисел, разбиение λ охватывает разбиение М тогда и только тогда , когда диаграмма Юнга из Х получается из диаграммы Юнга ц путем добавления дополнительного элемента.
• Хасса схема , изображающая охватывающую отношения к решетке Тамарей является скелетом из associahedron .
• Отношение покрытия любой конечной дистрибутивной решетки образует медианный граф .
• На вещественных числах с обычным общим порядком ≤ множество покрытий пусто: ни одно число не покрывает другое.

Свойства [ править ]

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

Ссылки [ править ]

• Кнут, Дональд Э. (2006), Искусство компьютерного программирования , том 4, выпуск 4 , Addison-Wesley, ISBN 0-321-33570-8.
• Стэнли, Ричард П. (1997), Перечислительная комбинаторика , 1 (2-е изд.), Cambridge University Press , ISBN 0-521-55309-1.
• Брайан А. Дэйви; Хилари Энн Пристли (2002), Введение в решетки и порядок (2-е изд.), Cambridge University Press, ISBN 0-521-78451-4, LCCN  2001043910.