category of sets equipped with a symmetric irreflexive binary relation
If we define an undirected graph as a pair with , the pair induces an undirected graph , and this gives an isomorphism of categories 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 irreflexive binary relation.It turns out that this category behaves exactly like (i.e. the category of directed graphs without loops), and the proofs of the properties are very similar.
Satisfied properties
Assigned properties (12)
- is locally small
- has connected limits
- has binary products
- is infinitary extensive
- is finitely accessible
- is locally cartesian closed
- has cokernel pairs
- has coequalizers of kernel pairs
- has cocartesian cofiltered limits
- has a generator
- is well-copowered
- has effective cocongruences
Deduced properties (57)
- has filtered-colimit-stable monomorphisms
- is ℵ₁-accessible
- has filtered colimits
- is locally finitely multi-presentable
- has pullbacks
- has pullback-stable regular epimorphisms
- has coproducts
- is countably extensive
- has coproduct-stable monomorphisms
- has a generating collection
- is inhabited
- has binary powers
- has equalizers
- has wide pullbacks
- has kernel pairs
- is Cauchy complete
- is locally essentially small
- has cofiltered limits
- has finite coproducts
- has cosifted limits
- is accessible
- has ℵ₁-filtered colimits
- is multi-cocomplete
- has coreflexive equalizers
- has finite-coproduct-stable monomorphisms
- has countable coproducts
- is extensive
- has directed colimits
- is concretizable
- is cosifted
- has directed limits
- has ℵ₁-cofiltered limits
- has copowers
- has ℵ₂-small coproducts
- has binary coproducts
- has an initial object
- has finite copowers
- has an extremal generating collection
- is well-powered
- is locally multi-presentable
- is locally poly-presentable
- has a strict initial object
- has disjoint finite coproducts
- is sifted
- has sequential limits
- has a multi-initial object
- has coquotients of cocongruences
- is connected
- is ℵ₁-cofiltered
- has sequential colimits
- has ℵ₂-small copowers
- has countable copowers
- has binary copowers
- has disjoint coproducts
- has a conatural numbers object
- has equalizers of cokernel pairs
- is cofiltered
Unsatisfied properties
Assigned properties (6)
- is not skeletal
- is not semi-strongly connected
- is not filtered
- does not have quotients of congruences
- does not have an extremal generator
- does not have a cogenerating collection
Deduced properties (145)*
- does not have reflexive coequalizers
- does not have effective congruences
- is not core-thin
- is not strongly connected
- is not core-connected
- is not thin
- is not finitely cocomplete
- is not ℵ₁-filtered
- is not balanced
- is not one-sorted finitary algebraic
- is not gaunt
- is not direct
- is not an elementary topos
- does not have a cogenerator
- does not have an extremal cogenerating collection
- is not inverse
- is not self-dual
- is not Grothendieck abelian
- is not a generalized variety
- does not have zero morphisms
- is not trivial
- is not discrete
- is not essentially discrete
- does not have cofiltered-limit-stable epimorphisms
- is not left cancellative
- does not have coequalizers
- does not have a terminal object
- does not have sifted colimits
- is not a groupoid
- is not mono-regular
- is not Barr-exact
- is not regular-subobject-trivial
- is not retract-trivial
- is not one-way
- is not a quasitopos
- is not co-Malcev
- is not counital
- is not coaccessible
- is not co-Grothendieck abelian
- is not cocartesian coclosed
- is not cocomplete
- does not have exact cofiltered limits
- is not countably coextensive
- is not right cancellative
- does not have an extremal cogenerator
- is not epi-regular
- does not have pushouts
- is not coregular
- is not essentially small
- does not have a quotient object classifier
- does not have a regular quotient object classifier
- is not locally finite
- is not essentially countable
- is not essentially finite
- is not an elementary cotopos
- is not a quasicotopos
- does not have a natural numbers object
- is not locally finitely presentable
- is not locally ℵ₁-presentable
- is not locally presentable
- is not finitary algebraic
- is not preadditive
- does not have biproducts
- is not multi-algebraic
- does not have a multi-terminal object
- does not have kernels
- does not satisfy CIP
- is not generalized inverse
- does not have connected colimits
- is not pointed
- is not quasi-pointed
- is not normal
- does not have finite products
- does not have finite powers
- is not small
- is not finite
- is not countable
- does not have all monomorphisms split
- does not have a subobject classifier
- is not subobject-trivial
- is not an EI-category
- is not a pretopos
- is not total
- does not have a coparametrized conatural numbers object
- is not locally copresentable
- is not locally finitely copresentable
- is not finitely coaccessible
- is not ℵ₁-coaccessible
- is not locally multi-copresentable
- is not locally poly-copresentable
- is not a dual generalized variety
- is not locally cocartesian coclosed
- is not coextensive
- does not have cokernels
- is not quotient-trivial
- is not generalized direct
- does not satisfy CSP
- is not infinitary coextensive
- is not dually one-sorted finitary algebraic
- does not have a strict terminal object
- is not co-quasi-pointed
- is not conormal
- does not have wide pushouts
- does not have pushout-stable regular monomorphisms
- is not Barr-coexact
- does not have all epimorphisms split
- is not regular-quotient-trivial
- is not a Grothendieck cotopos
- is not cototal
- is not unital
- does not have a parametrized natural numbers object
- is not complete
- is not additive
- is not abelian
- is not split abelian
- is not cartesian closed
- is not finitely complete
- is not multi-complete
- is not infinitary distributive
- is not countably distributive
- is not distributive
- does not have cartesian filtered colimits
- does not have countable products
- does not have countable powers
- is not a Grothendieck topos
- is not countably codistributive
- is not locally ℵ₁-copresentable
- is not dually finitary algebraic
- is not locally finitely multi-copresentable
- is not dually multi-algebraic
- does not have disjoint finite products
- is not codistributive
- does not have finite-product-stable epimorphisms
- is not a precotopos
- is not Malcev
- does not have products
- does not have exact filtered colimits
- does not have ℵ₂-small products
- does not have ℵ₂-small powers
- is not regular
- does not have a regular subobject classifier
- does not have disjoint products
- is not infinitary codistributive
- does not have product-stable epimorphisms
- does not have powers
*This also uses the deduced satisfied properties.
Unknown properties
All 220 category properties are decided, 202 of them by deduction.
—
Special objects
- initial object: , 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 in is , where .
- coproducts: The coproduct of a family in is , where . 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 such that is surjective and
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.
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 and , or equivalently and , agree on all properties currently recorded in the database, they are not equivalent categories. In both categories, the one-vertex graph 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 (i.e. have two vertices). In , there is only one such graph, , whereas in there are two: and .