we need to demonstrate an isomorphism .

This can't exist. There is a canonical functor the other way round: . But it is not an isomorphism (and not an equivalence) in general:

the category is the category whose objects are those of , and whose morphisms are words of composable morphisms in . Composition in is just concatenation of such words.

Now, every such word in composable morphisms can be evaluated to one single morphism in : we we just take all the morphisms in the word and form their composite using the composition rule provided with . This assignment is easily seen to be a functor from to . This functor is called the *counit of the adjunction* . Of the adjunction that we are wanting to establish.

To get that, we should try to explitly say what it is that a functor does. Say out in words which data you have to specify in order to describe such a functor to me.

Here is a hint: the functor needs to send every morphism in to a morphism in , such that this respects composition. The morphisms in are words of consecutive edges in the graph . Their composition operation is just the concatenation of words.

So in particular there are the words of length 1, and the functor needs to send each of them to some morphism in . Suppose this assignment of a morphism in for each morphism in that is a word of length 1 is given. What other information is there needed in order to specify a functor , i.e. in order to specify what it does to words of legnth greater than 1 ? Is there any further information needed? Can we use the functoriality of (the fact that it respects composition) in order to deduce what it does to words of length greater than 1?

The answer is yes. Do you see how this works?

So from this reasoning we find that specifying a functor is the same thing as giving a map of sets and a map of sets that matches the previous assignment on source and target objects. And nothing else. By functoriality of alone it follows that this fixes what does on all morphisms of .

But what we just specified is manifestly nothing but a map of graphs .

So functors encode precisely the same informaton as morphisms of graphs .

This is the adjunction isomorphism. We may write it as a bijecton of sets

.

Do you see what I mean?

(In fact to establish an adjunction we also need to check that this bijection is "natural". But let's not worry about that for the time being.)

]]>In the other thread, you phrased the question in a nice digestible way (for me):

given a functor , which graph morphism do you send it to? And how do you go the other way round?

The graph morphism we send to would be

To go back the other way, the obvious thing to try would be

Although I mistakenly wrote equals (which it doesn't) above, the other expression was correct, i.e. it is true that

Therefore, going back the other way, we have a morphism

which is not exactly what we started with, but close.

So to finish the exercise, we need to demonstrate an isomorphism

It seems obvious, i.e. there are corresponding objects and morphisms, but my time has expired for the moment...

]]>The best you are going to get with is , and at worst, you won't get a functor at all.

]]>Thanks Urs and sorry for the detour. I was confused about . Now I'm not. I'll do some work offline to iron out what I mean by , but that is not important for the current exercise you've re-focused things on. I'm headed for a train now (and another intense day), so attention will be sporadic for a while...

]]>Note to Urs: Please please know that I understand U is a functor. I even know it is the RIGHT functor. I knew that when I wrote my comment above last night, so please, with that in mind, have another look at what I wrote. I do think it is interesting.

I am looking. But now where are we? So we understand the functor now. What we are after is understanding that for any category and any graph, functors

are in bijection with graph morphisms

.

Do you see how this works?

]]>Eric,

you defined as follows:

Let me denote to be a map (I won't call it a functor, because the answer to my question may lay in the fact that U_{max} may not be a functor) that given a category produces the smallest directed graph such that .

I think this definition makes them the same. The free category functor is injective on objects: if two graphs are different, then their free categories are different.

The two concrete examples of graphs you call and in your latest comment are not equal. But they are also not isomorphic.

I am not sure what is needed for!

Another thing: above you write

Here is still the free category functor? Then is the graph whose edges are words in the morphisms of . But is the graph whose edges are just the morphisms in . The former is much bigger.

]]>The reason that I provided a proof was to give you an example of what a proof of functoriality entails. Then Urs posted his version of the proof because my version wasn't very clear.

Still, you're missing the point. This case is very confusing because you're talking about *the functor* U, and the "functors", i.e. the 1-cells in the 1-category of small 1-categories. The problem with what you're doing is that you're trying to give a morphism between a category and a graph, which is strictly not something that can be done. What you have to prove is precisely that your functor U_max commutes with composition and sends identities to identities. The internal structure other category has remarkably little to do with the actual problem.

Too bad! I actually spent a lot of time thinking last night to demonstrate that I'm trying (even though I was exhausted). I lost a lot of sleep because of it. I was very happy with what I came up with, so I am kind of sad that there was no "Good job" or "That is interesting". All I got was "You're being willfully ignorant here."

Harry answered my question about what the underlying graph should be. There were two options, he told me the correct one. I accepted it happily. His answer agreed with what David said and is double confirmed by Urs. The "correct" forgetful functor is the one that keeps all composite edges. Fine.

THIS IS A FUNCTOR. OBVIOUSLY! I never said it was not a functor. Ever.

I had a different functor in mind, but that is fine as long as I understand everything.

as far as I understand what you wrote, in fact is the same as .

Argh. No. Here is a concrete example. Given a category with three objects and 3 non-identity morphism , , and (as above)

[Note: I'll address David's super helpful (as always) comments about groupoids a little later.]

is the directed graph consisting of three nodes and THREE (non self-looping) edges corresponding to the non-identity morphisms and three self-loops corresponding to the identities (per David's comment above).

is the directed graph consisting of three nodes and only TWO (non self-looping) edges corresponding to the non-composite non-identity edges. It does not contain an edge corresponding to the morphism .

has three (non self-looping) edges. has two (non self-looping) edges. How can they be the same????

I then proceeded to construct a[n] (what I thought was a very neat) endofunctor on . I used the fact the was a functor and was a functor to prove that is also a functor. I didn't follow Harry's suggestion and prove it was a functor by showing it preserves compositions and identities, but so what? If and both and are functors, then is obviously a functor.

Of course is a functor. I would not say otherwise or I'd be accusing everyone here AND MacLane AND Pratt and Harry's professor of being wrong. That would be "willfully ignorant". But I never did that.

I had a misunderstanding of what was. That misunderstanding was cleared up. I defined a new forgetful functor , but that doesn't imply anything about .

Later, I even used the fact that was a functor AND even that is its adjoint functor to construct an adjoint to .

Now if by

as far as I understand what you wrote, in fact is the same as .

you meant "equivalent", then that is true in the sense that there is an isomorphism for any category , but even though two directed graphs, each having different number of edges, can be mapped to each other in a reversible matter, I'd still (from a graph theory perspective) consider them different objects if they had different numbers of edges.

Regarding David's comment...

Good point! Thank you :)

You are right. For to be defined unambiguously, its domain must be restricted to somehow "causal" categories. Maybe generalized direct category or generalized Reedy category or something. Basically, to categories without non-trivial loops. This excludes groupoids as you pointed out.

But this is not as bad as it sounds at first. As I was trying to describe recently, a groupoid can always be "extruded" to a "causal" category (yet to be defined, but is probably one of the two: direct or Reedy). is unambiguously defined on "categories with direction" and I hope to prove some day that any category can be extruded to a category with direction. At the moment, most terms in that statement are yet to be defined. It is one of my homework assignments.

So my conclusion from this is that is the right functor. may or may not be interesting, so we can forget about it. Most important, I have learned something.

Note to Urs: Please please know that I understand is a functor. I even know it is the RIGHT functor. I knew that when I wrote my comment above last night, so please, with that in mind, have another look at what I wrote. I do think it is interesting.

]]>in trying to construct some 'minimal quiver' of which a category is a path category on, you will, run into trouble. Given a groupoid with 3 objects a,b,c, all of which are uniquely isomorphic (so we have arrows a -> b, b -> c, a -> c, b -> a, c -> b, c -> a plus identity arrows, such that what we have here are inverses of each other) how do we pick, *in a systematic way* (or natural way) the arrows which supposedly form this minimal quiver? And so on for all other finite groupoids, all other finite categories and so on to all small categories.

If you have a (deloopong of a) monoid, i.e. a category with one object, then sending it to the underlying graph forgets two things: which arrows are composites of other arrows, and which arrow was the identity. So the underlying graph functor cannot remember the identity arrow to throw it out. So when above you said

>What David said (if I understood correctly, which is always a big "if") seemed to indicate the correct choice is 1.) , whereas I always thought it should be 2.)

actually it's neither, as you need to include the identity arrows as well (recall I said there should be six edges in the underlying directed graph of your category.

You do need to be careful about making statements like 'such and such is a functor from Cat to DiGrph', based on the consideration of a single specialised example at the extreme end of a spectrum. Other extreme examples, like the monoid above, or the groupoid need to be considered. It's all very well and good considering something that we know to be the free category on a finite directed graph (of a simple sort) and, by hand and outside the rules of the game, reconstructing the graph. But not all categories are of this form, and not even categories of this form plus some conditions (c.f. the monoid above).

Using the axiom of choice you can construct a map Ob(Cat) -> Ob(DiGrph) of the sort you describe, but you *cannot* make all the choices and still respect the algebraic structure (i.e. the arrows) of Cat and DiGrph. This latter point is the most important. Categories are algebraic structures, and you need all constructions to work with the maps between them. ]]>

I'm trying to fight the temptation of asking "why" the forgetful functor can't forget the maximum amount of information...

A category is a directed graph with the extra information of how to compose morphisms. Therefore we want to speak of the forgetful functor that forgets precisely this extra information.

but note that

as far as I understand what you wrote, in fact is the same as .

What Harry says above is correct. For a category with set of objects and set of morphisms and maps that send each morphisms to its source and target object, and with some composition operation, the underlying directed graph is precisely this data, but forgetting that there is a composition operation.

So the set of vertices of is the set and the set of edges of is and the maps that send each edge to its source and target are and , respectievly.

For a functor between categories, which is given by some maps of objects and some maps of morphisms the value of the functor on is the morphism of graphs that has precisely the same action, now regarded as a map between sets of vertices and edges of graphs.

One can see easily that for and two functors, i.e. two morphisms in the category of categories, we have the relation

between morphisms of directed graphs. So is indeed a functor.

Okay?

]]>You never addressed my comment about morphisms. Are you familiar with what the morphisms are in the 1-category of small 1-categories are?

To be clear, you need to show that the "functor" you're defining commutes with composition of functors and sends identities to identities as well. In this case, Hom(C,D) is the *set* of functors between C and D.

Basically your definitions are broken and don't make any sense.

The way that the standard definition of this forgetful functor actually works is as follows:

For any category C in (1-Cat of small 1-Cats)

Let C_0=Ob(C) is a set of points. For every element of Hom(X,Y), give an edge from the point X to the point Y.

This pair U(C):=(C_0, C_1) defines a quiver.

Then to show that this is functorial: Given a functor C->D, U(C->D) gives a morphism of graphs because functors send objects to objects and hom sets to hom sets, so applying the construction, this gives us a well-defined map of quivers.

U(Id_C) is obviously the map that we want, since it is the identity on points and edges.

U(G o F) commutes with composition again for the obvious reason (functors map objects to objects and arrows to arrows, so this gives us morphisms of graphs that do the same thing).

Do you see what I've just done? I've described the behavior of morphisms (functors in this case) under the action of the functor.

You're being willfully ignorant here. The definition of a functor is a *good* one (modulo strictness and constructibility concerns, which are *irrelevant*.)

The above calculation also answered my follow up question, 'What is the left adjoint of ?"

SInce

we can apply to the left to get

Similarly,

Pre-composing on the right, we get

If I'm not mistaken, the above two facts imply that is the left adjoint of .

]]>I specialize in hand waving, but here is my best attempt at an actual proof...

The objects of can be partitioned into three disjoint sets:

[Edit: This partition is not 100% correct as stated. It needs some work, but the basic idea should remain. This issue is pointed out In a comment below from David. We need to take care of digraphs having non-trivial loops, but that can be sorted out, so in what follows, consider it to be restricted to "digraphs without non-trivial loops".]

is a full subcategory of consisting of those digraphs for which all composite edges are included, i.e. if and are directed edges, then is also a directed edge.

is a full subcategory of consisting of those digraphs that contain no composite edges, i.e. if and are directed edges, then is NOT a directed edge.

is a full subcategory of consisting of all other digraphs, i.e. the ones that are neither full or minimal.

Given any full digraph, we can obtain a minimal digraph by removing all composite edges. Conversely, given any minimal digraph, we can obtain a full digraph by adding all composite edges. This process is reversible.

Let be an endofunctor on defned by (evil alert!)

- For any , is the corresponding minimal digraph
- For any , is the corresponding full digraph
- For any ,

and it does the obvious thing to morphisms.

A neat thing about this is the endofunctor squares to an identity functor and we have

and

From here, it is obvious (even to me) that is a functor since both and are functors.

]]>Functors must preserve morphisms and commute with composition. You have not shown this, therefore all that you've done is map a category to a graph. This is not valid, and it means that you are still misunderstanding the notion of a functor.

@Harry: I have shown that for any category that and are isomorphic. I believe this is enough to conclude that is indeed a functor. It is kind of cool.

]]>@Harry: In these notes, what he calls is the same as what we call . However, a diagram scheme (or directed graph) does not necessarily include all composite edges. For example, if , then it is not necessary that is in . Therefore, generally speaking, is not necessarily a category as described. To make sure that is a category, we need to associate a morphism to each and then ALSO add morphisms to fill in the missing composites. Unless I'm overlooking something, this last step appears to be missing from the notes.

Edit: I didn't see your comment above before writing this, so responded below.

]]>Functors must preserve morphisms and commute with composition. You have not shown this, therefore all that you've done is map a category to a graph. This is not valid, and it means that you are still misunderstanding the notion of a functor.

]]>The devil on my left shoulder tells me to ask. The angel on my right shoulder tells me to forget it. Unfortunately, the devil almost always wins.

Let me denote to be a map (I won't call it a functor, because the answer to my question may lay in the fact that may not be a functor)

that given a category produces the smallest directed graph such that

where is the usual forgetful functor.

Is a functor?

Edit: Light bulb. I'm going to go out on a limb and assume is a functor, but note that for any category because there is an isomorphism between the "smallest" and the "fullest" graphs. For example, starting with the "fullest" graph, we can forget all composites to get the "smallest" graph. We can exactly recover the "fullest" graph from the "smallest" graph by inserting all composites.

Edit^2: Now that that is cleared up, I really can move on. Yay!

]]>Remember that that functor is not a functor from some given category to a graph, but rather a functor from the 1-category of categories to graphs. It sends each category . Note the arrow that I've used here.

]]>I'm trying to fight the temptation of asking "why" the forgetful functor can't forget the maximum amount of information...

I will hold off on that one for another time and just accept that the forgetful functor is the "stupid" one for now.

PS: Thanks again for the notes Harry. These are good. When I started reading them the first time, I got scared pretty quickly. On second glance, I might have given up too easily.

]]>Thanks Harry. Yeah, I am looking for the notes you gave me. My filing system is not great :o It should be here somewhere... Edit: Found it!

]]>No, the underlying (read: forgetful) graph is just if you do the stupid thing and turn all of your objects into vertices and if you turn all of your morphims into directed paths.

Similarly, the free category is if you do the stupid thing again and just generate a catgory from a graph by composing by concatenation and letting the concatenation of no paths at an object be the identity.

This is also in those notes I sent you.

]]>You wouldn't know it by the quantity of posts, but in the weeks we've been talking about this, if you sum up all the time I have been able to actually *think* about it, it probably adds up to about 30 minutes :)

I've always been a pretty hard worker, but the new life in HK is tough. I'm sitting down now after a **very intense** 14 hour day at work. This place being my only solace for distractions.

David mentioned something in that other thread about underlying graphs that illustrated an extra degree of confusion on my part. Given a category with 3 objects , , and and three non-identity morphisms , and , what is its underlying graph? There are two options I can think of:

- , , and , or
- and

What David said (if I understood correctly, which is always a big "if") seemed to indicate the correct choice is 1.) , whereas I always thought it should be 2.). I always thought should be the "smallest" graph such that you can recover (or something "equivalent" in some way) when constructing the quiver . I figured you wouldn't need the directed edge in because this comes for free when you construct the quiver of the TWO directed edges and .

Basically, two different directed graphs can have the same quiver, so which one should you take as the underlying one? The "full one" (including all composite edges) or the "smallest" one (containing only non-composite edges)?

I should probably try to clear that up before moving on. Which is it? Is in ?

Thank you very much for all your help.

]]>I e-mailed him exercises as well. This is in fact a problem from that packet (Show that Pa: Dia -> Cat is left adjoint to U: Cat -> Dia).

Where Pa denotes the path category i.e. the free category, and U denotes the forgetful functor.)

Dia is the category of Diagram schemes (i.e. quivers, i.e. oriented graphs).

]]>