Date: Sat, 15 Mar 1997 09:49:46 -0400 (AST) Subject: a characterisation of factorisation systems Date: Fri, 14 Mar 1997 15:26:15 GMT From: Paul-Andre Mellies Dear categorists, I have recently proved an (E,M)-factorisation theorem in the framework of axiomatic rewriting systems: every derivation X -> Y factorises (up to Levy permutation equivalence) into a head reduction X -> Z followed by a non-head reduction Z -> Y. One special difficulty in my case is that I do not define the class M of non-head reductions as a category. So, I need a characterisation of factorisation system (E,M) without any assumption of categoricity of E or M. Here is the statement of the theorem I finally proved: ----------------------------------------------------------------------------- Let E and M be two classes of morphisms in a category C. (E,M) is a factorisation system of C if and only if the four following properties hold: 1. every morphism f in C can be factored as f=me with m in M and e in E, 2. if e is a morphism in E and m is a morphism in M then e is orthogonal to m, 3. if i is an iso left composable to e in E, then ie is in E, 4. if i is an iso right composable to m in M, then mi is in M. ----------------------------------------------------------------------------- I do not know if this characterisation already exists in the litterature on factorisation systems. If it does, please send me the reference to integrate in my paper. People interested in the paper can load it there: http://www.dcs.ed.ac.uk/home/paulm/ Date: Mon, 17 Mar 1997 14:49:58 -0400 (AST) Subject: Re: a characterisation of factorisation systems Date: Mon, 17 Mar 1997 10:01:13 -0500 From: Walter Tholen With regard to the message below, it should be pointed out that the history of factorization systems is almost as old as category theory itself, going back at least to Mac Lane's "Groups, categories and duality" of 1948 (Proc. Nat. Acad. Sci. U.S.A. 34, 263-267). The paper most often referred to in conjunction with factorization systems (P. Freyd and G.M. Kelly. JPAA 2 (1972) 169-191) requires the classes E and M to be closed under composition, a requirement that also occurs in many other papers. But that, in the presence of the conditions 1-4 below, this is a redundant requirement was known to at least some people at the time. The statement below appears explicitly in my Ph.D. thesis of 1974 (as Theorem 3.11 - even more generally, since I deal with "factorizations along a functor" there, which give the usual thing if you then consider the identity functor). But I certainly do not claim to have been the first to observe this. I am almost certain that the theorem below was known to O. Wyler in 1968 who has an unpublished paper with H. Ehrbar of 1968 (which he recalls in a 1987 paper in the Cahiers 28 , 143-159). Another often neglected reference is C.M. Ringel, Math. Z. 112 (1970) 248-266. I would also think that John Isbell , J. Kennison, Horst Herrlich, D. Pumpluen and Louis Nel were aware of the theorem at about that time. If all this does not sound clear-cut, then look at Theorem 1.8 in my book with D. Dikranjan on the "Categorical Structure of Closure Operators" (Kluwer, 1995); see also the Notes to Chapter 1 which give other useful references. Best regards to all, Walter Tholen. On Mar 15, 9:49am, categories wrote: > Subject: a characterisation of factorisation systems > Date: Fri, 14 Mar 1997 15:26:15 GMT > From: Paul-Andre Mellies > > > Dear categorists, > > I have recently proved an (E,M)-factorisation theorem > in the framework of axiomatic rewriting systems: > every derivation X -> Y factorises (up to Levy permutation equivalence) > into a head reduction X -> Z followed by a non-head reduction Z -> Y. > > One special difficulty in my case is that I do not define > the class M of non-head reductions as a category. > So, I need a characterisation of factorisation system (E,M) > without any assumption of categoricity of E or M. > Here is the statement of the theorem I finally proved: > > ----------------------------------------------------------------------------- > Let E and M be two classes of morphisms in a category C. > (E,M) is a factorisation system of C if and only if > the four following properties hold: > > 1. every morphism f in C can be factored as f=me with m in M and e in E, > 2. if e is a morphism in E and m is a morphism in M then e is orthogonal to m, > 3. if i is an iso left composable to e in E, then ie is in E, > 4. if i is an iso right composable to m in M, then mi is in M. > ----------------------------------------------------------------------------- > > I do not know if this characterisation already exists in the litterature > on factorisation systems. If it does, please send me the reference > to integrate in my paper. > Date: Tue, 18 Mar 1997 10:29:24 -0400 (AST) Subject: Re: a characterisation of factorisation systems Date: 18 Mar 97 12:42:34 +0200 From: Hans Porst >Date: Fri, 14 Mar 1997 15:26:15 GMT >From: Paul-Andre Mellies Your definition >Let E and M be two classes of morphisms in a category C. >(E,M) is a factorisation system of C if and only if >the four following properties hold: > >1. every morphism f in C can be factored as f=me with m in M and e in E, >2. if e is a morphism in E and m is a morphism in M then e is orthogonal >to m, >3. if i is an iso left composable to e in E, then ie is in E, >4. if i is an iso right composable to m in M, then mi is in M. seems to be precisely the definition used in Adamek, Herrlich, Strecker: Abstract and Concrete Categories. Check their Chapter 14! AHS 14.6 shows in particular that E and M will be closed under composition. --------------------------------------------------------- Hans-E. Porst e-mail: porst@mathematik.uni-bremen.de FB 3: Mathematik Phone: +49 421 2182276 University of Bremen +49 421 2184971 D-28334 Bremen Fax: +49 421 2184856 ---------------------------------------------------------