category of sets equipped with a symmetric binary relation
If we define an undirected loop-graph as a pair with , the pair induces an undirected loop-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 binary relation.It turns out that this category behaves exactly like (i.e. the category of directed graphs), and the proofs of the properties are very similar.
Satisfied properties
Assigned properties (10)
- is locally small
- is complete
- is cocomplete
- is infinitary extensive
- is finitely accessible
- is locally cartesian closed
- has a regular subobject classifier
- has a generator
- has an extremal cogenerator
- has product-stable epimorphisms
Deduced properties (109)
- 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
- has coproducts
- is countably extensive
- has coproduct-stable monomorphisms
- has a generating collection
- is inhabited
- 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 Cauchy complete
- has finite-coproduct-stable monomorphisms
- has countable coproducts
- is extensive
- is filtered
- has directed colimits
- has sifted colimits
- has powers
- has ℵ₂-small products
- has wide pullbacks
- has coreflexive equalizers
- has kernel pairs
- is concretizable
- 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
- has an extremal generating collection
- is well-powered
- is locally multi-presentable
- is locally poly-presentable
- 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 a terminal object
- has finite powers
- has cofiltered limits
- is coregular
- has coquotients of cocongruences
- is cosifted
- has sequential colimits
- has ℵ₂-small copowers
- has binary coproducts
- has an initial object
- 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
- is connected
- 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 (4)
- is not skeletal
- is not semi-strongly connected
- does not have an extremal generator
- is not co-Malcev
Deduced properties (97)*
- is not epi-regular
- is not strongly connected
- is not core-connected
- is not balanced
- is not one-sorted finitary algebraic
- is not gaunt
- is not direct
- is not thin
- is not additive
- is not inverse
- is not self-dual
- is not preadditive
- is not abelian
- does not have a strict terminal object
- 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
- is not a groupoid
- is not mono-regular
- 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
- does not have biproducts
- does not have effective congruences
- does not have kernels
- does not satisfy CIP
- is not coaccessible
- is not pointed
- is not normal
- 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 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 cokernels
- does not have exact cofiltered limits
- is not quotient-trivial
- is not generalized direct
- does not satisfy CSP
- is not infinitary coextensive
- is not an elementary cotopos
- is not a Grothendieck cotopos
- is not a precotopos
- is not a quasicotopos
- is not unital
- is not co-quasi-pointed
- is not a generalized variety
- is not Barr-exact
- is not an elementary topos
- is not a Grothendieck topos
- is not counital
- does not have a coparametrized conatural numbers object
- is not locally finitely copresentable
- is not ℵ₁-coaccessible
- is not dually finitary algebraic
- is not locally multi-copresentable
- is not locally finitely multi-copresentable
- is not locally poly-copresentable
- is not dually multi-algebraic
- does not have disjoint finite products
- is not countably codistributive
- is not generalized inverse
- is not finitary algebraic
- is not multi-algebraic
- is not a pretopos
- is not locally ℵ₁-copresentable
- is not dually one-sorted finitary algebraic
- does not have disjoint products
- is not infinitary codistributive
*This also uses the deduced satisfied properties.
Unknown properties
All 220 category properties are decided, 206 of them by deduction.
—
Special objects
- terminal object: , which can be seen as the undirected loop-graph with a single vertex and a loop
- initial object: , which can be seen as the undirected loop-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 binary relation. This indicates that the data may be incomplete or that a distinguishing property may be missing from the database.
Comments
- The inclusion functor has a left adjoint mapping to .
- The inclusion functor has a right adjoint mapping to .
- 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) and no morphism from the terminal object (i.e. have no loops). In , there is only one such graph, , whereas in there are two: and .