category of sets equipped with a binary relation

 graph theory  relational structures
Notation Bin\Bin Alternative notation DiGraph\DiGraph Objects pairs (X,R)(X,R), where XX is a set and R⊆X×XR \subseteq X \times X is a binary relation on XX 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 Quiv\Quiv, Binirr\Bin_{\irr}, Binsymm\Bin_{\symm}, Binsymm,irr\Bin_{\symm,\irr}, Binrefl\Bin_{\refl}, Binsymm,refl\Bin_{\symm,\refl}, Pos\Pos, PreOrd\PreOrd
The pair (X,R)(X,R) can also be interpreted as a directed graph (with vertex set XX and edge set RR), where loops are allowed, and the morphisms are precisely the morphisms of directed graphs. Thus, Bin=DiGraph,\Bin = \DiGraph, and DiGraph\DiGraph can be interpreted as the full subcategory of Quiv\Quiv, the category of quivers, consisting of quivers with at most one edge between any pair of vertices. In the proofs below, however, we will mostly not use the graph-theoretic interpretation and instead work with binary relations. This simplifies the exposition and has the additional advantage that we do not need to deal with the varying definitions of the term "directed graph" in the literature (in particular, there is no complete consensus on whether loops are allowed). Instead, we can work with the unambiguous notion of a binary relation.
The category Bin\Bin 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: ({∗},{(∗,∗)})(\{\ast\},\{(\ast,\ast)\}), which can be seen as the directed graph with a single vertex and a loop
  • initial object: (∅,∅)(\varnothing,\varnothing), which can be seen as the directed graph with no vertices and no directed edges
  • 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\}

Indistinguishable categories

These categories in the database currently have exactly the same properties as the category of sets equipped with a binary relation. This indicates that the data may be incomplete or that a distinguishing property may be missing from the database.

Comments

  • The forgetful functor Bin→Set\Bin \to \Set has a left adjoint mapping a set XX to (X,∅)(X,\varnothing).
  • The forgetful functor Bin→Set\Bin \to \Set has a right adjoint mapping a set XX to (X,X×X)(X,X \times X).