category of sets equipped with a symmetric irreflexive binary relation

Unknown properties

—

Special objects

• initial object: $(\varnothing,\varnothing)$, which can be seen as the undirected graph with no vertices and no edges
• products: [non-empty case] The product of a non-empty family $(X_i,R_i)_{i \in I}$ in $\Bin_{\symm,\irr}$ is $(\prod_{i \in I} X_i, \prod_{i \in I} R_i)$, where $\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 $(X_i,R_i)_{i \in I}$ in $\Bin_{\symm,\irr}$ is $(\coprod_{i \in I} X_i, \coprod_{i \in I} R_i)$, where $\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 undirected 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) \to (Y,S)$ such that $f : X \to Y$ is surjective and $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 irreflexive binary relation. This indicates that the data may be incomplete or that a distinguishing property may be missing from the database.

• category of sets equipped with an irreflexive binary relation

Comments

• The "category of simple graphs" studied in the nLab is a misnomer. The nLab article actually studies the category of sets equipped with a reflexive symmetric relation. Although the objects correspond to undirected graphs, since reflexive relations correspond to irreflexive relations by removing the diagonal, the morphisms are not the same. As mentioned above, 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 $\Bin_{\symm,\irr}$ and $\Bin_{\irr}$, or equivalently $\Graph$ and $\DiGraph_{NL}$, agree on all properties currently recorded in the database, they are not equivalent categories. In both categories, the one-vertex graph $K_1$ without edges can be characterized up to isomorphism as the unique connected object that admits a morphism to every non-initial object. We can then count the connected objects up to isomorphism that admit exactly two morphisms from $K_1$ (i.e. have two vertices). In $\Graph$, there is only one such graph, $\bullet \longleftrightarrow \bullet$, whereas in $\DiGraph_{NL}$ there are two: $\bullet \longrightarrow \bullet$ and $\bullet \longleftrightarrow \bullet$.