Four problems

Four problems

[Joyal, André]

Jean Benabou has formulated four problems of category theory.
They were communicated to a restricted list of peoples, not a private list.
I see no serious raisons for not sharing these problems with everyones. 
Here they are:


>Prob1. What conditions must a (small)  category C satisfy in order that :
>there exists a faithful functor  F: C --> G  where  G  is a groupoid?    
>(Generalized "Mal'cev" conditions)

>Prob2.  A "little" bit harder, in the same vein. Let C  be a (small) category, 
> S a set of maps of C and P: C --> C[Inv(S)]  be the universal functor 
> which inverts all maps of S. What conditions must the pair  (C,S)  satisfy 
>so that the functor >P  is faithful?

> If  P: C --> S  is a functor, I denote by V(P)  the subcategory of C  
>which has the same objects and as maps the vertical maps i.e. the f's such 
>that P(f) is an identity. Let V  be a subcategory of a (small) category C. 
> What conditions >must  the pair (C,V)  satisfy in order that:

>Prob3. There exists a functor P with domain C such that  V = V(P)
>Prob4. There exists a fibration  P with domain  C  such that  V = V(P)


Best,
André


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

Re: Four problems

[P.T.Johnstone]

On Apr 28 2010, Joyal, André wrote:

>Jean Benabou has formulated four problems of category theory.
>They were communicated to a restricted list of peoples, not a private list.
>I see no serious raisons for not sharing these problems with everyones. 
>Here they are:
>
>
>>Prob1. What conditions must a (small)  category C satisfy in order that :
>>there exists a faithful functor  F: C --> G  where  G  is a groupoid?    
>>(Generalized "Mal'cev" conditions)
>
This problem is solved in a recent paper of mine "On embedding categories
in groupoids" in Math. Proc. Camb. Philos. Soc., vol. 145. Actually, the
problem was essentially solved by Mal'cev and (independently) by Jim Lambek,
who gave necessary and sufficient conditions for a semigroup to be
embeddable in a group; all one has to do is to observe that the same
conditions work in the situation when one has several objects.

Peter Johnstone

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

Re: Four problems

[tholen]

In the article

J. Rosicky, W. Tholen, "Factorization, fibration and torsion", J.
Homotopy Theory and Related Structures (electronic) 2 (2007) 295-314

we prove a result closely related to Problems 3 and 4 below (variations
of which may well have appeared earlier?), as follows:

In a finitely complete category C,  (E,M) is a simple reflective
factorization system of C (in the sense of Cassidy, Hebert, Kelly, J.
Austr. Math. Soc 38, (1985)) if, and only if, there exists a
prefibration P: C ---> B preserving the terminal object of C with E =
P^{-1}(Iso B) and M = {P-cartesian morphisms}.

Here "prefibration" means that for all objects c in C, the functors C/c
---> B/Pc induced by P have right adjoints, such that the induced
monads are idempotent. (For a fibration one asks the counits to be
identity morphisms.) Of course, Jean's question wants P^(-1)(Iso) to be
replaced by the non-iso-closed class P^(-1)(Identities), which prevents
the class from being part of an ordinary factorization system. But
(without having looked into this at all) I would suspect that there is
probably a (more cumbersome) reformulation of the theorem above which
would address that concern.

Regards,
Walter.


Quoting "Joyal, André" <joyal.andre@uqam.ca>:

> Jean Benabou has formulated four problems of category theory.
> They were communicated to a restricted list of peoples, not a private list.
> I see no serious raisons for not sharing these problems with everyones.
> Here they are:
>
>
>> Prob1. What conditions must a (small)  category C satisfy in order that :
>> there exists a faithful functor  F: C --> G  where  G  is a groupoid?
>> (Generalized "Mal'cev" conditions)
>
>> Prob2.  A "little" bit harder, in the same vein. Let C  be a (small)
>> category,
>> S a set of maps of C and P: C --> C[Inv(S)]  be the universal functor
>> which inverts all maps of S. What conditions must the pair  (C,S)  satisfy
>> so that the functor >P  is faithful?
>
>> If  P: C --> S  is a functor, I denote by V(P)  the subcategory of C
>> which has the same objects and as maps the vertical maps i.e. the f's such
>> that P(f) is an identity. Let V  be a subcategory of a (small) category C.
>> What conditions >must  the pair (C,V)  satisfy in order that:
>
>> Prob3. There exists a functor P with domain C such that  V = V(P)
>> Prob4. There exists a fibration  P with domain  C  such that  V = V(P)
>
>
> Best,
> André
>
>
> [For admin and other information see: http://www.mta.ca/~cat-dist/ ]
>




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

RE : categories: Four problems

[Joyal, André]

Dear Walter,

Let me sketch a possible solution to problem 4 
(along the lines you have suggested).

> If  P: C --> S  is a functor, I denote by V(P)  the subcategory of C 
>which has the same objects and as maps the vertical maps i.e. the f's such
>that P(f) is an identity. Let V  be a subcategory of a (small) category C.
> What conditions >must  the pair (C,V)  satisfy in order that
> there exists a fibration  P with domain  C  such that  V = V(P)?

I first make a few observation on the properties
of a Grothendieck fibration P:C--->B.

1) If V is the subcategory of vertical maps in C,
then a morphism in C is cartesian with respect
to the functor P iff it is right orthogonal 
(= it has the unique right lifting property)
to every map in V.  

2) if R(V) is the class of maps in C which are right orthogonal
to every map in V, then every map f in C admits
a factorisation f=cv with v in V and c in R(V).

3) the base change of a map in V along a map in
R(V) exists and can be taken in V (up to an isomorphism). 

4) A Grothendieck fibration P:C--->B is *connected* if its fibers 
are connected categories. It is easy to see that every Grothendieck 
fibration  P:C--->B admits a factorisation P=DQ:C-->E-->B with Q:C-->E 
a connected Grothendieck fibration and  S:E-->B a discrete fibration 
(the fibers of D are the connected components of the fibers of P).
The vertical maps of P coincide with
the vertical maps of Q. This shows that if the problem
has a solution, then there is one in which
the fibration P:C-->B is connected, in which case there is a 
natural bijection between the objects of the 
base category B and the set  connected components
of the sub-category of vertical maps.


We shall suppose the the conditions 1-2-3 above are satisfied
but we will we will need an extra condition later. 

The idea then is to declare that the objects of B
*are* the connected components of the subcategory V.

If C_0 and C_1 are two connected components of V,
consider the distributor D:C_0-->C_1
obtained by putting D(a,b)=C(a,b) for every object
a of C_0 and every object b of C_1. 
The idea is to put

B(C_0,C_1)= colimit D

and to use the composition of arrows in C for
defining the composition of morphisms in B.
But we have to make sure that the composition
so defined is unambigous. And this is where
the extra condition 4 is popping out. 

First, the distributor D:C_0-->C_1 is locally 
corepresentable by a family. More precisely,
for any object b of C_1 the presheaf 

D(-,b):C_0-->Set

is a coproduct of representable presheaves.
This follows directly from condition 2
(the representing objects are morphisms f:a-->b in R(V)).
Let us put 

T(b)=\pi_0D(-,b)  

This defines a functor T:C_1--->Set (which depends
on C_0). It follows from condition 3 that
the functor T inverts every morphism of C_1.
This shows that the distribuor D:C_0-->C_1
is of a very special type. The category
of elements of the functor T is a *covering* el(T)-->C_1
(a covering is a discrete fibration which
is also an opfibration). It follows
that the distributor D:C_0-->C_1 can be represented as a span

C_0<---el(T)--->C_1

in which the second leg is a covering.
The problem 4 of Benabou will have a solution 
iff this covering is trivial (ie it is a product)
for any pair of connected components C_0
and C_1 of V. This is true for example
when the connected components of V are 
simply connected.


Best,
André


-------- Message d'origine--------
De: tholen@mathstat.yorku.ca [mailto:tholen@mathstat.yorku.ca]
Date: ven. 30/04/2010 21:13
À: Joyal, André
Cc: categories@mta.ca; tholen@mathstat.yorku.ca
Objet : Re: categories: Four problems
 
In the article

J. Rosicky, W. Tholen, "Factorization, fibration and torsion", J. 
Homotopy Theory and Related Structures (electronic) 2 (2007) 295-314

we prove a result closely related to Problems 3 and 4 below (variations 
of which may well have appeared earlier?), as follows:

In a finitely complete category C,  (E,M) is a simple reflective 
factorization system of C (in the sense of Cassidy, Hebert, Kelly, J. 
Austr. Math. Soc 38, (1985)) if, and only if, there exists a 
prefibration P: C ---> B preserving the terminal object of C with E = 
P^{-1}(Iso B) and M = {P-cartesian morphisms}.

Here "prefibration" means that for all objects c in C, the functors C/c 
---> B/Pc induced by P have right adjoints, such that the induced 
monads are idempotent. (For a fibration one asks the counits to be 
identity morphisms.) Of course, Jean's question wants P^(-1)(Iso) to be 
replaced by the non-iso-closed class P^(-1)(Identities), which prevents 
the class from being part of an ordinary factorization system. But 
(without having looked into this at all) I would suspect that there is 
probably a (more cumbersome) reformulation of the theorem above which 
would address that concern.

Regards,
Walter.


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

Four problems corrected

[Joyal, André]

Dear All, 

there was a few typographic errors my last message. 
I am sending you the correction.

Best, 
André


-----------------------------------------------------
 
Dear Walter,

Let me sketch a possible solution to problem 4 
(along the lines you have suggested).

> If  P: C --> S  is a functor, I denote by V(P)  the subcategory of C 
>which has the same objects and as maps the vertical maps i.e. the f's such
>that P(f) is an identity. Let V  be a subcategory of a (small) category C.
> What conditions >must  the pair (C,V)  satisfy in order that
> there exists a fibration  P with domain  C  such that  V = V(P)?

I first make a few observations on the properties
of a Grothendieck fibration P:C--->B.

1) If V is the subcategory of vertical maps in C,
then a morphism in C is cartesian with respect
to the functor P iff it is right orthogonal 
(= it has the unique right lifting property)
to every map in V.  

2) if R(V) is the class of maps in C which are right orthogonal
to every map in V, then every map f in C admits
a factorisation f=cv with v in V and c in R(V).

3) the base change of a map in V along a map in
R(V) exists and can be taken in V (up to an isomorphism). 

4) A Grothendieck fibration P:C--->B is *connected* if its fibers 
are connected categories. It is easy to see that every Grothendieck 
fibration  P:C--->B admits a factorisation P=SQ:C-->E-->B with Q:C-->E 
a connected Grothendieck fibration and  S:E-->B a discrete fibration 
(the fibers of S are the connected components of the fibers of P).
The vertical maps of P coincide with
the vertical maps of Q. This shows that if the problem
has a solution, then there is one in which
the fibration P:C-->B is connected, in which case there is a 
natural bijection between the objects of the 
base category B and the set  connected components
of the sub-category of vertical maps.


We shall suppose the the conditions 2-3 above are satisfied
but we will we will need an extra condition later. 

The idea then is to declare that the objects of B
*are* the connected components of the subcategory V.

If C_0 and C_1 are two connected components of V,
consider the distributor D:C_0-->C_1
obtained by putting D(a,b)=C(a,b) for every object
a of C_0 and every object b of C_1. 
The idea is to put

B(C_0,C_1)= colimit D

and to use the composition of arrows in C for
defining the composition of morphisms in B.
But we have to make sure that the composition
so defined is unambigous. And this is where
the extra condition 4 is popping out. 

First, the distributor D:C_0-->C_1 is locally 
corepresentable by a family. More precisely,
for any object b of C_1 the presheaf 

D(-,b):C_0-->Set

is a coproduct of representable presheaves.
This follows directly from condition 2
(the representing objects are morphisms f:a-->b in R(V)).
Let us put 

T(b)=\pi_0D(-,b)=colimit D(-,b)  

This defines a functor T:C_1--->Set (which depends
on C_0). It follows from condition 3 that
the functor T inverts every morphism of C_1.
This shows that the distribuor D:C_0-->C_1
is of a very special type. The category
of elements of the functor T is a *covering* el(T)-->C_1
(a covering is a discrete fibration which
is also an opfibration). It follows
that the distributor D:C_0-->C_1 can be represented as a span

C_0<---el(T)--->C_1

in which the second leg is a covering.
Assuming that the conditions 2 and 3 are 
satisfied, the problem of Benabou will have a solution 
iff this covering is trivial (ie it is a product)
for any pair of connected components C_0
and C_1 of V. This is true for example
when the connected components of V are 
simply connected.


Best,
André


-------- Message d'origine--------
De: tholen@mathstat.yorku.ca [mailto:tholen@mathstat.yorku.ca]
Date: ven. 30/04/2010 21:13
À: Joyal, André
Cc: categories@mta.ca; tholen@mathstat.yorku.ca
Objet : Re: categories: Four problems
 
In the article

J. Rosicky, W. Tholen, "Factorization, fibration and torsion", J. 
Homotopy Theory and Related Structures (electronic) 2 (2007) 295-314

we prove a result closely related to Problems 3 and 4 below (variations 
of which may well have appeared earlier?), as follows:

In a finitely complete category C,  (E,M) is a simple reflective 
factorization system of C (in the sense of Cassidy, Hebert, Kelly, J. 
Austr. Math. Soc 38, (1985)) if, and only if, there exists a 
prefibration P: C ---> B preserving the terminal object of C with E = 
P^{-1}(Iso B) and M = {P-cartesian morphisms}.

Here "prefibration" means that for all objects c in C, the functors C/c 
---> B/Pc induced by P have right adjoints, such that the induced 
monads are idempotent. (For a fibration one asks the counits to be 
identity morphisms.) Of course, Jean's question wants P^(-1)(Iso) to be 
replaced by the non-iso-closed class P^(-1)(Identities), which prevents 
the class from being part of an ordinary factorization system. But 
(without having looked into this at all) I would suspect that there is 
probably a (more cumbersome) reformulation of the theorem above which 
would address that concern.

Regards,
Walter.



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

Re: Four problems(corrected2)

[tholen]

Dear Andre,

You are overly generous when you describe your clever solution to
Jean's Problem 4 as being "along the lines [I] suggested".

The theorem with Rosicky that I had mentioned is at most a precursor to
your result; besides, we proved that theorem only after a remark that
you made after my talk at the CT meeting at Halifax/White Point.

Briefly: 100% credit for the solution belongs to you.

Bravo, Walter.


Andre Joyal wrote:
> -----------------------------------------------------
>
> Dear Walter,
>
> Let me sketch a possible solution to problem 4
> (along the lines you have suggested).




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

Re: Four problems(corrected2)

[Eduardo J. Dubuc]

It makes you feel real good a breath of fresh air !!  Thank you Walter.

eduardo dubuc



tholen@mathstat.yorku.ca wrote:
> Dear Andre,
>
> You are overly generous when you describe your clever solution to
> Jean's Problem 4 as being "along the lines [I] suggested".
>
> The theorem with Rosicky that I had mentioned is at most a precursor to
> your result; besides, we proved that theorem only after a remark that
> you made after my talk at the CT meeting at Halifax/White Point.
>
> Briefly: 100% credit for the solution belongs to you.
>
> Bravo, Walter.
>
>
> Andre Joyal wrote:
>> -----------------------------------------------------
>>
>> Dear Walter,
>>
>> Let me sketch a possible solution to problem 4
>> (along the lines you have suggested).
>

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

Re=3A_Four_problems=28corrected2=29?=

[Joyal, André]

Dear Walter,

You wrote:

> Briefly: 100% credit for the solution belongs to you.


This is very kind of you to say that!
 
But you have a contribution, since your partial solution 
stimulated me to think more about the problem.

Benabou also contributed by formulating the problem.


Best,
André


-------- Message d'origine--------
De: categories@mta.ca de la part de tholen@mathstat.yorku.ca
Date: dim. 02/05/2010 21:06
À: Joyal, André
Objet : categories: Re: Four problems(corrected2)
 
Dear Andre,

You are overly generous when you describe your clever solution to
Jean's Problem 4 as being "along the lines [I] suggested".

The theorem with Rosicky that I had mentioned is at most a precursor to
your result; besides, we proved that theorem only after a remark that
you made after my talk at the CT meeting at Halifax/White Point.

Briefly: 100% credit for the solution belongs to you.

Bravo, Walter.


Andre Joyal wrote:

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