Передпорядок

Передпорядок (відношення передпорядку) — бінарне відношення в теорії порядку, що є транзитивним та рефлексивним. Зазвичай позначається ${\displaystyle \leqslant ,}$ тоді визначення передпорядку на множині ${\displaystyle S}$ приймає вигляд:

діаграма Гассе передпорядку x R y визначеного як x/4 ≤ y4. Через наявність циклів, R не є антисиметричним, тому відношення не є частковим впорядком.

${\displaystyle \forall a,b,c\in S:\quad (a\leqslant b\land b\leqslant c)\Rightarrow (a\leqslant c)\quad }$ (транзитивність)

${\displaystyle \forall a\in S:\quad \qquad a\leqslant a\quad }$ (рефлексивність)

Якщо замінити у визначенні рефлексивність на антирефлексивність, то отримаємо строгий передпорядок, який позначеється ${\displaystyle \,<\,}$. Визначення:

${\displaystyle \forall a,b,c\in S:\quad (a<b\land b<c)\Rightarrow (a<c)\quad }$ (транзитивність)

${\displaystyle \forall a\in S:\quad \qquad \lnot (a<a)\quad }$ (антирефлексивність)

Пов'язані визначення

• Відношення еквівалентності — симетричний передпорядок.
• Частковий порядок — антисиметричний передпорядок.
• Повний передпорядок — передпорядок, що є повним.

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

В теорії категорій з поняттям передпорядку пов'язують зазвичай дві категорії: категорію передпорядків й категорії, які називають передпорядками.

Передпорядки

Категорія ${\displaystyle {\mathcal {P}}}$ називається передпорядком, якщо для будь-яких двох об'єктів ${\displaystyle a,b\in Ob{\mathcal {P}}}$ існує не більше одного морфізмe ${\displaystyle f\colon a\to b.}$ Якщо ${\displaystyle {\mathcal {P}}}$ — мала категорія, то на множині її об'єктів можна задати відношення передпорядка за наступним правилом:

${\displaystyle a\leqslant b\iff \exists f\colon a\to b}$

З аксіом категорії слідує, що таке відношення буде рефлексивним і транзитивним. Передпорядок — це абстрактна категорія, тобто його у загальному випадку не можна представити як категорію деяких множин із заданою структурою і відображеннями, що зберігають цю структуру.

• Передпорядок — це скелетна категорія.
• Якщо мала категорія ${\displaystyle {\mathcal {C}}}$ повна в малому, то вона є предпорядком, причому кожна менша множина його елементів має найбільшу нижню грань.
• Добуток набору (множини, класу і т. п.) об'єктів предпорядку — це найбільша нижня грань для цього набору. Кодобуток набору об'єктів — це його найменша верхня грань.
• Початковий об'єкт ${\displaystyle 0}$ у передпорядку ${\displaystyle {\mathcal {P}}}$, якщо він існує, — це його найменший об'єкт, так що ${\displaystyle \forall a\in {\mathcal {P}}\colon 0\leqslant a.}$ Аналогиічно, термінальний об'єкт передпорядку — це найбільший об'єкт у ньому.

Категорія передпорядків

Категорія передпорядків позначається зазвичай ${\displaystyle \mathbf {Preord} .}$ Об'єктами категорії передпорядків є передпорядки (в сенсі категорій), зокрема, множини, на яких задані відношення передпорядку. Морфізми в цій категорії — відображення множин, зберігають відношення предпорядку, тобто монотонні відображення. Розглянемо в ${\displaystyle \mathbf {Preord} }$ підкатегорію малих передпорядків ${\displaystyle \mathbf {Preord} _{S}.}$ Це конкретна категорія, наділена очевидним унівалентним забутливим функтором

${\displaystyle U\colon \mathbf {Preord} _{S}\to \mathbf {Set} ,}$

який зіставляє кожному малому передпорядку множину його об'єктів, а кожному морфізму — монотонне відображення відповідних множин. Цей функтор створює межі в ${\displaystyle \mathbf {Preord} }$. Таким чином, аналогічно ${\displaystyle \mathbf {Set} ,}$ початковим об'єктом в ${\displaystyle \mathbf {Preord} }$ є порожня множина, термінальним об'єктом — множина з одного елементу, добутком об'єктів — прямий добуток відповідних множин з покомпонентним порівнянням, тощо.

Джерела

• Куратовский К., Мостовский А. Теория множеств = Set Theory (Teoria mnogości). — М. : Мир, 1970. — 416 с.(рос.)

• Хаусдорф Ф. Теория множеств. — Москва ; Ленинград : , 1937. — 304 с. — .(рос.)

• Р. Голдблатт Топоси. Категорний аналіз логіки, — Мир, 1983. — 487 с.
• С. Маклейн Категорії для працюючого математика, — ФИЗМАТЛИТ, 2004. — 352 с — .