category of sets with a binary relation

 graph theory  set theory
Notation Bin\Bin Objects pairs (X,R)(X,R), where XX is a set and R⊆X×XR \subseteq X \times X is a binary relation Morphisms A morphism (X,R)→(Y,S)(X,R) \to (Y,S) is a relation-preserving map, i.e. a map f:X→Yf : X \to Y such that (x,x′)∈R(x,x') \in R implies (f(x),f(x′))∈S(f(x),f(x')) \in S. Related Set\Set, Rel\Rel, DiGraph\DiGraph, PreOrd\PreOrd, Pos\Pos, Mono\Mono

This category can also be viewed as a full subcategory of DiGraph\DiGraph consisting of directed graphs with at most one edge between any pair of vertices. Loops are allowed. It is a typical example of a quasitopos.

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: the singleton set {∗}\{\ast\} with the full relation
  • initial object: the empty set with the empty relation
  • products: The product of a family (Xi,Ri)i∈I(X_i,R_i)_{i \in I} is (∏i∈IXi,∏i∈IRi)(\prod_{i \in I} X_i, \prod_{i \in I} R_i), where ∏i∈IRi⊆∏i∈I(Xi×Xi)≅∏iXi×∏iXi\prod_{i \in I} R_i \subseteq \prod_{i \in I} (X_i \times X_i) \cong \prod_i X_i \times \prod_i X_i.
  • coproducts: The coproduct of a family (Xi,Ri)i∈I(X_i,R_i)_{i \in I} is (∐i∈IXi,∐i∈IRi)(\coprod_{i \in I} X_i, \coprod_{i \in I} R_i), where ∐i∈IRi⊆∐i∈I(Xi×Xi)⊆∐i∈IXi×∐i∈IXi\coprod_{i \in I} R_i \subseteq \coprod_{i \in I} (X_i \times X_i) \subseteq \coprod_{i \in I} X_i \times \coprod_{i \in I} X_i.

Special morphisms

  • isomorphisms: bijective maps that preserve and reflect the relation
  • monomorphisms: injective relation-preserving maps
  • epimorphisms: surjective relation-preserving maps
  • regular monomorphisms: injective maps that reflect and preserve the relation
  • regular epimorphisms: morphisms f:(X,R)→(Y,S)f : (X,R) \to (Y,S) such that f:X→Yf : X \to Y is surjective and S={(f(x),f(x′)):(x,x′)∈R}S = \{(f(x),f(x')) : (x,x') \in R\}