Предпорядок

Предпоря́док (квазипоря́док) — бинарное отношение на множестве, обладающее свойствами рефлексивности и транзитивности. Обычно это отношение обозначается [math]\displaystyle{ \preccurlyeq }[/math], тогда аксиомы предпорядка на множестве [math]\displaystyle{ M }[/math] принимают вид:

[math]\displaystyle{ \forall a\in M\colon a \preccurlyeq a }[/math],

[math]\displaystyle{ \forall a,b,c\in M\colon (a \preccurlyeq b \land b \preccurlyeq c)\Rightarrow(a \preccurlyeq c) }[/math].

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

[math]\displaystyle{ \forall a,b\in X\colon (a \preccurlyeq b)\lor(b \preccurlyeq a) }[/math].

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

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

[math]\displaystyle{ a \preccurlyeq b \iff \exists f\colon a\to b }[/math].

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

Если малая категория [math]\displaystyle{ \mathcal C }[/math] полна в малом, то она является предпорядком, причём каждое малое множество его элементов имеет наибольшую нижнюю грань. Произведение набора (множества, класса) объектов предпорядка — это наибольшая нижняя грань для этого набора. Копроизведение набора объектов — это его наименьшая верхняя грань. Начальный объект [math]\displaystyle{ 0 }[/math] в предпорядке [math]\displaystyle{ \mathcal P }[/math], если он существует, — это его наименьший объект, так что [math]\displaystyle{ \forall a\in\mathcal P\colon 0 \preccurlyeq a }[/math]. Аналогично, терминальный объект предпорядка — это наибольший объект в нём.

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

[math]\displaystyle{ U\colon \mathbf{Preord}_S \to \mathbf{Set} }[/math],

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

Литература

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