Категория отношений

В математике категория Rel имеет класс множеств как объектов и бинарных отношений как морфизмов .

Морфизм (или стрелка) R : A → B в этой категории представляет собой отношение между множествами A и B , поэтому R ⊆ A × B.

Композиция двух отношений R : A → B и S : B → C задается формулой

( a , c ) ∈ S o R ⇔ для некоторых b ∈ B , ( a , b ) ∈ R и ( b , c ) ∈ S . ^[1]

Rel также называют «категорией соответствий множеств». ^[2]

Характеристики

Категория Rel имеет категорию множеств Set как (широкую) подкатегорию , где стрелка f : X → Y в Set соответствует отношению F ⊆ X × Y , определяемому соотношением ( x , y ) ∈ F ⇔ f ( x ) = y . ^{[примечание 1]}^[3]

Морфизм в Rel является отношением, а соответствующий морфизм в противоположной категории к Rel имеет обратные стрелки, поэтому это обратное отношение . Таким образом, Rel содержит свою противоположность и является самодвойственным . ^[4]

Инволюция , представленная путем взятия обратного отношения, предоставляет кинжал , чтобы сделать Rel категорией кинжала .

Категория имеет два функтора в себя, заданные функтором hom : бинарное отношение R ⊆ A × B и его транспонированное отношение R ^T ⊆ B × A могут быть составлены либо как RR ^{T ,} либо как R ^T R . Первая композиция приводит к однородному отношению на A , а вторая — на B . Поскольку образы этих функторов hom находятся в самом Rel , в этом случае hom является внутренним функтором hom . Со своим внутренним функтором hom Rel является замкнутой категорией , и, кроме того, кинжальной компактной категорией .

Категория Rel может быть получена из категории Set как категория Клейсли для монады, функтор которой соответствует мощности set , интерпретируемой как ковариантный функтор.

Возможно, на первый взгляд немного удивительным является тот факт, что произведение в Rel задается дизъюнктным объединением ^[4]^{: 181} (а не декартовым произведением , как в Set ), то же самое относится и к копроизведению .

Rel является моноидально замкнутой , если определить как моноидальное произведение A ⊗ B , так и внутренний hom A ⇒ B декартовым произведением множеств. Это также моноидальная категория , если определить моноидальное произведение дизъюнктным объединением множеств. ^[5]

Категория Rel была прототипом алгебраической структуры, названной аллегорией Питером Дж. Фрейдом и Андре Сцедровым в 1990 году. ^[6] Начиная с регулярной категории и функтора F : A → B , они отмечают свойства индуцированного функтора Rel( A,B ) → Rel( FA, FB ). Например, он сохраняет композицию, преобразование и пересечение. Такие свойства затем используются для предоставления аксиом для аллегории.

Отношения как объекты

Дэвид Райдхерд и Род Берстолл считают, что Rel имеет объекты, которые являются однородными отношениями. Например, A — это множество, а R ⊆ A × A — бинарное отношение на A. Морфизмы этой категории — это функции между множествами, которые сохраняют отношение: скажем, S ⊆ B × B — это второе отношение, а f : A → B — это функция, такая, что f — это морфизм. ^[7] $xRy\подразумевает f(x)Sf(y),$

Эту же идею развивают Адамек, Херрлих и Штрекер, где они обозначают объекты ( A, R ) и ( B, S ), множество и отношение. ^[8]

Примечания

^ Эту категорию Райдхерд и Берстолл называют Set _{Rel .}

Ссылки

^ Mac Lane, S. (1988). Категории для работающего математика (1-е изд.). Springer. стр. 26. ISBN 0-387-90035-7.
^ Парейгис, Бодо (1970). Категории и функторы . Чистая и прикладная математика. Т. 39. Academic Press . С. 6. ISBN 978-0-12-545150-5.
^ Бергман, Джордж (1998). "§7.2 RelSet". Приглашение в общую алгебру и универсальные конструкции. Генри Хельсон. ISBN 0-9655211-4-1.
^ ab Barr, Michael ; Wells, Charles (1990). Теория категорий для вычислительной науки (PDF) . Prentice Hall. стр. 181. ISBN 978-0131204867.
^ Фонг, Брендан; Дэвид И. Спивак (2019). «Поставка наворотов в симметричных моноидальных категориях». arXiv : 1908.02633 [math.CT].
^ Фрейд, Питер Дж .; Щедров, Андре (1990). Категории, Аллегории . Северная Голландия. стр. 79, 196. ISBN. 0-444-70368-3.
^ Райдхерд, Дэвид; Берстолл, Род (1988). Вычислительная теория категорий . Prentice-Hall. стр. 41. ISBN 978-0131627369.
^ Адамек, Юрий; Херрлих, Хорст; Штрекер, Джордж Э. (2004) [1990]. "§3.3, пример 2(d)". Абстрактные и конкретные категории (PDF) . Исследовательская группа KatMAT, Бременский университет . стр. 22. Архивировано из оригинала (PDF) 2022-08-11.

Борсо, Фрэнсис (1994). Категории и структуры. Справочник по категориальной алгебре. Том 2. Cambridge University Press . С. 115. ISBN 978-0-521-44179-7.