From mboxrd@z Thu Jan 1 00:00:00 1970 X-Msuck: nntp://news.gmane.io/gmane.science.mathematics.categories/3076 Path: news.gmane.org!not-for-mail From: Vaughan Pratt Newsgroups: gmane.science.mathematics.categories Subject: Re: Undirected graph citation Date: Mon, 06 Mar 2006 20:43:29 -0800 Organization: Stanford University Message-ID: <440D0F71.8080405@cs.stanford.edu> References: <005d01c64089$1b437220$0b00000a@C3> Reply-To: pratt@cs.stanford.edu NNTP-Posting-Host: main.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit X-Trace: ger.gmane.org 1241019081 7148 80.91.229.2 (29 Apr 2009 15:31:21 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Wed, 29 Apr 2009 15:31:21 +0000 (UTC) To: categories@mta.ca Original-X-From: rrosebru@mta.ca Tue Mar 7 10:02:45 2006 -0400 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Tue, 07 Mar 2006 10:02:45 -0400 Original-Received: from Majordom by mailserv.mta.ca with local (Exim 4.52) id 1FGci1-0007J5-NC for categories-list@mta.ca; Tue, 07 Mar 2006 09:58:41 -0400 User-Agent: Mozilla Thunderbird 0.9 (Windows/20041103) X-Accept-Language: en-us, en In-Reply-To: <005d01c64089$1b437220$0b00000a@C3> Original-Sender: cat-dist@mta.ca Precedence: bulk X-Keywords: X-UID: 22 Original-Lines: 70 Xref: news.gmane.org gmane.science.mathematics.categories:3076 Archived-At: 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