Re: Undirected graph citation

Re: Undirected graph citation

[F W Lawvere]

As Clemens Berger reminds us, the category of small categories
is a reflective subcategory of simplicial sets, with a reflector that
preserves finite products. But as I mentioned, there is a similar
"advantage" for the Boolean algebra classifier (=presheaves on non-empty
finite cardinals, or "symmetric" simplicial sets):
The category of small groupoids is reflective in this topos, with the
reflector preserving finite products. Thus the Poincare' groupoid of a
simplicial complex is directly available. (The simplicial complexes are
merely the objects generated weakly by their points, a relation which
defines a cartesian closed reflective subcategory of any topos.)

It is not clear how one is to measure the loss or gain of combinatorial
information in composing the various singular and realization functors
between these different models. Is there such a measure?


Bill Lawvere

************************************************************
F. William Lawvere
Mathematics Department, State University of New York
244 Mathematics Building, Buffalo, N.Y. 14260-2900 USA
Tel. 716-645-6284
HOMEPAGE:  http://www.acsu.buffalo.edu/~wlawvere
************************************************************

Re: Undirected graph citation

[George Janelidze]

I am not sure if I really understand what is the target of this discussion,
but I would like to make some comments to Bill's messages:

The Poincare' groupoid is (up to an equivalence) nothing but the largest
Galois groupoid, and it is directly available as soon as one has what I call
Galois structure in my several papers, if we assume that every object of the
ground category has a universal covering. This is certainly the case for
every locally connected topos with coproducts and enough projectives.
Therefore this is certainly the case for every presheaf topos. Therefore
what Bill means by "directly available" should be not "available without
going through geometric realization" but just "can be calculated as the
result of reflection" (probably this is exactly what Bill had in mind).

Moreover, it was Grothendieck's observation that Galois/fundamental
groupoids are to be defined as quotients of certain equivalence relations -
in fact kernel pairs, and this observation was used by many authors in topos
theory and elsewhere; my own observation (1984) then was that one can make
Galois theory purely categorical by using not "quotients" but "images under
a left adjoint" (the first prototype for me was actually not Grothendieck's
but Andy Magid's "componentially locally strongly separable" Galois theory
of commutative rings). What I am trying to conclude is that the
Galois/fundamental groupoids actually arise not from anything simplicial but
from abstract category theory: it is just a result of a game with adjoint
functors between categories with pullbacks.

In another message Bill says: "A similar lacuna of explicitness occurs in
many papers on Galois theory where pregroupoids are an intermediate step ;
the description of  the pregroupoid concept is really just a presentation
of the monoid of endomaps of the 4-element set..." Assuming that everyone
understands that this is not about classical Galois theory (I don't think
somebody like J.-P. Serre ever mentions pregroupoids) and not about what
Anders Kock calls pregroupoids, let me again return to the categorical
Galois theory:

If p : E ---> B is an "extension" in a category C, R its kernel pair, and F
: C ---> X the left adjoint involved in a given Galois theory, then one
wants to define the Galois groupoid Gal(E,p) as F(R) = the image of R under
F (I usually write I instead of F, but in an email message this does not
look good...). But if our extension p : E ---> B is not normal, then, since
F usually does not preserve pullbacks, F(R) is not a groupoid - it is a
weaker structure, the "equational part" of groupoid structure. This weaker
structure is still good enough to define its internal actions in X and these
internal actions classify covering objects over B split by (E,p). Hence this
weaker structure needs a name and I called it "pregroupoid" (I did not know
that this term was already overused for almost the same and for unrelated
concepts). I cannot speak for everyone, but for my own purposes there are
actually several possible candidates for the notion of pregroupoid and half
of them can certainly be defined as monoid actions for a specific monoid,
like the one Bill mentions. However, in each case we deal with a "very
small" category actions and it is a triviality to observe that that category
can be replaced with a monoid. Essentially, what you need is to check that
the terminal object (in your category of pregroupoids) has either no proper
subobjects or only one such, which must be initial. In this observation -
due to Max Kelly, about the categories monadic over powers of Sets being
monadic over Sets, one usually says "strictly initial"; but we can omit
"strictly" here since it is about a topos.

George Janelidze

----- Original Message -----
From: "F W Lawvere" <wlawvere@buffalo.edu>
To: <categories@mta.ca>
Sent: Thursday, March 02, 2006 8:32 PM
Subject: categories: Re: Undirected graph citation


>
> As Clemens Berger reminds us, the category of small categories
> is a reflective subcategory of simplicial sets, with a reflector that
> preserves finite products. But as I mentioned, there is a similar
> "advantage" for the Boolean algebra classifier (=presheaves on non-empty
> finite cardinals, or "symmetric" simplicial sets):
> The category of small groupoids is reflective in this topos, with the
> reflector preserving finite products. Thus the Poincare' groupoid of a
> simplicial complex is directly available. (The simplicial complexes are
> merely the objects generated weakly by their points, a relation which
> defines a cartesian closed reflective subcategory of any topos.)
>
> It is not clear how one is to measure the loss or gain of combinatorial
> information in composing the various singular and realization functors
> between these different models. Is there such a measure?
>
>
> Bill Lawvere
>
> ************************************************************
> F. William Lawvere
> Mathematics Department, State University of New York
> 244 Mathematics Building, Buffalo, N.Y. 14260-2900 USA
> Tel. 716-645-6284
> HOMEPAGE:  http://www.acsu.buffalo.edu/~wlawvere
> ************************************************************
>
>
>
>
>
>
>

Re: Undirected graph citation

[F W Lawvere]

Dear George,

   Concerning undirected graphs, the Boolean algebra classifier, and
the intermediate sub-topos that suffices for groupoids:

   The special feature of these toposes I wanted to emphasize is not that
some of them can be generated by monoids, but rather (whether one splits
idempotents or not) that the site of operators is itself a full
subcategory of the category of sets. This is a small part of the point
that Vaughn wanted to make, I believe. Having the direct visualization of
this system of operators available as merely maps between certain small
sets is a useful auxiliary to formal presentations of the d,s kind.
As you mention, a basic way in which such presheaves can arise is by
applying a non-exact functor F to a group; the fact that the exponents on
the group are just these ordinary sets explains why we obtain an object
in this sort of topos (which can serve as a presentation of another group,
if desired).

   As noted in my unpublished (but widely distributed) paper on toposes
generated by codiscrete objects, the Yoneda embedding in these cases
produces of course a full sub-category of a topos, one which looks
exactly like (a piece of) the category of sets; of course this is not
the discrete inclusion, but its dialectical opposite, the codiscrete one.

Bill
************************************************************
F. William Lawvere
Mathematics Department, State University of New York
244 Mathematics Building, Buffalo, N.Y. 14260-2900 USA
Tel. 716-645-6284
HOMEPAGE:  http://www.acsu.buffalo.edu/~wlawvere
************************************************************



On Fri, 3 Mar 2006, George Janelidze wrote:

> I am not sure if I really understand what is the target of this discussion,
> but I would like to make some comments to Bill's messages:
>
> The Poincare' groupoid is (up to an equivalence) nothing but the largest
> Galois groupoid, and it is directly available as soon as one has what I call
> Galois structure in my several papers, if we assume that every object of the
> ground category has a universal covering. This is certainly the case for
> every locally connected topos with coproducts and enough projectives.
> Therefore this is certainly the case for every presheaf topos. Therefore
> what Bill means by "directly available" should be not "available without
> going through geometric realization" but just "can be calculated as the
> result of reflection" (probably this is exactly what Bill had in mind).
>
> Moreover, it was Grothendieck's observation that Galois/fundamental
> groupoids are to be defined as quotients of certain equivalence relations -
> in fact kernel pairs, and this observation was used by many authors in topos
> theory and elsewhere; my own observation (1984) then was that one can make
> Galois theory purely categorical by using not "quotients" but "images under
> a left adjoint" (the first prototype for me was actually not Grothendieck's
> but Andy Magid's "componentially locally strongly separable" Galois theory
> of commutative rings). What I am trying to conclude is that the
> Galois/fundamental groupoids actually arise not from anything simplicial but
> from abstract category theory: it is just a result of a game with adjoint
> functors between categories with pullbacks.
>
> In another message Bill says: "A similar lacuna of explicitness occurs in
> many papers on Galois theory where pregroupoids are an intermediate step ;
> the description of  the pregroupoid concept is really just a presentation
> of the monoid of endomaps of the 4-element set..." Assuming that everyone
> understands that this is not about classical Galois theory (I don't think
> somebody like J.-P. Serre ever mentions pregroupoids) and not about what
> Anders Kock calls pregroupoids, let me again return to the categorical
> Galois theory:
>
> If p : E ---> B is an "extension" in a category C, R its kernel pair, and F
> : C ---> X the left adjoint involved in a given Galois theory, then one
> wants to define the Galois groupoid Gal(E,p) as F(R) = the image of R under
> F (I usually write I instead of F, but in an email message this does not
> look good...). But if our extension p : E ---> B is not normal, then, since
> F usually does not preserve pullbacks, F(R) is not a groupoid - it is a
> weaker structure, the "equational part" of groupoid structure. This weaker
> structure is still good enough to define its internal actions in X and these
> internal actions classify covering objects over B split by (E,p). Hence this
> weaker structure needs a name and I called it "pregroupoid" (I did not know
> that this term was already overused for almost the same and for unrelated
> concepts). I cannot speak for everyone, but for my own purposes there are
> actually several possible candidates for the notion of pregroupoid and half
> of them can certainly be defined as monoid actions for a specific monoid,
> like the one Bill mentions. However, in each case we deal with a "very
> small" category actions and it is a triviality to observe that that category
> can be replaced with a monoid. Essentially, what you need is to check that
> the terminal object (in your category of pregroupoids) has either no proper
> subobjects or only one such, which must be initial. In this observation -
> due to Max Kelly, about the categories monadic over powers of Sets being
> monadic over Sets, one usually says "strictly initial"; but we can omit
> "strictly" here since it is about a topos.
>
> George Janelidze
>
> ----- Original Message -----
> From: "F W Lawvere" <wlawvere@buffalo.edu>
> To: <categories@mta.ca>
> Sent: Thursday, March 02, 2006 8:32 PM
> Subject: categories: Re: Undirected graph citation
>
>
> >
> > As Clemens Berger reminds us, the category of small categories
> > is a reflective subcategory of simplicial sets, with a reflector that
> > preserves finite products. But as I mentioned, there is a similar
> > "advantage" for the Boolean algebra classifier (=presheaves on non-empty
> > finite cardinals, or "symmetric" simplicial sets):
> > The category of small groupoids is reflective in this topos, with the
> > reflector preserving finite products. Thus the Poincare' groupoid of a
> > simplicial complex is directly available. (The simplicial complexes are
> > merely the objects generated weakly by their points, a relation which
> > defines a cartesian closed reflective subcategory of any topos.)
> >
> > It is not clear how one is to measure the loss or gain of combinatorial
> > information in composing the various singular and realization functors
> > between these different models. Is there such a measure?
> >
> >
> > Bill Lawvere
> >
> > ************************************************************
> > F. William Lawvere
> > Mathematics Department, State University of New York
> > 244 Mathematics Building, Buffalo, N.Y. 14260-2900 USA
> > Tel. 716-645-6284
> > HOMEPAGE:  http://www.acsu.buffalo.edu/~wlawvere
> > ************************************************************
> >
> >
> >
> >
> >
> >
> >
>
>
>
>
>

Re: Undirected graph citation

[George Janelidze]

Dear Bill,

Indeed, there were no monoids in Vaughan's original message of February 28,
but since you have mentioned them in your message of March 1, and since you
were talking there about "...lacuna of explicitness ... in many papers on
Galois theory...", I simply wanted to say that:

I do not see any relevance of these kinds of presentations in Galois theory
(apart from the fact the internal pre-whatever-s in a category X form an
X-valued presheaf category).

On the other hand Galois theory is not the end of the World, and I think the
beauty and importance of those your ideas is clear to everyone who saw them.

Putting myself in risk of making my message boring, I would like to make one
more remark concerning your last message and Galois theory:

You say: "...applying a non-exact functor F to a group..." - true and fine,
but I have actually mentioned F(R) for R being not a group, but another
extreme case of a groupoid, namely an equivalence relation. What seems to be
most amazing is, that, because F preserves not-all-but-some pullbacks, there
are beautiful examples where R is an equivalence relation and F(R) is a
group; in simple words, F creates a group out of nothing! The classical
example, as you know, is: if R is the kernel pair of a universal covering
map E ---> B of a "good" connected topological space B, and F is the functor
sending ("good") topological spaces to the sets of their connected
components, then F(R) is the fundamental group of B. The same thing is true
in other Galois theories of course.

George

----- Original Message -----
From: "F W Lawvere" <wlawvere@buffalo.edu>
To: <categories@mta.ca>
Sent: Sunday, March 05, 2006 3:21 AM
Subject: categories: Re: Undirected graph citation


>
> Dear George,
>
>    Concerning undirected graphs, the Boolean algebra classifier, and
> the intermediate sub-topos that suffices for groupoids:
>
>    The special feature of these toposes I wanted to emphasize is not that
> some of them can be generated by monoids, but rather (whether one splits
> idempotents or not) that the site of operators is itself a full
> subcategory of the category of sets. This is a small part of the point
> that Vaughn wanted to make, I believe. Having the direct visualization of
> this system of operators available as merely maps between certain small
> sets is a useful auxiliary to formal presentations of the d,s kind.
> As you mention, a basic way in which such presheaves can arise is by
> applying a non-exact functor F to a group; the fact that the exponents on
> the group are just these ordinary sets explains why we obtain an object
> in this sort of topos (which can serve as a presentation of another group,
> if desired).
>
>    As noted in my unpublished (but widely distributed) paper on toposes
> generated by codiscrete objects, the Yoneda embedding in these cases
> produces of course a full sub-category of a topos, one which looks
> exactly like (a piece of) the category of sets; of course this is not
> the discrete inclusion, but its dialectical opposite, the codiscrete one.
>
> Bill
> ************************************************************
> F. William Lawvere
> Mathematics Department, State University of New York
> 244 Mathematics Building, Buffalo, N.Y. 14260-2900 USA
> Tel. 716-645-6284
> HOMEPAGE:  http://www.acsu.buffalo.edu/~wlawvere
> ************************************************************
>
>
>
> On Fri, 3 Mar 2006, George Janelidze wrote:
>
> > I am not sure if I really understand what is the target of this
discussion,
> > but I would like to make some comments to Bill's messages:
> >
> > The Poincare' groupoid is (up to an equivalence) nothing but the largest
> > Galois groupoid, and it is directly available as soon as one has what I
call
> > Galois structure in my several papers, if we assume that every object of
the
> > ground category has a universal covering. This is certainly the case for
> > every locally connected topos with coproducts and enough projectives.
> > Therefore this is certainly the case for every presheaf topos. Therefore
> > what Bill means by "directly available" should be not "available without
> > going through geometric realization" but just "can be calculated as the
> > result of reflection" (probably this is exactly what Bill had in mind).
> >
> > Moreover, it was Grothendieck's observation that Galois/fundamental
> > groupoids are to be defined as quotients of certain equivalence
relations -
> > in fact kernel pairs, and this observation was used by many authors in
topos
> > theory and elsewhere; my own observation (1984) then was that one can
make
> > Galois theory purely categorical by using not "quotients" but "images
under
> > a left adjoint" (the first prototype for me was actually not
Grothendieck's
> > but Andy Magid's "componentially locally strongly separable" Galois
theory
> > of commutative rings). What I am trying to conclude is that the
> > Galois/fundamental groupoids actually arise not from anything simplicial
but
> > from abstract category theory: it is just a result of a game with
adjoint
> > functors between categories with pullbacks.
> >
> > In another message Bill says: "A similar lacuna of explicitness occurs
in
> > many papers on Galois theory where pregroupoids are an intermediate step
;
> > the description of  the pregroupoid concept is really just a
presentation
> > of the monoid of endomaps of the 4-element set..." Assuming that
everyone
> > understands that this is not about classical Galois theory (I don't
think
> > somebody like J.-P. Serre ever mentions pregroupoids) and not about what
> > Anders Kock calls pregroupoids, let me again return to the categorical
> > Galois theory:
> >
> > If p : E ---> B is an "extension" in a category C, R its kernel pair,
and F
> > : C ---> X the left adjoint involved in a given Galois theory, then one
> > wants to define the Galois groupoid Gal(E,p) as F(R) = the image of R
under
> > F (I usually write I instead of F, but in an email message this does not
> > look good...). But if our extension p : E ---> B is not normal, then,
since
> > F usually does not preserve pullbacks, F(R) is not a groupoid - it is a
> > weaker structure, the "equational part" of groupoid structure. This
weaker
> > structure is still good enough to define its internal actions in X and
these
> > internal actions classify covering objects over B split by (E,p). Hence
this
> > weaker structure needs a name and I called it "pregroupoid" (I did not
know
> > that this term was already overused for almost the same and for
unrelated
> > concepts). I cannot speak for everyone, but for my own purposes there
are
> > actually several possible candidates for the notion of pregroupoid and
half
> > of them can certainly be defined as monoid actions for a specific
monoid,
> > like the one Bill mentions. However, in each case we deal with a "very
> > small" category actions and it is a triviality to observe that that
category
> > can be replaced with a monoid. Essentially, what you need is to check
that
> > the terminal object (in your category of pregroupoids) has either no
proper
> > subobjects or only one such, which must be initial. In this
observation -
> > due to Max Kelly, about the categories monadic over powers of Sets being
> > monadic over Sets, one usually says "strictly initial"; but we can omit
> > "strictly" here since it is about a topos.
> >
> > George Janelidze
> >
> > ----- Original Message -----
> > From: "F W Lawvere" <wlawvere@buffalo.edu>
> > To: <categories@mta.ca>
> > Sent: Thursday, March 02, 2006 8:32 PM
> > Subject: categories: Re: Undirected graph citation
> >
> >
> > >
> > > As Clemens Berger reminds us, the category of small categories
> > > is a reflective subcategory of simplicial sets, with a reflector that
> > > preserves finite products. But as I mentioned, there is a similar
> > > "advantage" for the Boolean algebra classifier (=presheaves on
non-empty
> > > finite cardinals, or "symmetric" simplicial sets):
> > > The category of small groupoids is reflective in this topos, with the
> > > reflector preserving finite products. Thus the Poincare' groupoid of a
> > > simplicial complex is directly available. (The simplicial complexes
are
> > > merely the objects generated weakly by their points, a relation which
> > > defines a cartesian closed reflective subcategory of any topos.)
> > >
> > > It is not clear how one is to measure the loss or gain of
combinatorial
> > > information in composing the various singular and realization functors
> > > between these different models. Is there such a measure?
> > >
> > >
> > > Bill Lawvere
> > >
> > > ************************************************************
> > > F. William Lawvere
> > > Mathematics Department, State University of New York
> > > 244 Mathematics Building, Buffalo, N.Y. 14260-2900 USA
> > > Tel. 716-645-6284
> > > HOMEPAGE:  http://www.acsu.buffalo.edu/~wlawvere
> > > ************************************************************
> > >
> > >
> > >
> > >
> > >
> > >
> > >
> >
> >
> >
> >
> >
>
>
>
>

Re: Undirected graph citation

[wlawvere]

Dear George

By a presentation in mathematics I mean generators and relations for an
algebraic structure of a certain kind. Occasionally we are fortunate to
have also another more direct description of the same algebra, which it is
useful to make explicit; a well known example of the usefulness of making
explicit such a conceptual (as opposed to syntactical) description is the
pair of definitions for the algebra of operators that defines the notion
of simplicial set.

In your 2001 book with Borceux, Definition 7.2.1 involves five generators
and five relations. Sometimes this is augmented by symmetry.

What is actually being presented ?  a certain full finite subcategory of
the category of finite sets. Why should diagrams of this shape occur so
often and be transported by functors even when they do not satisfy any
exactness ? That is especially evident in the case of the Amitsur complex
on page 264: the family of powers of a given object is a functor of the
exponents, which are sets from that little category.

That groupoids form a subcategory of the topos permits to take images, in
the topos, of maps between groupoids; surprisingly, that can be useful.

I prefer to consider one more finite set, so that "associativity" is a
structure even when it is not an exact property (and analogously in the
case of categories vs truncated simplicial sets - the question is how
truncated). Then to be a groupoid is just a pullback-preservation
condition.

Bill

Quoting George Janelidze <janelg@telkomsa.net>:

> Dear Bill,
>
> Indeed, there were no monoids in Vaughan's original message of
> February 28,
> but since you have mentioned them in your message of March 1, and
> since you
> were talking there about "...lacuna of explicitness ... in many
> papers on
> Galois theory...", I simply wanted to say that:
>
> I do not see any relevance of these kinds of presentations in Galois
> theory
> (apart from the fact the internal pre-whatever-s in a category X form
> an
> X-valued presheaf category).
>
> On the other hand Galois theory is not the end of the World, and I
> think the
> beauty and importance of those your ideas is clear to everyone who
> saw them.
>
> Putting myself in risk of making my message boring, I would like to
> make one
> more remark concerning your last message and Galois theory:
>
> You say: "...applying a non-exact functor F to a group..." - true and
> fine,
> but I have actually mentioned F(R) for R being not a group, but
> another
> extreme case of a groupoid, namely an equivalence relation. What
> seems to be
> most amazing is, that, because F preserves not-all-but-some
> pullbacks, there
> are beautiful examples where R is an equivalence relation and F(R) is
> a
> group; in simple words, F creates a group out of nothing! The
> classical
> example, as you know, is: if R is the kernel pair of a universal
> covering
> map E ---> B of a "good" connected topological space B, and F is the
> functor
> sending ("good") topological spaces to the sets of their connected
> components, then F(R) is the fundamental group of B. The same thing
> is true
> in other Galois theories of course.
>
> George
>

Re: Undirected graph citation

[George Janelidze]

Dear Bill,

> By a presentation in mathematics I mean generators and relations for an
> algebraic structure of a certain kind. Occasionally we are fortunate to
> have also another more direct description of the same algebra, which it is
> useful to make explicit; a well known example of the usefulness of making
> explicit such a conceptual (as opposed to syntactical) description is the
> pair of definitions for the algebra of operators that defines the notion
> of simplicial set.

By a presentation in mathematics I mean exactly the same thing, I agree with
every word you said in this paragraph, and I know that what we call today
Lawvere theories was your beautiful discovery along this lines to thoughts.

> In your 2001 book with Borceux, Definition 7.2.1 involves five generators
> and five relations. Sometimes this is augmented by symmetry.
>
> What is actually being presented ?  a certain full finite subcategory of
> the category of finite sets.

I am sorry, what is "presented" in Definition 7.2.1 can of course be
considered as a subcategory of the category of finite sets, but certainly
not full (because, say, there are no arrows from C_1 to C_2). I suppose you
have noticed this, and so you are suggesting to modify the Definition
7.2.1 - since in "all" examples in fact there are more arrows. Well, one
could do so, but there is also a good reason not to do so: those five
generators and five relations is exactly the minimum needed to define
internal actions (I have actually first used this definition in my CT90
paper "Precategories and Galois theory" and many other people used similar
definitions for other purposes, probably long before).

Having said this, I again agree with every word of the rest of your message.
Can you accept the fact I agree with it and at the same time I do like
Definition 7.2.1? Note that if we go one step down in dimension, there will
be reflexive graphs whose "theory" is a full subcategory of sets and just
graphs whose "theory" is not. Are you telling me that this is a good reason
to forget the notion of graph, and use only reflexive graphs?

George

----- Original Message -----
From: <wlawvere@buffalo.edu>
To: <categories@mta.ca>
Sent: Monday, March 06, 2006 10:08 PM
Subject: categories: Re: Undirected graph citation


>
> Dear George
>
> By a presentation in mathematics I mean generators and relations for an
> algebraic structure of a certain kind. Occasionally we are fortunate to
> have also another more direct description of the same algebra, which it is
> useful to make explicit; a well known example of the usefulness of making
> explicit such a conceptual (as opposed to syntactical) description is the
> pair of definitions for the algebra of operators that defines the notion
> of simplicial set.
>
> In your 2001 book with Borceux, Definition 7.2.1 involves five generators
> and five relations. Sometimes this is augmented by symmetry.
>
> What is actually being presented ?  a certain full finite subcategory of
> the category of finite sets. Why should diagrams of this shape occur so
> often and be transported by functors even when they do not satisfy any
> exactness ? That is especially evident in the case of the Amitsur complex
> on page 264: the family of powers of a given object is a functor of the
> exponents, which are sets from that little category.
>
> That groupoids form a subcategory of the topos permits to take images, in
> the topos, of maps between groupoids; surprisingly, that can be useful.
>
> I prefer to consider one more finite set, so that "associativity" is a
> structure even when it is not an exact property (and analogously in the
> case of categories vs truncated simplicial sets - the question is how
> truncated). Then to be a groupoid is just a pullback-preservation
> condition.
>
> Bill
>

Re: Undirected graph citation

[Vaughan Pratt]

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

Re: Undirected graph citation

[Marco Grandis]

Undirected versus directed

Going along with the last messages of C Berger and FW Lawvere, I
would like to list the following parallel notions, undirected versus
directed. Of course, it is not a question of saying which is better,
but only of separating them to make things clearer.

---

Undirected:

- symmetric simplicial sets (sss)
- simplicial complexes (classical)
= sets with distinguished subsets
= sss where each simplex is determined by its vertices
- undirected graphs
- groupoids (fundamental groupoids)
- abelian groups (homology groups)
- spaces
- classical metric spaces
- undirected algebraic topology
---

Directed:

- simplicial sets
- "directed simplicial complexes" (not classical)
= sets with distinguished words
= simplicial sets where each simplex is determined by (the family of)
its vertices
- directed graphs
- categories (fundamental categories)
- preordered abelian groups ("directed homology groups")
- "directed spaces" (preordered, locally preordered, etc.)
- generalised metric spaces (Lawvere)
- "directed algebraic topology"
---

Spaces are plainly an undirected structure. Note that their singular
simplicial set already has a natural symmetric structure (by
"permuting vertices" on tetrahedra); there is no need of symmetrising
it and loosing information.

Classical algebraic topology is mostly undirected (since spaces,
groupoids, abelian groups are so), but it has also used directed
structures, like simplicial sets, for undirected purposes: simulating
spaces and computing undirected algebraic structures, like groupoids
and homology groups.
The study of "directed algebraic topology" is quite recent. (There
are some papers on that in my web page, from which one can see the
literature; present applications are concerned with concurrency and
rewriting. But the general aim should be modeling non-reversible
phenomena.)

Finally, I would like to point out - once more - that the term
"simplicial complex" is highly confusing: this notion (as Bill
recalls) is a simplified version of a symmetric simplicial set, while
the corresponding simplified version of a simplicial set is a "set
with distinguished words" (the reflexive cartesian closed subcategory
of "objects determined by their vertices", in the presheaf topos of
simplicial sets). But I have noticed that people can get nervous
about terminology, and it might be better to forget about this last
point.

Marco Grandis

Re: Undirected graph citation

[Dr. Cyrus F Nourani]

Hmmm, a paper entitled Funcotrial Generic Filters was written
July 2005, abstract to ASL, where you can observe ejecting on 
initial segments towards models. What it might do on preshaeves
was sent to a conference a month ago. Like I had told the list there 
were papers I published over several years ago on functors computing models
on Hasse diagrams.  
I'm not in a position to escalate and have to keep you on a holding
as to what it was doing on sheaves. On the surface it appears as if
we are living in parallel worlds getting a message through. 
Cyrus

> ----- Original Message -----
> From: "Vaughan Pratt" <pratt@cs.stanford.edu>
> To: categories@mta.ca
> Subject: categories: Re: Undirected graph citation
> Date: Mon, 06 Mar 2006 20:43:29 -0800
> 
> 
> 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

etc, etc...