Лекция 5. Частичный порядок, диаграмма Хассе, границы

Отношение, которое рефлексивно, антисимметрично и транзитивно, называют частичным порядком: он обобщает привычное «меньше или равно» на объекты, которые не всегда можно сравнить, например на множества по включению или на числа по делимости. На прошлой лекции мы разобрали эти свойства по отдельности (лекция 4), теперь собираем их в одно определение и изучаем, как устроены такие множества: как их рисовать, где у них «дно» и «потолок» и что такое точная граница подмножества.

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

1.1. Определение

Определение 1. Бинарное отношение $\le$ на множестве $A$ называется частичным порядком, если оно

• рефлексивно: $\forall a \in A\ \ a \le a$;
• антисимметрично: $\forall a, b \in A\ \ (a \le b \wedge b \le a) \to a = b$;
• транзитивно: $\forall a, b, c \in A\ \ (a \le b \wedge b \le c) \to a \le c$.

Определение 2. Пара $(A, \le)$, где $\le$ — частичный порядок на $A$, называется ЧУМ — частично упорядоченным множеством (англ. partially ordered set, poset).

1.2. Примеры

Слово «частичный» значит, что некоторые пары можно не сравнивать. В $(\mathbb{N}, \mid)$ числа $2$ и $3$ несравнимы: ни $2 \mid 3$, ни $3 \mid 2$. В $(\mathcal{P}(\{1, 2, 3\}), \subseteq)$ несравнимы $\{1\}$ и $\{2\}$.

2. Строгий порядок

Определение 3. Бинарное отношение $<$ на $A$ называется строгим порядком, если оно

• иррефлексивно: $\forall a \in A\ \ \neg(a < a)$;
• асимметрично: $\forall a, b \in A\ \ a < b \to \neg(b < a)$;
• транзитивно: $\forall a, b, c \in A\ \ (a < b \wedge b < c) \to a < c$.

Пример. Обычное $<$ на числах: $1 < 1$ ложно, а из $1 < 2$ и $2 < 3$ следует $1 < 3$. Другой пример — строгое включение $\subset$ на $\mathcal{P}(\{1, 2, 3\})$: $\{1\} \subset \{1, 2\} \subset \{1, 2, 3\}$.

Теорема 1. Если задан частичный порядок $\le$, то отношение $a < b \iff a \le b \wedge a \ne b$ является строгим порядком (индуцированный строгий порядок). Верно и обратное: по строгому порядку $<$ отношение $a \le b \iff a < b \vee a = b$ является частичным порядком.

Доказательство первой части. Иррефлексивность: $a \ne a$ ложно, значит $a < a$ ложно. Асимметричность: пусть $a < b$ и $b < a$; тогда $a \le b$ и $b \le a$, по антисимметрии $a = b$, а это противоречит $a \ne b$. Транзитивность: пусть $a < b$ и $b < c$; тогда $a \le c$ по транзитивности $\le$. Если бы $a = c$, то $a \le b$ и $b \le c = a$ дали бы $a = b$, противоречие. Значит $a \ne c$ и $a < c$. Обратная часть проверяется так же. $\blacksquare$

Поэтому дальше «порядок» и «строгий порядок» — две записи одного и того же: $\le$ и $<$ получаются друг из друга.

3. Линейный порядок, плотность, цепи

3.1. Линейный порядок

Определение 4. Частичный порядок называется линейным (полным, total), если он сильно связен, то есть любые два элемента сравнимы:

$\forall a, b \in A\ \ (a \le b) \vee (b \le a).$

Числа с $\le$ — линейный порядок; делимость и включение — нет.

3.2. Плотность

Определение 5. Линейный порядок плотен, если между любыми двумя различными элементами есть третий:

$\forall a, b \in A\ \ (a < b \to \exists c\ \ a < c < b).$

Условие нужно писать именно со строгим $<$: с нестрогим $\le$ в качестве $c$ подошёл бы сам $a$, и любой порядок оказался бы плотным.

Пример. $(\mathbb{Q}, <)$ плотен: между $a$ и $b$ лежит $\dfrac{a + b}{2}$. $(\mathbb{Z}, <)$ не плотен: между $1$ и $2$ нет целого числа.

3.3. Цепи и антицепи

Определение 6. Подмножество ЧУМ называется цепью, если любые два его элемента сравнимы, и антицепью, если любые два его различных элемента несравнимы.

Пример. В $(\mathbb{N}, \mid)$ множество $\{1, 2, 4, 12\}$ — цепь: $1 \mid 2 \mid 4 \mid 12$. Множество $\{4, 6\}$ — антицепь: $4 \nmid 6$ и $6 \nmid 4$.

3.4. Лексикографический порядок

Определение 7. Пусть на $A$ и на $B$ заданы строгие порядки. Лексикографический порядок на $A \times B$:

$(a_1, a_2) < (b_1, b_2) \iff a_1 < b_1 \ \vee\ (a_1 = b_1 \wedge a_2 < b_2).$

Так упорядочены слова в словаре: сначала сравниваем первые буквы, и только если они равны, переходим ко вторым.

Пример. $(2, 9) < (3, 1)$, потому что $2 < 3$ и вторые компоненты не смотрим. $(2, 3) < (2, 7)$, потому что первые компоненты равны, а $3 < 7$.

Теорема 2. Лексикографический порядок линеен тогда и только тогда, когда линейны оба исходных порядка (на непустых $A$ и $B$).

Доказательство. Пусть оба линейны, а $(a_1, a_2) \ne (b_1, b_2)$. Если $a_1 \ne b_1$, то один из них меньше в $A$, и это решает сравнение пар. Если $a_1 = b_1$, то $a_2 \ne b_2$, и они сравнимы в $B$. Обратно: если в $A$ есть несравнимые $x, y$, то при любом $c \in B$ пары $(x, c)$ и $(y, c)$ несравнимы; аналогично для $B$ и пар $(c, x)$, $(c, y)$. $\blacksquare$

3.5. Топологическая сортировка

Определение 8. Линейный порядок $\preceq$ на ЧУМ $(A, \le)$ называется его топологической сортировкой, если $a \le b$ влечёт $a \preceq b$. Иными словами, это способ выстроить все элементы в ряд так, чтобы ничего не стояло раньше того, что меньше него.

Пример. Для делимости на $\{1, 2, 3, 4, 6, 12\}$ подходят порядки $1, 2, 3, 4, 6, 12$ и $1, 3, 2, 6, 4, 12$: в обоих число стоит после всех своих делителей. Сортировок бывает много, она единственна только у линейного порядка.

4. Диаграмма Хассе

4.1. Покрытие

Рисовать все пары $a \le b$ неудобно: слишком много лишних стрелок. Поэтому из отношения оставляют только «скелет» — отношение покрытия.

Определение 9. Элемент $a$ покрывает $b$, если $b < a$ и не существует $c$ с $b < c < a$ (отношение покрытия).

4.2. Построение

Диаграмма Хассе — скелет частичного порядка. Строится так:

Стрелки на рёбрах не нужны: направление «вверх» уже задано расположением.

4.3. Пример: делители числа 12

$D_{12} = \{1, 2, 3, 4, 6, 12\}$ с отношением делимости. Покрытий семь: $1 - 2$, $1 - 3$, $2 - 4$, $2 - 6$, $3 - 6$, $4 - 12$, $6 - 12$. Ребра $1 - 4$ нет, потому что между ними стоит $2$.

      12
     /  \
    4    6
    |  / |
    2    3
     \  /
      1

5. Экстремальные элементы

Определение 10. Элемент $m$ минимален, если $\nexists a\colon a < m$. Элемент $m$ максимален, если $\nexists a\colon m < a$.

Определение 11. Элемент $m$ наименьший, если $\forall a \in A\ \ m \le a$. Элемент $m$ наибольший, если $\forall a \in A\ \ a \le m$.

На диаграмме Хассе минимальные элементы — те, под которыми ничего нет, максимальные — те, над которыми ничего нет. Наименьший — единственная «нижняя точка», с которой связаны все остальные.

Утверждение 1. Наименьший элемент, если он существует, единственен и минимален. То же верно для наибольшего и максимального.

Доказательство. Единственность: если $m$ и $m'$ оба наименьшие, то $m \le m'$ и $m' \le m$, откуда $m = m'$ по антисимметрии. Минимальность: если бы нашлось $a < m$, то $a \le m$ и $a \ne m$; но $m$ наименьший, поэтому $m \le a$, и по антисимметрии $a = m$ — противоречие. $\blacksquare$

6. Верхние и нижние грани

Определение 12. Пусть $S \subseteq A$. Элемент $u \in A$ — верхняя грань $S$, если $s \le u$ для всех $s \in S$. Элемент $l \in A$ — нижняя грань $S$, если $l \le s$ для всех $s \in S$.

Грань берётся из всего $A$ и не обязана лежать в $S$.

Определение 13. Супремум $\sup S$ — наименьшая верхняя грань $S$. Инфимум $\inf S$ — наибольшая нижняя грань $S$.

Раз наименьший и наибольший элементы единственны (утверждение 1), то $\sup S$ и $\inf S$, если существуют, тоже единственны.

Пример в $(D_{12}, \mid)$:

Пример в $(\mathbb{R}, \le)$: для интервала $S = (0, 1)$ верхние грани — все числа из $[1, +\infty)$, $\sup S = 1$, $\inf S = 0$. Ни $1$, ни $0$ не принадлежат $S$, поэтому у $S$ нет ни наибольшего, ни наименьшего элемента, а точные грани есть.

Частые ошибки

• Путать минимальный и наименьший элемент (раздел 5): минимальных может быть много, наименьший один и не всегда есть.
• Считать, что любые два элемента ЧУМ сравнимы. Это свойство линейного порядка.
• Писать плотность через $\le$ (раздел 3.2): определение теряет смысл, нужно строгое $<$.
• Искать $\sup S$ только внутри $S$: верхняя грань берётся из всего $A$ и может в $S$ не лежать.
• Считать, что $\sup$ и $\inf$ есть всегда. В $(\{1, 2, 3, 4, 6\}, \mid)$ у множества $\{4, 6\}$ нет верхних граней, значит нет и $\sup$.
• Рисовать на диаграмме Хассе рёбра, следующие из транзитивности, и петли.
• Брать делимость на $\mathbb{Z}$ вместо $\mathbb{N}$: пропадает антисимметричность.

Мини-тренажёр

1. Отношение $R = \{(1, 1), (2, 2), (3, 3), (1, 2), (2, 3)\}$ на $\{1, 2, 3\}$ — частичный порядок? Если нет, что добавить?
2. Выпишите все пары строгого порядка, индуцированного делимостью на $\{1, 2, 3, 6\}$.
3. Сравните лексикографически $(2, 9)$ и $(3, 1)$, затем $(2, 3)$ и $(2, 7)$.
4. Плотны ли $(\mathbb{Q}, <)$ и $(\mathbb{Z}, <)$?
5. Постройте диаграмму Хассе для $(\mathcal{P}(\{1, 2, 3\}), \subseteq)$. Сколько в ней вершин и рёбер? Найдите наименьший и наибольший элементы, $\sup\{\{1\}, \{2\}\}$ и $\inf\{\{1, 2\}, \{2, 3\}\}$.
6. В $(\{2, 3, 4, 6, 12\}, \mid)$ найдите минимальные и максимальные элементы, наименьший и наибольший, $\sup\{2, 3\}$ и $\inf\{4, 6\}$. Существует ли $\inf\{2, 3\}$?
7. Укажите ещё одну топологическую сортировку делимости на $\{1, 2, 3, 4, 6, 12\}$ и найдите цепь из трёх элементов и антицепь из двух.

Шпаргалка