category of sets equipped with a reflexive binary relation

 graph theory  relational structures
Notation Binrefl\Bin_{\refl} Alternative notation DiGraphrefl\DiGraph_{\refl} Objects pairs (X,R)(X,R), where XX is a set and R⊆X×XR \subseteq X \times X is a reflexive 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 Bin\Bin, Binsymm,refl\Bin_{\symm,\refl}, Binsymm\Bin_{\symm}, Binsymm,irr\Bin_{\symm,\irr}, Binirr\Bin_{\irr}, PreOrd\PreOrd

The pair (X,R)(X,R) can also be interpreted as a directed graph (with vertex set XX and edge set RR) that is reflexive, i.e. in which every vertex has a loop, and the morphisms are precisely morphisms of directed graphs. Thus, Binrefl=DiGraphrefl,\Bin_{\refl} = \DiGraph_{\refl}, and DiGraphrefl\DiGraph_{\refl} can be interpreted as a full subcategory of DiGraph\DiGraph. 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. Instead, we can focus on the unambiguous notion of a reflexive binary relation.
This category shares many properties with Bin\Bin. Two differences are that Binrefl\Bin_{\refl} is semi-strongly connected and has an extremal generator.

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 reflexive directed graph with a single vertex
  • initial object: (∅,∅)(\varnothing,\varnothing), which can be seen as the reflexive 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 reflexive binary relation. This indicates that the data may be incomplete or that a distinguishing property may be missing from the database.

Comments

  • The inclusion functor Binrefl→Bin\Bin_{\refl} \to \Bin has a left adjoint mapping (X,R)(X,R) to (X,R∪ΔX)(X,R \cup \Delta_X).
  • The inclusion functor Binrefl→Bin\Bin_{\refl} \to \Bin has a right adjoint mapping (X,R)(X,R) to (X~,R∣X~)(\tilde{X},R|_{\tilde{X}}), where X~={x∈X:(x,x)∈R}\tilde{X} = \{x \in X : (x,x) \in R\}.