Indiscrete objects in a functor category

Indiscrete objects in a functor category

[Aleks Kissinger]

It's common to describe the category of (directed, multi-) graphs as a
functor category Graph := [2, Set], where 2 here is the category with
2 objects and 2 parallel arrows (s & t).

For a pair of sets (V,E), one can construct the indiscrete graph
I(V,E) as a graph with vertices V and edges E x V x V, where the
source and target maps are just the 2nd and 3rd projection
respectively. This gives a right adjoint to the forgetful functor from
Graph to pairs of sets. This enables one to construct a category of
graphs with a fixed set of vetex/edge labels as a slice over Graph:

Graph / I(Lv, Le)

since a graph hm G --> I(Lv,Le) is the same as a map U(G) --> (Lv,Le),
which is just a pair of functions assigning labels to the vertices and
edges of G.


This seems to me like a pretty standard trick, which extends to any
functor category from a C which is in some sense "suitably acyclic".
For instance, consider a category of "partitioned graphs" [3, Set],
where 3 has objects (P,V,E) and arrows:

E --s--> V, E --t--> V, and V --p--> P

where, p assigns each of the vertices a partition. For a triple
(P,V,E) we can form the indiscrete partitioned graph with:

- partitions P
- vertices V x P
- edges E x (V x P) x (V x P)
- p = pi2, s = pi2, t = pi3

which gives a right-adjoint to the forgetful functor from partitioned
graphs to triples of sets. This is clearly an instance of a general
recipe, whereby you start with the objects with no arrows out, and
work your way backwards, always adding copies of the codomain of every
out-arrow. Again one can attach labels to partitioned graphs by
slicing:

[3,Set] / I(Lp,Lv,Le)


So, my question: Is the general case a known/studied construction? If
so, could someone provide a reference?



Best,

Aleks


[For admin and other information see: http://www.mta.ca/~cat-dist/ ]

Re: Indiscrete objects in a functor category

[Aleks Kissinger]

Yes, indiscrete isn't exactly right. Perhaps something like
"saturated" is more appropriate.

Right Kan extensions give a nice way to put this, which makes it clear
that this extends beyond finite base category as well. So, the
refinement of my question is: have people studied (left or) right Kan
extensions over the inclusion into C of its associated discrete
category C0?

It seems to me for instance that taking C = the simplicial category
and C0 = natural numbers would have been studied, e.g. in forming
something like "coloured simplicial sets" as a slice.

On 20 December 2015 at 03:28, Steve Lack <steve.lack@mq.edu.au> wrote:
> Dear Aleks,
>
> I would say that the known construction of which this is a special case is
> right Kan extensions. The forgetful functor from graphs to pairs of sets is
> given by restriction along the inclusion in what you call 2 of the subcategory
> with the same object but no non-identity arrows. Thus the right adjoint is given
> by right Kan extension along this inclusion. Such right Kan extensions can always
> be constructed using limits; in your case, because the domain of the functor along
> which you are extending is discrete, these limits are actually products.
>
> By the way, I would not use “indiscrete” in this context.  For me indiscrete would
> refer to things in the image of the right adjoint to the functor which associates to a
> graph its set of vertices. The set of edges of the indiscrete graph would  then be V x V.
>
> Regards,
>
> Steve Lack.
>
>
>
>> On 19 Dec 2015, at 9:48 PM, Aleks Kissinger <aleks0@gmail.com> wrote:
>>
>> It's common to describe the category of (directed, multi-) graphs as a
>> functor category Graph := [2, Set], where 2 here is the category with
>> 2 objects and 2 parallel arrows (s & t).
>>
>> For a pair of sets (V,E), one can construct the indiscrete graph
>> I(V,E) as a graph with vertices V and edges E x V x V, where the
>> source and target maps are just the 2nd and 3rd projection
>> respectively. This gives a right adjoint to the forgetful functor from
>> Graph to pairs of sets. This enables one to construct a category of
>> graphs with a fixed set of vetex/edge labels as a slice over Graph:
>>
>> Graph / I(Lv, Le)
>>
>> since a graph hm G --> I(Lv,Le) is the same as a map U(G) --> (Lv,Le),
>> which is just a pair of functions assigning labels to the vertices and
>> edges of G.
>>
>>
>> This seems to me like a pretty standard trick, which extends to any
>> functor category from a C which is in some sense "suitably acyclic".
>> For instance, consider a category of "partitioned graphs" [3, Set],
>> where 3 has objects (P,V,E) and arrows:
>>
>> E --s--> V, E --t--> V, and V --p--> P
>>
>> where, p assigns each of the vertices a partition. For a triple
>> (P,V,E) we can form the indiscrete partitioned graph with:
>>
>> - partitions P
>> - vertices V x P
>> - edges E x (V x P) x (V x P)
>> - p = pi2, s = pi2, t = pi3
>>
>> which gives a right-adjoint to the forgetful functor from partitioned
>> graphs to triples of sets. This is clearly an instance of a general
>> recipe, whereby you start with the objects with no arrows out, and
>> work your way backwards, always adding copies of the codomain of every
>> out-arrow. Again one can attach labels to partitioned graphs by
>> slicing:
>>
>> [3,Set] / I(Lp,Lv,Le)
>>
>>
>> So, my question: Is the general case a known/studied construction? If
>> so, could someone provide a reference?
>>
>>
>>
>> Best,
>>
>> Aleks
>>
>>


[For admin and other information see: http://www.mta.ca/~cat-dist/ ]

Re: Indiscrete objects in a functor category

[Peter Johnstone]

The forgetful functor [C,Set] --> Set/ob C always has a right adjoint,
given by right Kan extension along the inclusion C_0 --> C, where C_0
is the discrete category with the same objects as C. For the same
construction in a more general context, see B2.3.16 in `Sketches of
an Elephant'.

Peter Johnstone

On Sat, 19 Dec 2015, Aleks Kissinger wrote:

> It's common to describe the category of (directed, multi-) graphs as a
> functor category Graph := [2, Set], where 2 here is the category with
> 2 objects and 2 parallel arrows (s & t).
>
> For a pair of sets (V,E), one can construct the indiscrete graph
> I(V,E) as a graph with vertices V and edges E x V x V, where the
> source and target maps are just the 2nd and 3rd projection
> respectively. This gives a right adjoint to the forgetful functor from
> Graph to pairs of sets. This enables one to construct a category of
> graphs with a fixed set of vetex/edge labels as a slice over Graph:
>
> Graph / I(Lv, Le)
>
> since a graph hm G --> I(Lv,Le) is the same as a map U(G) --> (Lv,Le),
> which is just a pair of functions assigning labels to the vertices and
> edges of G.
>
>
> This seems to me like a pretty standard trick, which extends to any
> functor category from a C which is in some sense "suitably acyclic".
> For instance, consider a category of "partitioned graphs" [3, Set],
> where 3 has objects (P,V,E) and arrows:
>
> E --s--> V, E --t--> V, and V --p--> P
>
> where, p assigns each of the vertices a partition. For a triple
> (P,V,E) we can form the indiscrete partitioned graph with:
>
> - partitions P
> - vertices V x P
> - edges E x (V x P) x (V x P)
> - p = pi2, s = pi2, t = pi3
>
> which gives a right-adjoint to the forgetful functor from partitioned
> graphs to triples of sets. This is clearly an instance of a general
> recipe, whereby you start with the objects with no arrows out, and
> work your way backwards, always adding copies of the codomain of every
> out-arrow. Again one can attach labels to partitioned graphs by
> slicing:
>
> [3,Set] / I(Lp,Lv,Le)
>
>
> So, my question: Is the general case a known/studied construction? If
> so, could someone provide a reference?
>
>
>
> Best,
>
> Aleks
>
>


[For admin and other information see: http://www.mta.ca/~cat-dist/ ]