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