🔀 Дискретка

Частичный порядок

Q: Чем частичный порядок отличается от линейного?

Линейный требует, чтобы для любой пары выполнялось $a \preceq b$ или $b \preceq a$ — всех можно выстроить в один ряд. Частичный допускает несравнимые элементы: включение не сравнивает $\{1,2\}$ и $\{3\}$, делимость — числа $6$ и $10$. Из-за этого максимальных элементов бывает несколько, а наибольшего нет. Полезный факт: любой частичный порядок достраивается до линейного без противоречий — на этом держится индукция по частичным порядкам.

англ. Partial order

Рефлексивное, антисимметричное и транзитивное отношение — «не хуже чем», без гарантии, что любые два элемента сравнимы между собой.

Частичный порядок — отношение, задающее «направление сравнения», но разрешающее несравнимые пары. Аксиомы: рефлексивность ( $a ⪯ a$ ), антисимметричность ( $a ⪯ b$ и $b ⪯ a$ влекут $a = b$ ) и транзитивность. Образцы: обычное $\leq$ на числах, включение $\subseteq$ на множествах, делимость $m ∣ n$ на целых. Сравнимы не все пары: подмножества ${1, 2}$ и ${3}$ не лежат одно в другом, поэтому порядок и называют частичным. Определения отношений и их классификация — в уроке отношения.

Рисуют порядок диаграммой Хассе: выше — большие элементы, ребро проводится, когда один элемент покрывает другой. Сразу видны минимальные и максимальные элементы — их может быть несколько, а наибольший и наименьший иногда не существуют вовсе. Цепь — набор попарно сравнимых элементов, антицепь — попарно несравнимых; баланс цепей и антицепей (теорема Дилуорса) — рабочая техника оценок в сортировках и планировании. Если же любые два элемента сравнимы, порядок называют линейным, и вся картина сворачивается к привычному «меньше — больше».

a ⪯ a; a ⪯ b, b ⪯ a \Rightarrow a = b; a ⪯ b, b ⪯ c \Rightarrow a ⪯ c

рефлексивность, антисимметричность, транзитивность: по сравнению с эквивалентностью симметричность заменена на антисимметричность

Частые вопросы

Чем частичный порядок отличается от линейного?

Линейный требует, чтобы для любой пары выполнялось $a ⪯ b$ или $b ⪯ a$ — всех можно выстроить в один ряд. Частичный допускает несравнимые элементы: включение не сравнивает ${1, 2}$ и ${3}$ , делимость — числа $6$ и $10$ . Из-за этого максимальных элементов бывает несколько, а наибольшего нет. Полезный факт: любой частичный порядок достраивается до линейного без противоречий — на этом держится индукция по частичным порядкам.

Что такое минимальный элемент и чем он отличается от наименьшего?

Минимальный — тот, меньше которого нет: под ним пусто, но с несравнимыми соседями он может «не знаться», поэтому минимумов бывает много. Наименьший — элемент, не превосходящий любого другого; он единственный, если существует, и всегда минимален. Обратное неверно: в порядке делимости на множестве ${2, 3, 5, 6}$ минимальны $2, 3, 5$ , а наименьшего нет. В диаграмме Хассе минимальные элементы — нижние точки без входящих рёбер.