Relations in category theory

These categorical structures are closely related to fragments of first-order logic:

• Regular logic : \(\wedge\), \(\top\), \(\exists\)
  • See Remark 2.9 (iii) in (Carboni & Walters, 1987)
• Coherent logic : \(\wedge\), \(\vee\), \(\top\), \(\bot\), \(\exists\)

For references, see page on categorical logic.

Rel, the category of sets and relations:

• Coecke & Paquette, 2010: Categories for the practicing physicist (doi, arxiv)
  • Sec 3.4.2: Detailed treatment of Rel as dagger compact monoidal category
  • Sec 3.5.5: Categorical matrix calculus in Rel
  • Sec 3.5.7: Internal monoids and comonoids (used in Carboni & Walters)
  • Sec 3.5.8: Frobenius equations in Rel
• Selinger, 1999: Categorical structure of asynchrony (doi, pdf)
  • Sec 2.1: Two different traces on Rel

RRel, the double category of sets, functions, and relations:

• Grandis & Paré, 1999: Limits in double categories (pdf)
  • Defined in Sec. 3.4: Relations
  • 2-cells are squares satisfying \(Rg \subseteq fS\), where the composition is composition of relations
• Baez & Master, 2018: Open Petri nets (arxiv, Azimuth 1 ,2 ,3 )
  • Defined in Sec. 5: The double category of relations
  • 2-cells are squares satisfying \((f \times g)R \subseteq S\), where LHS is image of \(R\) under \(f \times g\)
• Lambert, 2021: Double categories of relations (arxiv)

Allegories

Monograph treatments:

• Freyd & Scedrov, 1990: Categories, Allegories
• Johnstone, 2002: Sketches of an Elephant, Ch. A3: Allegories

Applications of allegories in computer science:

• Brown & Hutton, 1994: Categories, allegories, and circuit design (doi, pdf)
• Brown & Jeffrey, 1994: Allegories of circuits (doi)
• Gallego Arias & Lipton, 2012: Logic programming in tabular allegories (doi)
• Zieliński et al, 2013: Allegories for database modeling (doi)

Bicategories of relations

The two main papers by Carboni and Walters:

• Carboni & Walters, 1987: Cartesian bicategories I (doi)
• Carboni, Kelly, Walters, Wood, 2008: Cartesian bicategories II (pdf, arxiv)

Related papers by Carboni, Walters, and their coauthors:

• Carboni, Kasangian, Street, 1984: Bicategories of spans and relations (doi)
• Carboni, 1987: Bicategories of partial maps (doi , pdf)
• Katis, Sabadini, Walters, 1997: Bicategories of processes (doi)
• Katis, Sabadini, Walters, 1997: Span(Graph): A categorical algebra of transition systems (doi)
• Walters & Wood, 2008: Frobenius objects in cartesian bicategories (arxiv, pdf)
• Lack, Walters, Wood, 2010: Bicategories of spans as cartesian bicategories (arxiv, pdf)

Comparing allegories and bicategories of relations:

• Knijnenburg & Nordemann, 1994: Two categories of relations (pdf)
• Lawler, 2015: PhD thesis: Fibrations of predicates and bicategories of relations, Sec 2: Categories, fibrations, and allegories (arxiv)

Other works related to bicategories of relations:

• Fong & Spivak, 2019: Graphical regular logic (arxiv, nCat Cafe )
  • Conference version: Fong & Spivak, 2019: String diagrams for regular logic (extended abstract) (arxiv)
• Fong & Spivak, 2019: Regular and relational categories: Revisiting ’Cartesian bicategories I’ (arxiv)
• Bonchi, Pavlovic, Sobocinksi, 2017: Functorial semantics for relational theories (arxiv)
• Bonchi, Seeber, Sobocinksi, 2020: Cartesian bicategories with choice (arxiv)
• Bonchi, Santamaria, Seeber, Sobocinksi, 2021: On doctrines and cartesian bicategories (arxiv)

Applications of bicategories of relations:

• Heunen & Tull, 2015: Categories of relations as models of quantum theory (arxiv)
• Patterson, 2017: Knowledge representation in bicategories of relations (arxiv)