category of sets equipped with a symmetric reflexive binary relation

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

If we define a reflexive undirected graph as a pair (V,E)(V,E) with E⊆P1,2(V)E \subseteq P_{1,2}(V) such that {v}∈E\{v\} \in E for all v∈Vv \in V, then the pair (X,R)(X,R) induces a reflexive undirected graph (X,{{x,x′}:(x,x′)∈R})(X,\{\{x,x'\} : (x,x') \in R\}), and this gives an isomorphism of categories Binsymm,refl≅Graphrefl.\Bin_{\symm,\refl} \cong \Graph_{\refl}. 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 "graph" in the literature (simple? multiple edges? loops? finite?). Instead, we can focus on the unambiguous notion of a symmetric reflexive binary relation.
It turns out that this category behaves exactly like Binrefl\Bin_{\refl} (i.e. the category of reflexive directed graphs), 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

  • terminal object: ({∗},{(∗,∗)})(\{\ast\},\{(\ast,\ast)\}), which can be seen as the reflexive undirected graph with a single vertex and a loop
  • initial object: (∅,∅)(\varnothing,\varnothing), which can be seen as the reflexive undirected graph with no vertices and no 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 symmetric reflexive binary relation. This indicates that the data may be incomplete or that a distinguishing property may be missing from the database.

Comments

  • The "category of simple graphs" studied in the nLab is a misnomer. The nLab article actually studies the current category Binsymm,refl\Bin_{\symm,\refl}. Although its objects correspond to undirected graphs, since reflexive relations correspond to irreflexive relations by removing the diagonal, the morphisms are not the same. As mentioned here, the category of undirected graphs is isomorphic to the category of sets equipped with an irreflexive symmetric relation. While it is true that this category does not behave as well as the category of sets equipped with a reflexive symmetric relation, this does not justify renaming it.
  • Although the categories Binsymm,refl\Bin_{\symm,\refl} and Binrefl\Bin_{\refl}, or equivalently Graphrefl\Graph_{\refl} and DiGraphrefl\DiGraph_{\refl}, agree on all properties currently recorded in the database, they are not equivalent categories. In both categories, we can then count the connected objects up to isomorphism that admit exactly two morphisms from the terminal object, i.e. have two vertices. In Graphrefl\Graph_{\refl}, there is only one such graph, ∙⟷∙\bullet \longleftrightarrow \bullet (loops not shown), whereas in DiGraphrefl\DiGraph_{\refl} there are two: ∙⟶∙\bullet \longrightarrow \bullet and ∙⟷∙\bullet \longleftrightarrow \bullet (loops not shown).