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

Математическое отношение внутри порядков

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

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

Определение

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

Пусть и будут элементами . ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle X}$

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

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

Примеры

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

Характеристики

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

Ссылки

• Кнут, Дональд Э. (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.