Re: Undirected graph citation

[Vaughan Pratt <pratt@cs.stanford.edu>]

George Janelidze wrote:
>
> Indeed, there were no monoids in Vaughan's original message of February 28,

My take on monoids vs. initial segments of Delta, FinSet, etc. as sites
for a category of presheaves is that it is like Hasse diagrams vs.
posets, or axioms vs. theories.  The former should be understood only as
a convenient representation of its idempotent completion, just as a
Hasse diagram of a poset is a convenient representation of its reflexive
transitive closure, or an axiom system a convenient representation of a
theory.

In the case of reflexive undirected graphs as a presheaf category, the
monoid Set(2,2) works as a site but is not idempotent closed (the two
constant functions don't split).  In the category of sets with one or
two elements however, the terminator splits the constant functions, as
it does in any category with a terminator if one defines "constant
morphism" as an idempotent split by the terminator.

The benefit of idempotent closed sites is that equivalent presheaf
categories must then have equivalent sites, as I learned from Jiri
Adamek's post on this list the other week asking for the earliest
reference to that fact.  I subsequently learned the proof from Borceux
Vol I (Theorem 6.5.11, where idempotent completion is called by its
synonym Cauchy completion).

My question was about the theory, for which Bill pointed out a nice
axiomatization.

As it turns out, the earliest reference answering my original question
may well be this very list!  At the risk of embarrassing Marco Grandis
(to whom I therefore apologize in advance), the 1999 monoid-on-graphs
thread at

   http://www.mta.ca/~cat-dist/catlist/1999/monoid-on-graphs

includes two posts by Marco, the first asserting that FinSet could be
substituted for Delta in the definition of reflexive graphs as
presheaves on the truncation of that site, the second recanting a day
later and pointing out the impact of the twist:2->2 in creating what he
called at the time involutive reflexive graphs.  Marco subsequently
wrote about symmetric simplicial complexes as the higher-dimensional
generalization of the impact of the twist.

So far no one has mentioned an earlier explicit reference than this
March 1999 one in response to my question.  Bill mentioned Sets for
Mathematics, but that was 2003.

I did however receive two private responses from a La Jolla 1965
participant who first protested that surely presheaves on the site I
asked about were *directed* graphs, but then with the same one-day pause
as Marco pointed out the role of the twist in binding together the two
directions of an undirected edge.  (I assume this is history repeating
itself and not the email counterpart of a standup routine the experts do
from time to time for our edutainment.  In standup, timing is as
important as content.)

My own excuse for not noticing Marco's 1999 posts, or for that matter
Francois Lamarche's citation question sparking that whole thread, is
that I was in Hanover that week exhibiting at CeBIT what Guinness
Records 2000 subsequently listed as the world's smallest webserver
(p.162, nestled interestingly when the book is closed).  Bad timing on
my part, that was a useful thread.

It's impressive what can come out of a simple request for citations on
this list.

Vaughan