Порядок включения

Частичный порядок, возникающий как отношение включения подмножества в некоторую совокупность объектов.

В математической области теории порядка порядок включения — это частичный порядок , который возникает как отношение подмножества -включения на некоторой коллекции объектов. Проще говоря, каждый посет P = ( X ,≤) является ( изоморфным ) порядком включения (так же, как каждая группа изоморфна группе перестановок — см. теорему Кэли ). Чтобы увидеть это, сопоставьте каждому элементу x из X множество

${\displaystyle X_{\leq (x)}=\{y\in X\mid y\leq x\};}$

тогда транзитивность ≤ гарантирует, что для всех a и b в X мы имеем

${\displaystyle X_{\leq (a)}\subseteq X_{\leq (b)}{\text{ precisely when }}a\leq b.}$

Могут существовать множества мощности , меньшей, чем такие , что P изоморфен порядку включения на S. Размер наименьшего возможного S называется 2- мерностью P. ${\displaystyle S}$ ${\displaystyle |X|}$

Несколько важных классов частично упорядоченных множеств возникают как порядки включения для некоторых естественных наборов, таких как булева решетка Q ⁿ , которая является набором всех 2 ⁿ подмножеств набора из n -элементов, порядки интервального включения , которые являются в точности порядками размерности порядка не более двух, и порядки размерности n , которые являются порядками включения на наборах из n -ящиков, закрепленных в начале координат . Другие порядки включения, которые интересны сами по себе, включают порядки окружностей , которые возникают из дисков на плоскости, и порядки углов .

Смотрите также

• Теорема Биркгофа о представлении
• Граф пересечения
• Интервальный порядок

Ссылки

• Фишберн, ПК; Троттер, У.Т. (1998). «Геометрические приказы о сдерживании: обзор». Приказ . 15 (2): 167–182. doi :10.1023/A:1006110326269. S2CID  14411154.
• Санторо, Н., Сидней, Дж. Б., Сидней, С. Дж. и Уррутия, Дж. (1989). «Геометрическое включение и частичные порядки». Журнал SIAM по дискретной математике . 2 (2): 245–254. CiteSeerX  10.1.1.65.1927 . doi :10.1137/0402021.{{cite journal}}: CS1 maint: несколько имен: список авторов ( ссылка )