category of sets and relations

 set theory
Notation Rel\Rel Objects sets Morphisms A morphism from AA to BB is a relation, i.e. a subset of A×BA \times B. Related Set\Set, Bin\Bin External nLab link
This category is self-dual as it can be: There is an isomorphism Rel≅Relop\Rel \cong \Rel^{\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

Assigned properties

Deduced properties

Unsatisfied properties

Assigned properties

Deduced properties*

*This also uses the deduced satisfied properties.

Unknown properties

—

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: same as monomorphisms
  • regular epimorphisms: same as epimorphisms