category of sets and relations

  • notation: Rel\mathbf{Rel}
  • objects: sets
  • morphisms: A morphism from AA to BB is a relation, i.e. a subset of A×BA \times B.
  • Related categories: Set\mathbf{Set}
  • nLab Link

This category is self-dual as it can be: There is an isomorphism Rel≅Relop\mathbf{Rel} \cong \mathbf{Rel}^{\mathrm{op}} that is the identity on objects and maps a relation to its opposite relation. It is the prototype of a dagger-category.

Satisfied Properties

Properties from the database

Deduced properties

Unsatisfied Properties

Properties from the database

Deduced properties*

*This also uses the deduced satisfied properties.

Unknown properties

There are 2 properties for which the database doesn't have an answer if they are satisfied or not. Please help to contribute the data!

Special objects

  • terminal object: empty set
  • initial object: empty set
  • products: disjoint unions (!)
  • coproducts: disjoint union

Special morphisms

  • isomorphisms: bijective functions
  • monomorphisms: A relation R:A→BR : A \to B is a monomorphism iff the map R∗:P(A)→P(B)R_* : P(A) \to P(B) defined by T↦{b∈B:∃ a∈T:(a,b)∈R}T \mapsto \{b \in B : \exists \, a \in T: (a,b) \in R \} is injective.
  • epimorphisms: A relation R:A→BR : A \to B is an epimorphism iff the map R∗:P(B)→P(A)R^* : P(B) \to P(A) defined by S↦{a∈A:∃ b∈S:(a,b)∈R}S \mapsto \{a \in A : \exists \, b \in S: (a,b) \in R \} is injective.
  • regular monomorphisms:
  • regular epimorphisms: