category of sets equipped with an irreflexive binary relation

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

The pair (X,R)(X,R) can also be interpreted as a directed graph without loops (with vertex set XX and edge set RR), and the morphisms are precisely morphisms of directed graphs. Thus, Binirr=DiGraphNL,\Bin_{\irr} = \DiGraph_{NL}, and DiGraphNL\DiGraph_{NL} can be interpreted as the full subcategory of Quiv\Quiv, the category of quivers, consisting of quivers with no loops and 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 focus on the unambiguous notion of an irreflexive binary relation.
There are major categorical differences between Binirr\Bin_{\irr} and Bin\Bin; for example, Binirr\Bin_{\irr} has no terminal object.
It turns out that this category behaves exactly like Binsymm,irr\Bin_{\symm,\irr} (i.e. the category of undirected graphs, with loops not allowed), and the proofs of the properties are very similar.

Satisfied Properties

Assigned properties

Deduced properties

Unsatisfied Properties

Assigned properties

Deduced properties*

*This also uses the deduced satisfied properties.

Unknown properties

—

Special objects

  • initial object: (∅,∅)(\varnothing,\varnothing), which can be seen as the directed graph with no vertices and no edges
  • products: [non-empty case] The product of a non-empty 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. On the level of directed graphs, this means that we take the disjoint union of vertices and edges, with no edges between distinct components.

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 an irreflexive binary relation. This indicates that the data may be incomplete or that a distinguishing property may be missing from the database.