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

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

• 1 Определение
• 2 Примеры
• 3 Свойства
• 4 Ссылки

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

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

Тогда $y\; \{\backslash \; displaystyle\; y\}$covers$x\; \{\backslash \; displaystyle\; x\}$, записывается $x\; ⋖\; y\; \{\backslash \; displaystyle\; x\; \backslash \; lessdot\; y\}$, если и нет элемента $z\; \{\backslash \; displaystyle\; z\}$такого что . Эквивалентно, $y\; \{\backslash \; displaystyle\; y\}$охватывает $x\; \{\backslash \; displaystyle\; x\}$, если interval $[x,\; y]\; \{\backslash \; displaystyle\; [x,\; y]\}$- это двухэлементный набор $\{x,\; y\}\; \{\backslash \; displaystyle\; \backslash \; \{x,\; y\; \backslash \}\}$.

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

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

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

• Knuth, Donald E. (2006), The Art of Computer Programming, Volume 4, Fascicle 4, Addison-Wesley, ISBN 0-321-33570-8.
• Stanley, Ричард П. (1997), Enumerative Combinatorics, 1(2-е изд.), Cambridge University Press, ISBN 0-521-55309- 1.
• Брайан А. Дэйви; Хилари Энн Пристли (2002), Введение в решетки и порядок (2-е изд.), Cambridge University Press, ISBN 0-521-78451-4, LCCN 2001043910.