Re: making a cone universal in a faithful way

Re: making a cone universal in a faithful way

[Lutz Schroeder]

Dear Dimitri,

> For example, if I is the empty category, the question becomes "when can
> you make c an initial object in a faithful way?". If I is the final
> category, then the cocone alpha amounts to a morphism f : F(*) -> c and the
> question becomes "when can you make f an isomorphism in a faithful way?".
>
> There are two obvious necessary conditions.
> 1) Let f,g : c -> d be two morphisms of C. If f alpha_i = g alpha_i for
> every i in I, then we should have f = g.L
> 2) Let f : a -> F(i) and g : a -> F(j) be two morphisms of C such that
> alpha_i f = alpha_j g. Then for every cocone beta : F => d, we should
> have beta_i f = beta_j g.
>
> In the case of the empty category, the first condition means that for
> every object d there is at most one arrow c -> d and the second condition
> is void. In the case of the final category, the first condition means
> that f is an epi and the second that f is a mono. It is not hard to prove
> that in both cases, theses conditions are sufficient.

While I'm willing to believe the case of initial objects, the statement
is wrong already for the case of isomorphisms. Let's call f a potential
isomorphism if there exists a faithful functor (equivalently an
embedding) that makes f an isomorphism. Then one has the following
property of potential isomorphisms (from my 1999 thesis; in German, I'm
afraid):

Lemma: Let s be a potential isomorphism, and let f,g,h,j,l,p be
morphisms such that

	fs = sg
	hg = ks
	fl = sp.

Then kl = hp.

Proof: In an extended category where s has a two-sided inverse s^{-1},
we have gs^{-1} = s^{-1}f from fs = sg, and hence

	kl = kss^{-1}l = hgs^{-1}l = hs^{-1}fl = hs^{-1}sp = hp    []

The property of the lemma is not implied by s being both epi and mono
(i.e. a bimorphism). It is comparatatively easy to prove this using
contrived examples, such as the following.

Let the category A consist of objects A, B, C, D, and families of morphisms

	g_i: A -> A
	p_i: B -> A
	s_k: A -> C
	h_i: A -> D
	l_i: B -> C
	f_i: C -> C
	k_i: B -> D
	q_i,r: B -> D

indexed over i>=0, k>=1, where we identify f_0 and g_0 with the
respective identities. Composition is by addition of indices, with the
single exception

	h_0p_0 = r.

(This satisfies the associative law, since the exceptional case r occurs
only in trivial cases of the law -- it cannot be pre- or postcomposed
with a nontrivial morphism, and its two factors do not have proper
factorisations.) Then s_1 is a bimorphism but violates the property of
the above lemma, and hence is not a potential isomorphism:

	f_1s_1 = s_1g_1, h_0g_1 = k_0s_1, and f_1l_0 = s_1p_0,

but

	k_0l_0 = q_0 \neq r = h_0p_0.


Best regards,

Lutz

-- 
--------------------------------------
PD Dr. Lutz Schro"der
Senior Researcher
DFKI Bremen
Safe and Secure Cognitive Systems
Cartesium, Enrique-Schmidt-Str. 5
D-28359 Bremen

phone: (+49) 421-218-64216
Fax:   (+49) 421-218-9864216
mail: Lutz.Schroeder@dfki.de
www.dfki.de/sks/staff/lschrode
--------------------------------------


-------------------------------------------------------------
Deutsches Forschungszentrum fu"r Ku"nstliche Intelligenz GmbH
Firmensitz: Trippstadter Strasse 122, D-67663 Kaiserslautern

Gescha"ftsfu"hrung:
Prof. Dr. Dr. h.c. mult. Wolfgang Wahlster (Vorsitzender)
Dr. Walter Olthoff

Vorsitzender des Aufsichtsrats:
Prof. Dr. h.c. Hans A. Aukes

Amtsgericht Kaiserslautern, HRB 2313
-------------------------------------------------------------






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

Re: making a cone universal in a faithful way

[Steve Lack]

Dear Dimitri,

I think that finding useful necessary and sufficient conditions in general
is a very hard problem. But here is something that might be useful in
specific cases.

There will exist some faithful functor G:C-->D sending alpha to a colimit
cocone if and only if the universal functor G:C-->D sending alpha to
a colimit cocone is faithful. This universal functor can be constructed
as follows (this forms part of the general theory of sketches).

Let M be the full subcategory of [C^op,Set] consisting of those functors
F which send alpha to a limit cone. Then M is reflective in [C^op,Set],
via a left adjoint L, and the composite LY:C-->M does indeed send alpha
to a colimit cocone. The universal G is obtained by factorizing LY as
a bijective on objects functor G:C-->D followed by a fully faithful
J:D-->M.

Clearly G will be faithful if and only if LY is, and this can be determined
once one has calculated L on representables. Calculating L explicitly
is in general still a hard problem, but in specific cases you may be able to
do it sufficiently explicitly to solve your problem.

The connection with sketches is that you can think of your cocone as giving
a limit sketch on C^op, then the category M defined above is the category of
models of the sketch.

Regards,

Steve Lack.


On 4/08/09 2:37 AM, "Dimitri Ara" <dimitri.ara@gmail.com> wrote:

> Dear List,
>
> Has the following elementary problem been already studied?
>
> Let C be a category, I a small category, F : I -> C a functor and
> alpha : F => c a cocone (c is an object of C). When does there exist a
> category D and a faithful functor G : C -> D taking alpha to a universal
> cocone?
>
> For example, if I is the empty category, the question becomes "when can
> you make c an initial object in a faithful way?". If I is the final
> category, then the cocone alpha amounts to a morphism f : F(*) -> c and the
> question becomes "when can you make f an isomorphism in a faithful way?".
>
> There are two obvious necessary conditions.
> 1) Let f,g : c -> d be two morphisms of C. If f alpha_i = g alpha_i for
> every i in I, then we should have f = g.
> 2) Let f : a -> F(i) and g : a -> F(j) be two morphisms of C such that
> alpha_i f = alpha_j g. Then for every cocone beta : F => d, we should
> have beta_i f = beta_j g.
>
> In the case of the empty category, the first condition means that for
> every object d there is at most one arrow c -> d and the second condition
> is void. In the case of the final category, the first condition means
> that f is an epi and the second that f is a mono. It is not hard to prove
> that in both cases, theses conditions are sufficient.
>
> Question: are they sufficient in the general case?
>
> Regards,
> --
> Dimitri
>
>
> [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: making a cone universal in a faithful way

[Lutz Schroeder, categories]

Dear Dimitri,

> You are right. I didn't checked very carefully the local confluence of my
> rewriting system. To get confluence, I need to add the fact that the
> bimorphism f satisfies "fu = vf implies u = 1 and v = 1". So this is enough
> for f to be a potential isomorphism.

Yes, that does the trick, and is also the best sufficient condition that
I have been able to come up with in my thesis. I would guess something
similar might work for the general case, but the condition is actually
so strong as to be somewhat unsatisfactory. Note in particular that it
fails for actual (nontrivial) isomorphisms. I poked around this problem
for quite a bit back then but haven't been able to isolate a
satisfactory criterion (other than the obvious one that talks explicitly
about equality in a non-confluent axiom system).

Good luck,

Lutz



-- 
--------------------------------------
PD Dr. Lutz Schröder
Senior Researcher
DFKI Bremen	
Safe and Secure Cognitive Systems
Cartesium, Enrique-Schmidt-Str. 5
D-28359 Bremen

phone: (+49) 421-218-64216
Fax:   (+49) 421-218-9864216
mail: Lutz.Schroeder@dfki.de
www.dfki.de/sks/staff/lschrode
--------------------------------------


-------------------------------------------------------------
Deutsches Forschungszentrum für Künstliche Intelligenz GmbH
Firmensitz: Trippstadter Strasse 122, D-67663 Kaiserslautern

Geschäftsführung:
Prof. Dr. Dr. h.c. mult. Wolfgang Wahlster (Vorsitzender)
Dr. Walter Olthoff

Vorsitzender des Aufsichtsrats:
Prof. Dr. h.c. Hans A. Aukes

Amtsgericht Kaiserslautern, HRB 2313
-------------------------------------------------------------




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

Re: making a cone universal in a faithful way

[Dimitri Ara]

        Dear Lutz,

> While I'm willing to believe the case of initial objects, the statement
> is wrong already for the case of isomorphisms.

You are right. I didn't checked very carefully the local confluence of my
rewriting system. To get confluence, I need to add the fact that the
bimorphism f satisfies "fu = vf implies u = 1 and v = 1". So this is enough
for f to be a potential isomorphism.

While the general statement I gave is wrong, I'm still interested in
condition to make the conclusion true (for example, in the case of the
sum or of the amalgated sum).

Regards,
-- 
Dimitri


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

making a cone universal in a faithful way

[Dimitri Ara]

Dear List,

Has the following elementary problem been already studied?

Let C be a category, I a small category, F : I -> C a functor and
alpha : F => c a cocone (c is an object of C). When does there exist a
category D and a faithful functor G : C -> D taking alpha to a universal
cocone?

For example, if I is the empty category, the question becomes "when can
you make c an initial object in a faithful way?". If I is the final
category, then the cocone alpha amounts to a morphism f : F(*) -> c and the
question becomes "when can you make f an isomorphism in a faithful way?".

There are two obvious necessary conditions.
1) Let f,g : c -> d be two morphisms of C. If f alpha_i = g alpha_i for
every i in I, then we should have f = g.
2) Let f : a -> F(i) and g : a -> F(j) be two morphisms of C such that
alpha_i f = alpha_j g. Then for every cocone beta : F => d, we should
have beta_i f = beta_j g.

In the case of the empty category, the first condition means that for
every object d there is at most one arrow c -> d and the second condition
is void. In the case of the final category, the first condition means
that f is an epi and the second that f is a mono. It is not hard to prove
that in both cases, theses conditions are sufficient.

Question: are they sufficient in the general case?

Regards,
--
Dimitri


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