Free category on a graph
bhal...@my-dejanews.com
I am reading book on category theory. I think it Walters' book. In first
chapter "I. The Algebra of Functions" is discussion of "The free ctaegory
on a graph" I have question. The category that is generated from a graph, is
this graph a result of applying reflexive closure operator and transitive
closure operator to the graph??? cat = Trans (Reflex (graph))??
Also what role do closure operators play in category theory???
Thank you.
Regards,
Vasili N. Galchin
-----------== Posted via Deja News, The Discussion Network ==----------
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
Levent Erkok
> I am reading book on category theory. I think it Walters' book. In first
> chapter "I. The Algebra of Functions" is discussion of "The free ctaegory
> on a graph" I have question.
If you keep on reading Walter's book (pg. 13) it says:
Given a graph G, and no given relations, we can form a category generated
by G called the free category on G.
The objects of the free category are the same as those of G. Arrows from
object A to object B are paths of arrows from A to B with domains and
codomains matching up, .... Composition is concatenation of paths; the
identities are the empty paths.
So, if there is a path from node A to B (of any length) it corresponds to an
arrow in the category. In this sense your observation of:
> The category that is generated from a graph, is
> this graph a result of applying reflexive closure operator and transitive
> closure operator to the graph??? cat = Trans (Reflex (graph))??
is almost correct, but might be worded more carefully to avoid confusion
as follows: Let the original graph be G=(V, E) where V is the set of nodes
and E is a subset of V*V. Then the corresponding category will have V as
its objects. Then you construct the reflexive and transitive closure of E
(as you suggested), call it E*. Then, for each pair (n1, n2) in this extended
relation E*, you put an arrow from n1 to n2 in the category. This will
completely define the corresponding category. (Example 18 on pg. 13 gives
a nice example..)
> Also what role do closure operators play in category theory???
I think the question is quite ambiguous. If you can be more specific, I'm
sure somebody will give us more insight about that.
-Levent.
john baez
<bhal...@my-dejanews.com> wrote:
> I am reading book on category theory. I think it Walters' book. In first
>chapter "I. The Algebra of Functions" is discussion of "The free category
>on a graph" I have question. The category that is generated from a graph, is
>this graph a result of applying reflexive closure operator and transitive
>closure operator to the graph??? cat = Trans (Reflex (graph))??
That sounds right if I understand what you mean. A category theorist
would say it more elegantly as follows: there's a forgetful functor
from the category of categories to the category of graphs, and the
left adjoint of this sends each graph to the free category on that graph.
But if you don't like adjoint functors, you may prefer an explicit
construction along the lines you mention.
Of course there are different definitions of "graph", and one needs to
use the right one to get this business to work smoothly. Namely, we
define a graph to be a collection of vertices, together with, for each
pair of vertices (x,y), a collection of edges from x to y. Then a
category is just a graph with extra structure and properties, so there's
a forgetful functor taking categories to their underlying graphs.
(I say "collection" rather than "set" above to avoid nitpicky issues
about large vs. small categories.)
Wim van Gessel
ba...@galaxy.ucr.edu (john baez) wrote:
#In article <757hii$m4h$1...@nnrp1.dejanews.com>,
# <bhal...@my-dejanews.com> wrote:
#
#> I am reading book on category theory. I think it Walters' book. In first
#>chapter "I. The Algebra of Functions" is discussion of "The free category
#>on a graph" I have question. The category that is generated from a graph, is
#>this graph a result of applying reflexive closure operator and transitive
#>closure operator to the graph??? cat = Trans (Reflex (graph))??
#
#That sounds right if I understand what you mean. A category theorist
#would say it more elegantly as follows: there's a forgetful functor
#from the category of categories to the category of graphs, and the
#left adjoint of this sends each graph to the free category on that graph.
#But if you don't like adjoint functors, you may prefer an explicit
#construction along the lines you mention.
#
#Of course there are different definitions of "graph", and one needs to
#use the right one to get this business to work smoothly. Namely, we
#define a graph to be a collection of vertices, together with, for each
#pair of vertices (x,y), a collection of edges from x to y. Then a
#category is just a graph with extra structure and properties, so there's
#a forgetful functor taking categories to their underlying graphs.
#
#(I say "collection" rather than "set" above to avoid nitpicky issues
#about large vs. small categories.)
#
There is a different approach, which allows you to find out what is the
"natural" notion of a graph in this situation. I am not sure whether it
appears anywhere in the literature; if it does, please forgive my
ignorance, or else consider it as a Xmas gift.
Consider the forgetful functor from "the" category of categories to "the"
category of sets, which for any category just gives its set of arrows.
This functor has a left adjoint, which for any set constructs a category
of disconnected arrows, each with identity arrows at both ends.
The right adjoint reflects isomorphisms, which implies that the adjunction
can be decomposed as a "tower" of monads, which in this case is
really quite short.
The adjunction induces a monad on the category of sets, which corresponds
to a very simple algebraic theory, as follows:
there are two unary operations, d() and c(), satisfying the identities
c(c(X)) = d(c(X)) = c(X) ; c(d(X)) = d(d(X)) = d(X) for any X
Here c() and d() are of course interpreted as codomain resp. domain.
Let's call this theory the theory of diagram schemes. Since it uses
only unary operators, it can also be described simply as a monoid, and
a model of the theory (i.e. a diagram scheme) as an "action" of the
monoid. The resulting category of monoid actions is always a topos,
and it turns out to be one of the simplest cases of a non-Boolean topos.
Now the original adjunction between sets and categories factors through
this topos of diagram schemes -- voila!
__
Wim van Gessel
john baez
Wim van Gessel <wvge...@xs4all.nl> wrote:
>The right adjoint reflects isomorphisms, which implies that the adjunction
>can be decomposed as a "tower" of monads, which in this case is
>really quite short.
What's the theorem you're hinting at here? Any functor that's a right
adjoint and reflects isomorphisms is a composite of some number of
monadic functors? How many does one need, at most? This is interesting
to me because my friend James Dolan once caught an error in a book which
said that a composite of monadic functors was always monadic.
Wim van Gessel
ba...@galaxy.ucr.edu (john baez) wrote:
#In article <75fsq4$dgt$4...@news2.xs4all.nl>,
#Wim van Gessel <wvge...@xs4all.nl> wrote:
#
#>The right adjoint reflects isomorphisms, which implies that the adjunction
#>can be decomposed as a "tower" of monads, which in this case is
#>really quite short.
#
#What's the theorem you're hinting at here? Any functor that's a right
#adjoint and reflects isomorphisms is a composite of some number of
#monadic functors? How many does one need, at most? This is interesting
#to me because my friend James Dolan once caught an error in a book which
#said that a composite of monadic functors was always monadic.
I hope some specialist can come to my rescue, because I am not in a
position to tell what has been published about this type of question.
I'll try to give some tentative, partial answers though.
I do know that the notion of a 'tower of monads' appears in the literature;
I didn't invent the phrase. I am also pretty sure that in general one
has to consider towers up to any ordinal.
Also, one has to make assumptions about the presence of enough limits and
colimits in both categories.
In the situations that are more or less familiar to me the categories
concerned are categories of partial algebraic structures with finitary
operations, having at least finite limits and colimits for countable
diagrams, and one may assume that 'all' functors involved in relevant
constructions will preserve filtered colimits; such sweeping statements
can be obtained using finiteness conditions, directly or translated
into topological language.
Given a functor G : Y --> X with left adjoint F : X --> Y , the first
step in the construction is the definition of the monad induced by an
adjunction, its category of algebras A , and a functor G' : Y --> A
which is really the same thing as G . This is standard.
The next step is the construction of a left adjoint for G' ; at that
point one may invoke some abstract existence principle, but in the
situations indicated above there is usually an explicit construction
available which depends on the colimit constructions of the base
category X ; also, colimit constructions for the new category can be
obtained. The construction can then be repeated. Infinite stages can
be constructed using sequence diagrams as objects.
The construction fails to give anything new when the induced monad is an
equivalence, i.e. if the right adjoint is a reflection functor, up to
equivalence of categories. When that happens, and the original right
adjoint functor reflects isos (sorry for the double meaning of
'reflect') it is easy to check that the last constructed adjunction is
an equivalence, so we have essentially decomposed the original
adjunction; in the other case there is a residual
reflection/coreflection pair that cannot be resolved.
In the other direction, a right adjoint of a monadic functor must
clearly reflect isos, and this property is preserved if such functors
are composed.
This explains why the condition that the right adjoint must reflect isos
is essential.
Now the question remains (among many others of course): under what
conditions can we be sure that the sequence of monads comes to an end?
In the cases indicated above this is actually so, and indeed we never
have to go beyond the first limit ordinal. This depends essentially on
the condition that filtered colimits are preserved.
To see that finite sequences of monads are in general not enough we
can use generalized algebraic theories; these can be given by a
family of function symbols (finitary, of course) and a set of axioms
in the form of simple Horn clauses, like
P0 & ... & Pn => C where each premiss and conclusion is either an
equation or has the form X! i.e. 'X exists' or 'X is well-defined' .
Forgetful functors give the set of elements X for which X! holds, and
their left adjoints are given by interpreting the set of Horn clauses
as an inductive closure operator. The originator of this thread already
indicated that.
It is not too hard to get cases of infinite depth this way.
__
Wim van Gessel
bhal...@hotmail.com
Levent Erkok <er...@church.cse.ogi.edu> wrote:
> In comp.lang.functional bhal...@my-dejanews.com wrote:
> > I am reading book on category theory. I think it Walters' book. In first
> > on a graph" I have question.
>
>
> Given a graph G, and no given relations, we can form a category generated
> by G called the free category on G.
>
> The objects of the free category are the same as those of G. Arrows from
> object A to object B are paths of arrows from A to B with domains and
> codomains matching up, .... Composition is concatenation of paths; the
> identities are the empty paths.
>
> So, if there is a path from node A to B (of any length) it corresponds to an
> arrow in the category. In this sense your observation of:
>
>
> as follows: Let the original graph be G=(V, E) where V is the set of nodes
> and E is a subset of V*V. Then the corresponding category will have V as
> its objects. Then you construct the reflexive and transitive closure of E
> (as you suggested), call it E*. Then, for each pair (n1, n2) in this extended
> relation E*, you put an arrow from n1 to n2 in the category. This will
> completely define the corresponding category. (Example 18 on pg. 13 gives
> a nice example..)
>
> > Also what role do closure operators play in category theory???
>
> I think the question is quite ambiguous. If you can be more specific, I'm
> sure somebody will give us more insight about that.
proto-category. If you perform closure you get a category. Also it seems
a graph homomorphism is a proto-functor. Perform a closure on this and you
get a category functor!!!???
Vasili
>
> -Levent.
Dan Christensen
<er...@church.cse.ogi.edu> wrote:
> Let the original graph be G=(V, E) where V is the set of nodes and E
> is a subset of V*V. Then the corresponding category will have V as
> its objects. Then you construct the reflexive and transitive closure
> of E (as you suggested), call it E*. Then, for each pair (n1, n2) in
> this extended relation E*, you put an arrow from n1 to n2 in the
> category. This will completely define the corresponding
> category. (Example 18 on pg. 13 gives a nice example..)
This is incorrect. For example, if the graph looks like
A--->B
| |
| |
v v
C--->D
then the free category will have two morphisms from A to D, and thus
will not be the category of any graph. Similar problems occur if
there are loops in the graph, e.g. if you reverse the arrows from
A to C and C to D above.
Dan
--
Dan Christensen
j...@math.jhu.edu
Levent Erkok
Well, I think I'm confused now. Referring to Walters' book again, on page 13,
(example 18) he gives a graph, which has a lot of loops in it and then
goes ahead and describes the free category on it, just the way described
earlier, which you said to be incorrect. May be you can look at that book
and tell me where I misunderstand the process.
-Levent.
PS. The book mentioned is: "Categories and Computer Science", R. F. C. Walters,
Cambridge University Press, 1991. ISBN: 0-521-42226-4.
Levent Erkok
> In comp.lang.functional Dan Christensen <j...@sunset.ma.huji.ac.il> wrote:
> > In discussing the free category on a graph, Levent Erkok
> > <er...@church.cse.ogi.edu> wrote:
> > This is incorrect. For example, if the graph looks like
> > A--->B
> > | |
> > | |
> > v v
> > C--->D
> > then the free category will have two morphisms from A to D, and thus
> > will not be the category of any graph. Similar problems occur if
> > there are loops in the graph, e.g. if you reverse the arrows from
> > A to C and C to D above.
> Well, I think I'm confused now. Referring to Walters' book again, on page 13,
> (example 18) he gives a graph, which has a lot of loops in it and then
> goes ahead and describes the free category on it, just the way described
> earlier, which you said to be incorrect. May be you can look at that book
> and tell me where I misunderstand the process.
OK, the confusion is cleared now, by Timothy Chow (thanks..). What the
book said was to put an arrow for each path in the graph. Of course, when
I said transitive closure, it didn't exactly correspond to what the
book described (if there are n paths between two nodes, each should get
an arrow in the category) but transitive closure doesn't exactly mean that.
So, it was my mistake. Thanks for pointing it out.
-Levent.
Dan Christensen
> OK, the confusion is cleared now, by Timothy Chow (thanks..).
Good, and sorry for not explaining myself fully. Tim was right when
he wrote:
> Dan's clause "and thus will not be the category of any graph" I
> think is mistyped.
I meant something like "and thus the underlying graph of the category
will not be a simple graph, ie. a graph in which there is at most one
edge (in each direction) between any two vertices". But that was more
of an aside, the main point being that the transitive closure
description Levent gave was not quite right.