Предпорядок

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

Предпоря́док — бинарное отношение на множестве, обладающее свойствами рефлексивности и транзитивности. Обычно это отношение обозначается \leqslant, тогда аксиомы предпорядка на множестве M принимают вид:

\forall a\in M\colon a\leqslant a,
\forall a,b,c\in M\colon (a\leqslant b \and b\leqslant c)\Rightarrow(a\leqslant c).

Теория категорий[править | править вики-текст]

В теории категорий с понятием предпорядка связывают обычно две категории: категорию предпорядков и категории, называемые предпорядками.

Предпорядки[править | править вики-текст]

Категория \mathcal P называется предпорядком, если для любых двух объектов a,b\in Ob \mathcal P существует не более одного морфизма f\colon a\to b. Если \mathcal P — малая категория, то на множестве её объектов можно задать отношение предпорядка по следующему правилу:

a \leqslant b \iff \exists f\colon a\to b

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

Категория предпорядков[править | править вики-текст]

Категория предпорядков обозначается обычно \mathbf{Preord}. Объектами категории предпорядков являются предпорядки (в смысле категорий), в частности, множества, на которых задано отношение предпорядка. Морфизмы в этой категории — отображения множеств, сохраняющие отношение предпорядка, то есть монотонные отображения. Рассмотрим в \mathbf{Preord} подкатегорию малых предпорядков \mathbf{Preord}_S. Это конкретная категория, наделённая очевидным унивалентным забывающим функтором

U\colon \mathbf{Preord}_S \to \mathbf{Set},

сопоставляющим каждому малому предпорядку множество его объектов, а каждому морфизму — монотонное отображение соответствующих множеств. Этот функтор создаёт пределы в \mathbf{Preord}. Таким образом, аналогично \mathbf{Set}, начальным объектом в \mathbf{Preord} является пустое множество, терминальным объектом — множество из одного элемента, произведением объектов — прямое произведение соответствующих множеств с покомпонентным сравнением.

Связанные определения[править | править вики-текст]

Линейный порядок — это предпорядок на множестве, для которого любые два элемента множества сравнимы:

\forall a,b\in X\colon (a\leqslant b)\or(b\leqslant a).

Литература[править | править вики-текст]

  • Р. Голдблатт Топосы. Категорный анализ логики, — М.: Мир, 1983. — 487 с.
  • Маклейн С. Глава 1. Категории, функторы и естественные преобразования // Категории для работающего математика = Categories for the working mathematician / Пер. с англ. под ред. В. А. Артамонова. — М.: Физматлит, 2004. — С. 17—42. — 352 с. — ISBN 5-9221-0400-4