nLab
reflexive graph

Contents

Idea

A graph is reflexive if for each vertex vv there is a (specified) edge vvv \to v.

Properties

Proposition

The category of reflexive directed graphs RefGphRefGph, i.e., reflexive quivers, equipped with the functor U:RefGphSetU: RefGph \to Set which sends a graph to its set of edges, is monadic over SetSet.

Proof

RefGphRefGph is the category of functors RSetR \to Set where RR is the walking reflexive fork, consisting of two objects 0,10, 1 and generated by arrows i:01i: 0 \to 1 and s,t:10s, t: 1 \to 0 subject to si=1 0=tis i = 1_0 = t i and no other relations. This RR is in turn the Cauchy completion of a monoid MM consisting of two elements e 0=is,e 1=ite_0 = i s, e_1 = i t and an identity, with multiplication e 0e 0=e 0=e 1e 0e_0 e_0 = e_0 = e_1 e_0 and e 1e 1=e 1=e 0e 1e_1 e_1 = e_1 = e_0 e_1, and therefore RefGphRefGph is equivalent to the category of functors MSetM \to Set, i.e., the category of MM-sets Set MSet^M. This is the category of algebras of the monad M×M \times - whose monad structure is induced from the monoid structure of MM.

Revised on March 6, 2016 11:58:53 by Todd Trimble (67.81.95.215)