Categoria de relações

Na matemática, a categoria Rel tem a classe de conjuntos como objetos e relação binárias como morfismos.

Um morfismo (ou flecha) R : A → B nesta categoria é uma relação entre os conjuntos A e B, então R ⊆ A × B.

A composição de duas relações R: A → B e S: B → C é dada por

(a, c) ∈ S o R ⇔ para algum b ∈ B, (a, b) ∈ R e (b, c) ∈ S.^[1]

Rel também já foi chamado de "categoria de correspondências de conjuntos".^[2]

Propriedades

A categoria Rel possui a categoria de conjuntos Set como uma (ampla) subcategoria, onde a flecha f : X → Y em Set corresponde à relação F ⊆ X × Y definida por (x, y) ∈ F ⇔ f(x) = y.^{[nota 1]}^[3]

Um morfismo em Rel é uma relação, e o morfismo correspondente na categoria oposta a Rel tem as setas invertidas, então é a relação inversa. Assim, Rel contém sua oposta e é auto-dual.^[4]

A involução representada pela inversão da relação fornece o dagger para tornar Rel uma categoria dagger.

A categoria possui dois functors em si mesma dados pelo functor hom: Uma relação binária R ⊆ A × B e sua transposição R^T ⊆ B × A podem ser compostas tanto como R R^T quanto como R^T R. A primeira composição resulta em uma relação homogênea em A e a segunda em B. Como as imagens desses funtores hom estão em Rel própria, neste caso hom é um functor hom interno. Com seu functor hom interno, Rel é uma categoria fechada, e além disso, uma categoria compacta dagger.

A categoria Rel pode ser obtida a partir da categoria Set como a categoria Kleisli para o monad cujo functor corresponde ao conjunto das partes, interpretado como um functor covariante.

Talvez um pouco surpreendente à primeira vista seja o fato de que o produto em Rel é dado pela união disjunta^[4]^:181 (em vez do produto cartesiano como é em Set), e o mesmo ocorre com o coproduto.

Rel é monoidal fechada, se definirmos tanto o produto monoidal A ⊗ B quanto o functor hom interno A ⇒ B pelo produto cartesiano de conjuntos. Também é uma categoria monoidal se definirmos o produto monoidal pela união disjunta de conjuntos.^[5]

A categoria Rel foi o protótipo para a estrutura algébrica chamada de alégora por Peter J. Freyd e Andre Scedrov em 1990.^[6] Começando com uma categoria regular e um funtor F: A → B, eles observam propriedades do funtor induzido Rel(A,B) → Rel(FA, FB). Por exemplo, ele preserva composição, conversão e interseção. Tais propriedades são então usadas para fornecer axiomas para uma alegoria.

Relações como objetos

David Rydeheard e Rod Burstall consideram que Rel possui objetos que são relações homogêneas. Por exemplo, A é um conjunto e R ⊆ A × A é uma relação binária em A. Os morfismos desta categoria são funções entre conjuntos que preservam uma relação: Dizemos que S ⊆ B × B é uma segunda relação e f: A → B é uma função tal que $xRy\implies f(x)Sf(y),$ então f é um morfismo.^[7]

A mesma ideia é avançada por Adamek, Herrlich e Strecker, onde eles designam os objetos (A, R) e (B, S), conjunto e relação.^[8]

Notas e referências

Notas

↑ Esta categoria é chamada de SetRel por Rydeheard e Burstall

Referências

↑ Mac Lane, S. (1988). Categories for the Working Mathematician 1st ed. [S.l.]: Springer. p. 26. ISBN 0-387-90035-7
↑ Pareigis, Bodo (1970). Categories and Functors. Col: Pure and Applied Mathematics. 39. [S.l.]: Academic Press. p. 6. ISBN 978-0-12-545150-5
↑ Bergman, George (1998). «§7.2 RelSet». An Invitation to General Algebra and Universal Constructions. [S.l.]: Henry Helson. ISBN 0-9655211-4-1
↑ ^a ^b Barr, Michael; Wells, Charles (1990). Category Theory for Computing Science (PDF). [S.l.]: Prentice Hall. 181 páginas. ISBN 978-0131204867
↑ Fong, Brendan; David I Spivak (2019). «Supplying bells and whistles in symmetric monoidal categories». arXiv:1908.02633 [math.CT]
↑ Freyd, Peter J.; Scedrov, Andre (1990). Categories, Allegories. [S.l.]: North Holland. pp. 79, 196. ISBN 0-444-70368-3
↑ Rydeheard, David; Burstall, Rod (1988). Computational Category Theory. [S.l.]: Prentice-Hall. 41 páginas. ISBN 978-0131627369
↑ Adamek, Juri; Herrlich, Horst; Strecker, George E. (2004) [1990]. «§3.3, example 2(d)». Abstract and Concrete Categories (PDF). [S.l.]: KatMAT Research group, University of Bremen. 22 páginas. Cópia arquivada (PDF) em 11 de agosto de 2022

[3] Esta categoria é chamada de SetRel por Rydeheard e Burstall

[1] Mac Lane, S. (1988). Categories for the Working Mathematician 1st ed. [S.l.]: Springer. p. 26. ISBN 0-387-90035-7

[2] Pareigis, Bodo (1970). Categories and Functors. Col: Pure and Applied Mathematics. 39. [S.l.]: Academic Press. p. 6. ISBN 978-0-12-545150-5

[4] Bergman, George (1998). «§7.2 RelSet». An Invitation to General Algebra and Universal Constructions. [S.l.]: Henry Helson. ISBN 0-9655211-4-1

[MB&CW-5] Barr, Michael; Wells, Charles (1990). Category Theory for Computing Science (PDF). [S.l.]: Prentice Hall. 181 páginas. ISBN 978-0131204867

[6] Fong, Brendan; David I Spivak (2019). «Supplying bells and whistles in symmetric monoidal categories». arXiv:1908.02633 [math.CT]

[7] Freyd, Peter J.; Scedrov, Andre (1990). Categories, Allegories. [S.l.]: North Holland. pp. 79, 196. ISBN 0-444-70368-3

[R&B-8] Rydeheard, David; Burstall, Rod (1988). Computational Category Theory. [S.l.]: Prentice-Hall. 41 páginas. ISBN 978-0131627369

[9] Adamek, Juri; Herrlich, Horst; Strecker, George E. (2004) [1990]. «§3.3, example 2(d)». Abstract and Concrete Categories (PDF). [S.l.]: KatMAT Research group, University of Bremen. 22 páginas. Cópia arquivada (PDF) em 11 de agosto de 2022

[1]

[2]

[nota 1]

[3]

[4]

[5]

[6]

[7]

[8]