Отношение предпорядка¶

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

¶Определение и формальные свойства

Пусть \(P\) — произвольное множество. Бинарное отношение \(\precsim\) на \(P\) называется отношением предпорядка, если для любых \(a, b, c \in P\) выполняются два условия:

1. Рефлексивность: \(a \precsim a\) (каждый элемент сравним сам с собой).
2. Транзитивность: если \(a \precsim b\) и \(b \precsim c\), то \(a \precsim c\).

Если дополнительно выполняется свойство антисимметричности (если \(a \precsim b\) и \(b \precsim a\), то \(a = b\)), то отношение является частичным порядком. Если же отношение предпорядка является ещё и связным (для любых \(a, b\) выполняется \(a \precsim b\) или \(b \precsim a\)), то оно называется полным предпорядком (или квазипорядком).

¶Связь с отношением эквивалентности

Из отношения предпорядка \(\precsim\) можно естественным образом получить отношение эквивалентности \(\sim\), определив \(a \sim b\) тогда и только тогда, когда \(a \precsim b\) и \(b \precsim a\). Классы эквивалентности по этому отношению образуют фактормножество \(P/\!\sim\), на котором отношение предпорядка индуцирует частичный порядок: \([a] \leq [b]\) тогда и только тогда, когда \(a \precsim b\). Таким образом, любой предпорядок сводится к частичному порядку на классах эквивалентности.

¶Примеры

¶1. Числовые неравенства

На множестве действительных чисел \(\mathbb{R}\) отношение «меньше или равно» (\(\leq\)) является предпорядком (и даже частичным порядком). Отношение «строго меньше» (\(<\)) не является предпорядком, так как не рефлексивно.

¶2. Отношение делимости

На множестве натуральных чисел \(\mathbb{N}\) отношение «\(a\) делит \(b\)» (обозначается \(a \mid b\)) является предпорядком: оно рефлексивно (каждое число делит само себя) и транзитивно (если \(a \mid b\) и \(b \mid c\), то \(a \mid c\)). Однако оно не антисимметрично, так как если \(a \mid b\) и \(b \mid a\), то \(a = b\) — здесь антисимметричность выполняется, поэтому это частичный порядок. В более общем случае, например, на множестве целых чисел с учётом знака, отношение делимости может не быть антисимметричным.

¶3. Отношение включения множеств

На булеане \(\mathcal{P}(X)\) (множестве всех подмножеств некоторого множества \(X\)) отношение включения \(\subseteq\) является предпорядком и частичным порядком.

¶4. Отношение достижимости в графе

В ориентированном графе отношение «существует путь из вершины \(a\) в вершину \(b\)» является предпорядком на множестве вершин. Оно рефлексивно (путь длины 0) и транзитивно (композиция путей). Если граф содержит циклы, то отношение может не быть антисимметричным.

¶5. Предпорядок, порождённый функцией

Пусть \(f: X \to Y\) — произвольная функция. Определим на \(X\) отношение: \(x \precsim y\) тогда и только тогда, когда \(f(x) \leq f(y)\) (где \(\leq\) — некоторый порядок на \(Y\)). Это отношение является предпорядком. Если \(f\) — не инъективна, то предпорядок не будет антисимметричным, так как разные элементы могут иметь одинаковое значение \(f\).

¶6. Предпорядок в теории предпочтений

В экономике и теории принятия решений отношение предпочтения \(\succsim\) на множестве альтернатив часто моделируется как полный предпорядок: для любых двух альтернатив \(a\) и \(b\) либо \(a \succsim b\) (a не хуже b), либо \(b \succsim a\). Рефлексивность и транзитивность считаются стандартными аксиомами рационального выбора.

¶Классификация и связанные понятия

¶Виды предпорядков

• Частичный порядок — предпорядок, удовлетворяющий антисимметричности.
• Полный предпорядок (квазипорядок) — предпорядок, в котором любые два элемента сравнимы (связность).
• Предпорядок с дополнительными свойствами (например, направленный предпорядок, где для любой пары элементов существует верхняя грань).

¶Связь с другими структурами

• Категория предпорядков — малая категория, в которой объекты — элементы множества, а морфизмы — пары \((a,b)\) такие, что \(a \precsim b\). Категория предпорядка является примером тонкой категории (между любыми двумя объектами не более одного морфизма).
• Предпорядок и топология — предпорядок порождает топологию Александрова, в которой открытыми множествами являются верхние множества (множества, замкнутые относительно предпорядка вверх).
• Предпорядок и решётки — если предпорядок является частичным порядком и для любых двух элементов существуют точная верхняя и точная нижняя грани, то множество образует решётку.

¶Применение

¶Теоретическая информатика

• Семантика языков программирования — предпорядки используются для моделирования аппроксимации и частичной информации (например, в области domain theory, где элементы — частично определённые вычислительные объекты, а предпорядок — отношение «является аппроксимацией»).
• Типы и подтипы — в системах типов отношение подтипирования часто является предпорядком (рефлексивно и транзитивно, но не обязательно антисимметрично, так как два разных типа могут быть взаимными подтипами).
• Анализ программ — в абстрактной интерпретации предпорядки на абстрактных доменах позволяют формализовать отношение «более точное приближение».

¶Математическая экономика

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

¶Теория категорий

• Категории как обобщение предпорядков — предпорядок можно рассматривать как категорию, в которой между любыми двумя объектами существует не более одного морфизма. Многие конструкции в теории категорий (пределы, копределы) имеют аналоги в теории предпорядков (точные верхние и нижние грани).

¶Математическая логика

• Отношение выводимости — в формальных системах отношение «формула \(A\) выводима из формулы \(B\)» (или наоборот) часто является предпорядком на множестве формул.
• Семантика Крипке — в модальной логике предпорядки используются как отношения достижимости между возможными мирами.

¶Интересные факты

• Любое отношение предпорядка можно «превратить» в частичный порядок, отождествив эквивалентные элементы (процедура факторизации по отношению эквивалентности, порождённому взаимной сравнимостью).
• В теории категорий предпорядок — это категория, в которой каждый hom-множество содержит не более одного элемента. Такие категории называются тонкими.
• Понятие предпорядка тесно связано с понятием предбазы топологии: совокупность верхних множеств предпорядка образует предбазу топологии Александрова.
• В математической экономике аксиома транзитивности предпочтений иногда подвергается критике, поскольку в реальном поведении людей могут наблюдаться нетранзитивные предпочтения (например, эффект циклического выбора).

¶Источники

• Бурбаки Н. «Теория множеств». — М.: Мир, 1965.
• Голдблатт Р. «Топосы. Категорный анализ логики». — М.: Мир, 1983.
• Davey B. A., Priestley H. A. «Introduction to Lattices and Order». — Cambridge University Press, 2002.
• Kreps D. M. «Notes on the Theory of Choice». — Westview Press, 1988.
• Виноградов И. М. (ред.) «Математическая энциклопедия». — М.: Советская энциклопедия, 1977–1985.