Subject: Re: Categories of relational structures Date: 03 May 1993 14:01:26 -0400 (EDT) From: Paul Glenn >Define a relational structure (A,R) to consist of a set A and a >n-ary relation on A for some ordinal n. A homomorphism >f:(A,R)->(B,S) is a function f:A->B between the underlying sets >of two relational structures of the same arity, such that f(R) c >S. Write Str_n for the category of all n-ary relational >structures and homomorphisms between them, and Str for the sum >in CAT of Str_n over all ordinals n. >1. What is the term for the notion of full subcategory of >either Str_n or Str? Failing that, what would be a suitable >term? Relational categories? Categories of relational >structures? > >Familiar examples of such categories and an upper bound on their >arities include those of groups (3), rings (4), fields (4), >lattices (3), vector spaces over the field K (1+max(|K|,2)), >directed graphs (2), posets (2), and categories (3). > >I would expect complete lattices, complete Boolean algebras, >topological spaces, and hypergraphs not to embed in Str_n for >any n, because their structural elements (subsets, e.g. open >sets) have no fixed cardinality bound, unlike n-tuples. A >pointer to a proof of such nonembedding, or a demonstration of >how to embed them, would be greatly appreciated. Since the >concept is such a natural one, this question must surely have >been looked at before. > >2. What generalizations of Str or Str_n have been considered? >One can make Str a bit more "communicative" by permitting >homomorphisms between dissimilar structures (A,R), (B,S) of >respective arities mby defining R$(n) to be the set of n-tuples of A whose first m >elements satisfy R. This probably looks about as useful today >as the telephone did in 1879. I can offer a few comments on arity concerning your category of "relational structures" Str. First, with regard to the list of examples where you mentioned an "an upper bound on their arities", I wondered if you meant (e.g. for groups) the *least* n such that groups embed into Str_n? That would be n=3 in the group case since each group's multiplication table can be regarded as a 3-ary relation R where (a,b,c) in R iff ab=c. For *any* n>3 one can define (for any group) an n-ary relation S where (a1,...,an) belongs to S iff a1 ... an = 1. The mult table for the group determines S and is recoverable from S. Thus a group embeds in Str_n for any n>3. However, n=3 is minimal for groups. Second, an n+1-ary relation R on S0 x ... x Sn spawns an infinite family of relations of all arities. These are generated by two operations: (1) Projection: the image of R in the composition R >---> (product all j) Sj ----> (product all j except i) Sj. (Simplicially speaking, this is the "i'th face" of R, i=0,...,n). (2) Repetition of coordinates: R x Si >---> S0 x ... x Si x Si x ... x Sn. (Simplicially speaking, this is the "i'th degenerate image" of R). There are equations, the "simplicial identities", which equate the various relations obtained this way. While none of these relations derived from R contain "new" information, they provide a useful alternative for defining homomorphisms between relations of different arities. Here's what I have in mind. Let R >--> A^m and S >--> B^n be relations , m and n arbitrary. Then define a homomorphism from (R,A) ---> (S,B) as the composite (R,A) --> (R',A) --> (S,B) where R' >---> A^n is a "simplicial image" of R >--> A^m obtained by some sequence of projection and repetition operations described above, and where (R',A) ---> (S,B) is a homomorphism in Str_n. This strikes me as being perhaps more "natural" (though more restrictive) than the "padding out" process you mentioned in your post. With this definition of homomorphism, an n-ary relation R >--> A^m corresponds to a functor (delta/[m])^op --> Sets. (Delta = cat of finite totally ordered sets and non-decreasing maps). The category Str can be viewed, equivalently, as: (1) fibred over delta (i.e. there's a discrete opfibration Str --> delta^op), or (2) a coalgebra for a certain cotriple on Cat, the (ordinary) category of small categories. (This must be qualified slightly since Str isn't small). The details of these assertions are in a paper I've written (I'd be glad to send a preprint). In that paper, I viewed monics R >--> A^(m+1), (more generally, A >--> A0 x ... x Am) as formulas in a first order theory. +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ Subject: Paper available From: raymond@fwi.uva.nl (Raymond Hoofman ) Date: Tue, 4 May 1993 11:27:41 +0200 (MET DST) The following paper is available by anonymous ftp: Remarks on the Theory of Semi-Functors R. Hoofman & I. Moerdijk Abstract: "By establishing an appropriate equivalence, we show that the theory of semi-functors can be fully embedded in the theory of (ordinary) functors. As a result, standard properties and constructions on functors extend automatically to semi-functors." FTP instructions: > ftp vera.fwi.uva.nl > Name: anonymous > Password: [your email address] > cd pub/illc/raymond > binary > get rsf.dvi.Z (dvi-format) > get rsf.ps.Z (ps-format) > quit > uncompress rsf.ps > uncompress rsf.dvi With kind regards, Raymond Hoofman. +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ Subject: Categories of relational structures From: Jiri Rosicky Date: Thu, 6 May 1993 15:17:23 +0200 (MET DST) There is a book devoted to these questions: A.Pultr and V.Trnkova, Combinatorial, Algebraic and Topological Representations of Groups, Semigroups and Categories, North Holland 1980. The question whether complete lattices, etc. can be embedded into Str_n depends on what one means under embedd. If it is a full embedding, the problem is set-theoretical. +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ Subject: Categories of relationl structures Date: Thu, 6 May 93 12:10:59 EDT From: es@math.mcgill.ca (Elaine Swan) If I am not mistaken, every small category and every algebraic category can be fully embedded into Str. This seems to follow from old results of the Czech school of category theory, see e.g. J. Algebra 11(1969), 159-212 and references listed there. If my memory does not deceive me, the same is true for every concrete category, provided one accepts Vopenka's Principle. From: Jim Lambek +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ Subject: latest update to ctcs Date: Fri, 7 May 93 08:35:31 EDT From: barr@triples.Math.McGill.CA (Michael Barr) A major update to ctcs is available for anonymous ftp from triples.math.mcgill.ca in /pub/barr under the name ctcsupdate. Both the tex (latex) and dvi files are available. The tex file requires diagram.tex and bezier.sty to run. diagram.tex is in /pub/texmacros. Michael Barr +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ Subject: Terminal coalgebras Date: Fri, 7 May 93 14:40:02 EDT From: barr@triples.Math.McGill.CA (Michael Barr) A new version of my paper, ``Terminal coalgebras in well-founded sets'', now retitled, ``Terminal coalgebras for endofunctor on sets'' is now availiable for anonymous ftp in triples.math.mcgill.ca in /pub/barr/termobj.tex and /pub/barr/termobj.dvi. The version reflects changes that I have made as a result of a several conversations I had with Peter Aczel recently concerning the original version. I mistakenly attributed to him several statements that he apparently did not make in his talk in September, 1989 at the Manchester meeting and which did not appear in the published version of the talk. I apologize for this. In any case, only about a quarter of this paper was on the subject of that talk and that is the only part that has been changed non-trivially. Michael Barr +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ Subject: paper available by ftp Date: Sat, 8 May 93 12:45:36 +0200 From: moggi@diana.disi.unige.it (Eugenio Moggi) ---------------------------- The following paper is available via ftp from Imperial College. The procedure follows the title and abstract A Semantics for Evaluation Logic Eugenio Moggi DISI, Univ. of Genova viale Benedetto XV 3, 16132 Genova, ITALY moggi@disi.unige.it Abstract This paper proposes a topos-theoretic semantic for the modalities and evaluation predicate of Pitts' Evaluation Logic, and introduces several predicate calculi (ranging from Horn sequents to Higher Order Logic), which are sound and complete w.r.t. natural classes of models. It is shown (by examples) that many computational monads satisfy the additional properties required by the proposed semantics. ------------------ ftp theory.doc.ic.ac.uk login: anonymous password: cd /theory/papers/Moggi binary get ELT.dvi.Z -or- get ELT.ps.Z +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ Subject: Announcement of summer school From: TEMPUS Date: Thu, 6 May 1993 09:51:46 +0200 (MET DST) Tempus Summer School for Algebraic and Categorical Methods in Computer Science Second Announcement Brno, June 28 - July 3, 1993 Sponsored by the European Community TEMPUS office the organizers are pleased to announce an intensive course designed to serve its students as a forum for exchange of ideas between the disciplines of mathematics and computer science. Courses: P. J. Freyd (Philadelphia), Cartesian Logic and Cartesian Categories Y. Lafont (Paris), Linear Logic J. Lambek (Montreal), Categories and Deductive Systems C. P. Stirling (Edinburgh), Modal and Temporal Logics for Processes G. Winskel (Aarhus), Models and Logic for Concurrent Computation Special lecture: D. S. Scott (Linz), The Theory of Domains: Origin, Development, Future Lectures will be held starting Monday morning, June 28, to Saturday noon, July 3; Wednesday afternoon is reserved for social activities. Each course will consist of five lectures,one lecture per day. There will be a reception for participants on the evening of Sunday, June 27th. An afternoon-excursion will be organized, followed by a conference dinner. Fees: Conference fee is 220 DM, (tuition 100 DM, accomodation 120 DM). Price includes accomodation in double bedrooms, breakfast and lunch. The tuition fees can be supported by the organizers for a limited number of participants. Please apply! Registration: Please send name, address (including e-mail, if available) and gender to the organizing office by May 20, 1993.Please indicate if you plan to bring a guest or indicate the name of participant with whom you wish to share accommodation. Organizing Committee: Jiri Rosicky Anna Sekaninova Jan Slovak Address: TEMPUS SUMMER SCHOOL Department of Algebra and Geometry Masaryk University Janackovo nam. 2a 662 95 BRNO The Czech Republic e-mail: tempus@queen.math.muni.cs fax: 42-5-74 55 10 (later 42-5-41 21 03 37) phone: 42-5-74 56 66 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ Subject: paper on FTP Date: Mon, 10 May 93 00:39:40 EDT From: pavlovic@triples.Math.McGill.CA (Dusko Pavlovic) A paper on categorical proof theory MAPS II: CHASING PROOFS IN THE LAMBEK-LAWVERE LOGIC by Dusko Pavlovic is available by anonymous FTP from triples.math.mcgill.ca. The file is called mapsII, and there are -A4 and -US formats, in .dvi and .ps files. Please let me know if you have any problems with these files. -- Regards, Dusko Abstract In the Lambek-Lawvere logic, propositions and proofs are presented as objects and arrows in a category. It is the categorical embodiment of the strong constructivist paradigms of propositions-as-types and proofs-as-constructions, which lie in the foundation of computational logic. But a third paradigm arises here, not available elsewhere: the idea of logical-operations-as-adjunctions. It opens a possibility of genuinely categorical proof theory. In the present paper, we study the Lambek-Lawvere version of regular logic: the $\{\wedge,\exists\}$-fragment of the first order logic with equality. The corresponding categorical structure is regular fibration. The examples include stable factorisations, sites, triposes. Regular logic is exactly what is needed to talk about maps, as total and single-valued relations. However, when enriched with proofs-as-arrows, this familiar concept must be supplied with an additional conversion rule, connecting the proof of the totality with the proof of the single-valuedness. We explain the logical meaning of this and describe conditions under which every map in a regular fibration corresponds to a unique arrow in the base category. When this is the case, a natural fragment of generalized regular logic, in the Lambek-Lawvere style, reduces to regular logic of sites. +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ Subject: room mate for UACT meeting? Date: Wed, 12 May 93 17:06:08 +0200 From: ABERNE@dhvrrzn1.uni-hannover.dbp.de Is anybody interested in sharing a residence hall room at the UACT worshop in Berkeley in July? Non-smokers preferred. J"urgen Koslowski c/o aberne@dhvrrzn1.uni-hannover.dbp.de +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ Subject: Preliminary notice of workshop From: H.GUSTAFSON@qut.edu.au Date: Wed, 12 May 93 13:28:16 +1000 Sender: piggy@hilbert.maths.utas.edu.au The following is a preliminary notice of the 1993 Workshop in Categories, Computing and Combinatorics, for your interest: *************************************************************** 3C WORKSHOP 93 CATEGORIES, COMPUTING AND COMBINATORICS September 1-3, 1993 School of Computer Science and Engineering University of New South Wales * Preliminary announcement and call for participation * This is the second in a series of _informal_ workshops exploring the connections between category theory, logic theoretical computer science and algebraic combinatorics. It will provide a forum at which experts and interested workers from outside the field can exchange ideas. The scope of the workshop has been significantly widened. There will be talks in the following general areas: 1. Categorical logic and categorical models of computation (e.g. imperative programming, distributed computing) 2. The role of category theory in computer system design (e.g. object-oriented design, information systems and database theory, design process automation) 3. Applications of category theory to combinatorics and combinatorial topology 4. Algebraic combinatorics and coding theory Our emphasis will be on the connections between different strands of research, and on new ways of thinking about old problems. We hope to promote cross-fertilisation between areas. There will be a series of tutorials on each of these areas during the afternoon of Wednesday, September 1; these will assume only a passing acquaintance with category theory and/or combinatorics. They are meant to provide a suitable background for the more specialised talks on Thursday and Friday. We expect a number of international visitors to be participating: these will include Takayuki Hibi (Hokkaido; algebraic combinatorics) and Patrick Sol\'e (Nice; coding theory). Arrangements for other visitors have not yet been finalised, but they _tentatively_ include Nicoletta Sabadini (Milan), Lin Ying Ming (Szechuan), Eric Wagner (IBM Yorktown Heights) and Rod Burstall (Edinburgh). Anyone is welcome to participate. We intend the talks to be accessible to people without an extensive background in category theory and/or combinatorics; one of our major goals is to make the most recent ideas and results in these areas available to a wider community. In particular we would hope to have a number of industrial participants, as we did last year. Research students are also especially welcome. The programme will be finalised in August. Prospective speakers should contact Amitavo Islam as soon as possible. A limited amount of financial assistance is available to assist speakers travelling from interstate. Organisers: Wesley Phoa (UNSW) general organiser Karl Wehrhahn (Sydney) combinatorics Dominic Verity (Macquarie) category theory Amitavo Islam (Sydney) administration Linda Milne (UNSW) UNSW arrangements This workshop is being run in conjunction with the Software Engineering Research Group (UNSW), the Sydney Category Group, the CATACOMB Group (Sydney) and the Theory Group (Macquarie). - ------------------------------------------------------------- 3C WORKSHOP 1993 -- REGISTRATION FORM Name: _______________________________________________________ Physical address: ___________________________________________ _______________________________________________________ _______________________________________________________ ______________________________ Phone: _________________ Email address: ______________________________________________ I plan to attend the Wednesday tutorials [ ] I would like a delicious and exciting lunch on Thursday ($7) [ ] Friday ($7) [ ] Please attempt to arrange accommodation for me [ ] (Accommodation and lunch arrangements are very tentative at the moment; please do not send any payment yet. We only need an indication of numbers at this stage.) I would like to give a talk entitled ______________________________________________________ (Please contact Amitavo Islam separately; you should be prepared to provide copies of your slides, or a paper, for an informal proceedings volume to be distributed to participants.) (Speakers will get a free lunch.) Send this registration form to wes@cs.unsw.oz.au or Wesley Phoa School of Computer Science and Engineering University of NSW Kensington NSW 2033 ************************************************************************ +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ Subject: coequalisers again From: Paul Taylor Date: Mon, 17 May 1993 13:23:11 +0100 The more I think about coequalisers the less I understand them. DOES ANYONE KNOW of a category in which REGULAR EPIS DO NOT COMPOSE? (Maybe the opposite of the category of commutative rings?) Here is a summary of the results of the previous discussion: I asked what a REGULAR EPI is. I asked this because the observation that all monos in a topos are regular is often made immediately after introducing the subobject classifier, by considering the characteristic map and constantly true. This is not a co-equivalence relation, but regular epis are usually defined in terms of equivalence relations. However if the kernel pair of a map exists, it coequalises this if it coequalises anything, so the definitions agree. You can't do much logic in a category without pullbacks, but Mike Barr and Peter Freyd gave me generalisations which are applicable without them. Categories of algebras were the original examples of REGULAR CATEGORIES. In these there is a factorisation of homomorphisms into regular epis (which are charactersed as surjections) and monos. This is stable under pullback, as is the class of regular epis, and also the class of diagrams which are kernels and coequalisers. Does a regular category have all coequalisers? The definition in the literature is ambiguous, but I am inclined to agree with that in "Categories, Allegories" by Peter Freyd and Andre Scedrov (North Holland 1992), namely that they do not. Although categories of algebras have all coequalisers, and regular epis are stable, coequaliser diagrams need not be. Here is a counterexample in the category of groups given to me by Peter Freyd. 2 --------> 2 2 >-----> 2 2 ---->> 2 ---->> 1 | | | --------> | | | | -- | | | -- | | | -- | | | | | | | V | | V 2 --------> V V 2 >-----> 2 A -------------->> 3 --------> 4 Here 2^2 is the four-element normal subgroup of the group of even permuations on four symbols. The parallel pair consists of the inclusion and the map which interchanges (12)(34) with (13)(24). The equalisers and coequalisers are illustrated and the squares are pullbacks in the obvious way. There are several reasons why I am interested in all of this. One of them is the interpretation of WHILE PROGRAMS using coequalisers of functional relations, which must be stable under pullback. I would like to be able to embed such a category in a topos. There is an obvious Grothendieck topology, and the inclusion sends the coequalising maps to epis, but why should it preserve the coequaliser DIAGRAMS? (For a draft of a paper on while programs, see /theory/papers/Taylor/while-1993.dvi at theory.doc.ic.ac.uk) The other reason is an application to SYNTHETIC DOMAIN THEORY. See my paper in LICS 1991 (also /theory/papers/Taylor/lics.dvi) for the background. Eugenio Moggi asked for a good class of monos (see /theory/papers/Moggi/ELT.dvi) and I was trying to show that what I called "extremal" monos in my LiCS paper coincided with those which arise as equalisers of parallel pairs into powers of Sigma. Somewhat to my surprise, I discovered yesterday that in any category with kernel pairs and coequalisers of them (NOT NECESSARILY STABLE), a map is mono iff it is orthogonal to all regular epis where "orthogonal" means that the universal property for factorisation systems is satisfied. Moreover if regular epis compose, (reg.epi)-(mono) is a factorisation Hence the question above. Stability of regular epis is sufficient but not necessary to make them compose. For SDT I am specifically interested in "Sigma-epis" instead of monos (maps which internally satisfy the cancellation property for parallel pairs into the object Sigma, rather than all objects). For reasons concerned with Eugenio Moggi's Evaluation Logic, we want Sigma-regular monos to be "topological subspaces", ie that maps to Sigma extend along the mono. This is also sufficient to make regular monos compose. Paul Taylor +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ Subject: Workshop on Foundational Methods in Computer Science Date: Tue, 18 May 93 07:59 PDT From: hook@hood.cse.ogi.edu (Jim Hook) **** FMCS UPDATE **** REGISTRATION DEADLINE **** In my first announcement I neglected to specifiy that I need a firm count on rooms and meals by Monday, May 24. Please send email registration forms by Sunday, April 23, to Kerri Crockett (crockett@cse.ogi.edu). - Jim Hook FMCS93 **** Announcement and Registration **** Foundational Methods in Computer Science: A workshop on applications of categories in computer science 1993 June 4--6 Reed College, Portland, Oregon Sponsored by the Computer Science and Engineering Department at Oregon Graduate Institute of Science & Technology and the Department of Mathematics at Reed College. This workshop is an informal, casual meeting to bring together researchers in mathematics and computer science with a focus on the application of category theory in computer science. It is a three day meeting. On Friday, June 4, we will have tutorials on category theory. On Saturday and Sunday we will have research meetings. The workshop will end at noon on Sunday. All sessions will be held on the Reed campus which is quiet, beautifully landscaped, and adjacent to a park and a public golf course. The registration fee is $60 for regular registration and $45 for students. Registration includes breakfasts, refreshments, breaks and a Chinese buffet. Dormitory accommodation is available at $3.50 + $20 per night (three nights = $63.50). Preliminary Schedule highlights: (Assignment of talks to sessions may change!) Thursday 6/3: 1800 - 2100 Registration and reception Friday 6/4: Tutorials Sessions I and II: Elementary category theory David Benson and Bob Walters Session III: Binding Monads to Program Blocks Ernie Manes Session IV: Sketches Charles Wells Saturday 6/5: Research sessions Session V: Monads & Kleisli Phil Mulry Dick Kieburtz Session VI: Charity Robin Cockett What happened to charity? Tom Fukushima More on monads Todd Simpson Distributive logic Session VII: Vaughan Pratt The Symmetry of Satisfaction in Much More Detail Session VIII: Concurrency Dave Spooner The Category of Protocols Bob Walters Concurrency and Distributed Processing Sunday 6/6 Session IX: Charles Wells and Atish Bagchi Rules of Inference for Sketches Session X: Type theory and Recursion theory Several people have tentatively suggested titles along this theme. The workshop is happening during the Portland Rose festival. Highlights of the festival during the workshop include: 6/3 Coronation 6/4 Fireworks spectacular 6/4-6 Rose Festival Carnival on Waterfront 6/4-5 Golf Classic 6/5 Starlight Parade/Run A friend who did the run last year reports that it is quite a sight with thousands of people running! ** Registration ** DUE May 23! Please send registration information via email to crockett@cse.ogi.edu. Advance payment is preferred. Checks should be payable to Oregon Graduate Institute and should reference FMCS93. They should be mailed to: FMCS93 (Kerri Crockett) Computer Science and Engineering Oregon Graduate Institute 19600 NW von Neumann Dr. Beaverton, Oregon 97006 Name: Affiliation: Address: email: phone: registration fee (regular = $60, student = $45): _______ Vegetarian banquet meal? (yes/no) presentation? (yes/no) title: likely session: Accommodation: dorm rooms: (list nights needed) cost = $3.50 + ____ nights * $20 = $__.50 If you want to stay off campus please make those arrangements on your own. Extra Banquet tickets ($25/person): A few people suggested that it would have been fun to have a T-shirt from last year's workshop. Would you be interested in buying a T-shirt on site when you arrive? If so, what size? (Don't send money for T-shirts with your registrations!) ** Questions? ** If you have any questions or comments, please contact Jim Hook or Kerri Crockett at OGI. James Hook hook@cse.ogi.edu Phone: (503) 690-1169 Fax: (503) 690-1553 Kerri Crockett crockett@cse.ogi.edu Phone: (503) 690-1640 Department of Computer Science and Engineering Oregon Graduate Institute of Science & Technology 19600 N.W. von Neumann Drive Beaverton, OR 97006-1999 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ Subject: re: coequalisers again (note from moderator: several posts in reply to Paul's question follow, the delay in resending is due to my absence and a local shutdown - Bob) From: "G.M. Kelly" Date: Wed, 19 May 1993 20:14:51 -0300 Paul Taylor should look at my very old paper "Monomorphisms, epimorphisms, and pull-backs", J.Austral.Math.Soc. 9 (1969), 124-142. There he will find counter-examples as well as theorems. Max Kelly. +++++++++++++++++++++++++++++++++++ Date: Wed, 19 May 93 19:15:23 EDT From: barr@triples.Math.McGill.CA (Michael Barr) Ragular epis that do not compose: In Cat, which is complete and cocomplete and is even tripleable over a category (graphs) tripleable over sets, regular epis do not compose. Let 2 be the category with two objects and one non-identity arrow from one to the other. Let N be the category with one object and a natural numbers of maps. Let N_2 be the category with one object and 2 arrows, one an identity and the other idempotent. The obvious map from N to N_2 is obviously a regular epi and so is the map from 2 to N that identifies the objects, but the composite is not. Michael ++++++++++++++++++ From: pavlovic@triples.Math.McGill.CA (Dusko Pavlovic) > DOES ANYONE KNOW of a category in which REGULAR EPIS DO NOT COMPOSE? > (Maybe the opposite of the category of commutative rings?) I don't suppose that this is what you mean, but isn't already something like --0--> --a--> --f--> --1--> --b--> a0=a1, fa=fb providing an answer to the question as it stands? - Dusko ++++++++++++++++++++++++++++++++++++++++++++++++ Date: Thu, 20 May 93 10:28:54 -0700 From: Art Stone Subject: an answer to Paul Taylor's question Paul Taylor asks for a category in which REGULAR EPIS DO NOT COMPOSE. The short answer is |Cat . (Where |x denotes boldface-x, look at the canonical presentation, which has length two, of |3 in terms of free categories over sets, i.e., coproducts of copies of |2. The intervening algebras in this presentation are free categories over graphs.) In slightly greater generality, how do we produce examples of categories in which there are chains of length n of regular epis -- whose composites cannot be written as composites of fewer than n regular epis (for each n > 1) ? When I worried about this several decades ago, Peter Freyd gave an answer, in his essentially equationally defined categories [e.g., in the early pages of his Aspects of Topoi] -- defined by equations on a set of partial as well as entire operations -- in which the operations can be ordered so that for each partial operation its domain is defined by equations in earlier operations. |Cat is an example when n = 2. This leads into the subject of adjoint towers [Applegate-Tierney, LNM 137; Adamek-Herrlich-Rosicky c.1987] To get a tower of height n over |Sets^m (for any m ) there must be n batches of progressively "higher" operations, each requiring the last of the preceding batches, in the definitions of its domains. For the |Cat example, the intervening category is directed |Graphs. The base category is respectively |Sets or |Sets^2 , when we use the usual one-sorted or two-sorted definition of "category". And if we define "category" in terms of (commuting) "triangle", in place of "morphism", then the tower degenerates -- after the pattern of the main theorem of Gabriel-Ulmer [LNM 195 and LNM 221]. Now, if |Cat is interesting in this way, what does it mean that |Cat is a topos wrt categories enriched over it [as remarked by Ross Street several months ago here on the catnet], and what modifications are we going to be compelled to make when we attempt to carry topos-style thinking from |Sets over to |Cat? Talk about WHILE programs suggests talk about imperative languages. Perhaps more important, even, than their dealing with STATE is the way imperative languages can be explicit about extending or shrinking storage (using pointers). Manes and Moggi have shown us how monads can be used to model STATE and given us a category theoretic translation of the distinction between call-by-value and call-by-name [begin with Moggi's paper on theory.doc.ic.ac.uk]. Is there also a 2-category theoretic translation of the distinction between call-by-value and call-by-reference, that depends on the difference between the two kinds of composition we have in 2-categories? Here I doubt if the base 2-category can be |Cat. But |Cat (x) |Cat remains a possibility, where (x) denotes Gray's assymetric tensor product [LNM 391 and in the Heller-Tierney (ed.) Eilenberg festschrift]. Art Stone +++++++++++++++++++++++++++++++++++++++++++ Date: Thu, 20 May 93 14:17:35 EDT From: Walter Tholen Subject: Coequalizers Regarding Paul Taylor's question, here are some useful references that contain answers: G.M. Kelly, Monomorphisms, epimorphisms, and pullbacks, J. Austral. Math Soc. 9 (1969) 124-142. (Mentions an example of a complete,cocomplete, wellpowered, cowellpowered additive category due to Isbell in which reg. epis do not compose. The following articles deal with long chains of regular epis; this is a selection only:) J. MacDonald and A. Stone,The tower and regular decomposition , Cahiers TGDC 23 (1983) 197-213 R. Bo"rger and W. Tholen,Total categories and solid functors, Can. J. Math 42(1990) 213-229 (see sections 4 and5) J. Adamek and W. Tholen, Total categories with generators, J. of Alg. 133 (1990) 63-78 (see section 1) R. Bo"rger, Making factorizations compositive, Comm. Math. Univ. Carolin. (1991) 749-759 (see section 3). The last article mentions one remaining problem on the composition- cancellation behaviour of regular epis in a category (with kernel pairs and their coequalizers, say): consider the properties (A) and (B): (A) if e is split epi and d is regular epi, then the composite ed of first d and then e is regular epi, (B) if a composite ed is regular epi, then e is regular epi one always has that if (A) holds in our category, then also (B) holds. But what about the converse? (Note that neither property holds true in general, already Kelly's paper contains a counter-example.) Regards, Walter Tholen +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ Subject: re: coequalisers again From: Paul Taylor Date: Sat, 22 May 1993 14:59:33 +0100 Thanks to Art Stone in particular and also Mike Barr, Max Kelly, Dusko Pavolovic and Walter Tholen for their helpful comments, which I still have to study. I wonder whether any specialists in group theory or commutative algebra might be able to find a single example of non-composing regular monos in the category of groups or of commutative rings. Something like: (1) a normal subgroup of a centraliser in a simple group, or (2) A chain of subrings R Paul Taylor (pt@doc.ic.ac.uk) asks: > I wonder whether any specialists in group theory or commutative algebra > might be able to find a single example of non-composing regular monos > in the category of groups or of commutative rings. Alas, every inclusion of a subgroup (monomorphism of groups) is an equalizer "for free" (a regular monomorphism), so there's no example of the desired sort in {Groups} . (The argument I know is one I learned from Eilenberg several decades ago; it uses a suitable permutation group as the target of two homomorphisms (from the larger group) whose equalizer is precisely the given subgroup. Cheers. -- Fred +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ Subject: re: coequalisers again From: Reinhard Boerger Date: Tue, 25 May 1993 16:44:43 -0400 It has been known for a long time that all monomorphisms in the category of groups are regular, therefore the regular monos compose. I do not know who proved it first. It can be shown directly by representing any inclusion map, say from H to G, as an equaliser of two arrows from G to the group of all bijections from the set of all left cosets modulo H to itself. Another way is to look at the usual descriptions of amalgamated products (i.e. poushouts of pairs of monos); then every mono m can be seen to be the equaliser ofthe two maps forming the pushout of m with itself. In the category of rings (commutative or not, unital or not), regular monos do not compose. The problem is stdied in detail in John Isbell's paper "Epimorphisms and dominions", La Jolla Proceedings, 1965. Similar arguments work for monoids or semigroups. A nice and easy, but seemingly not very well-known example is given by Gabriel and Ulmer (LNM 221): let N be the additive monoid of non-negative integers, let A be the submonoid generated by 3 and 5 and B the submonoid generated by 3, 5, and 7. Then the inclusions from A to B and from B to N can easily be see to be regular monos, but their composite is not, due to the following nice computation: assume f(3)=g(3) and f(5)=g(5) for some morphism from N to some monoid (multiplicatively written). Then f(7)=f(2)f(5)=f(2)g(5)= f(2)g(3)g(2)=f(2)f(3)g(2)=f(5)g(2)=g(5)g(2)=g(7). Gabriel and Ulmer also prove the (now?) well known fact that in any category with finite limits regular epis compose, if they are stable under pullback, and they even state their result more generally. Only recently, I realized that their result easily implies that the class of regular epimorphisms stable under pullback (i. e. of all morphisms e such that every pullback of e is a regular epi) is aways closed under compostion, even if regular epis do not compose. Greetings Reinhard Boerger +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ Subject: coequalisers & visit From: Paul Taylor Date: Wed, 26 May 1993 17:14:12 +010 Thanks for sending me exactly the kind of counterexample I need for my foundations book. It will do very nicely as an exercise in the section on factorisation systems. I shall have to think a bit more about the one involving presentations of categories which Art Stone and others mentioned. I am coming to Canada for LiCS in Montreal next month. My flight plan is to arrive in Toronto on Saturday 12 June and return from Montreal (via (!!) Toronto) after LiCS. I wonder whether the people at York would like to hear a seminar from me in return for some local accommodation for a few days? Several subjects are on offer: stable domain/category theory (see the papers in my ftp archive, which I think soem of you already have), intuitionistic ordinals, synthetic domain theory, as you please. Paul Taylor +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ Subject: linear topology, hopf algebras and *-autonomous categories Date: Fri, 28 May 93 14:57:23 EDT From: blute@triples.Math.McGill.CA (Richard Blute) The following paper is available by anonymous ftp from the site triples.math.mcgill.ca. It is in the file pub/blute in dvi and ps format(compressed). Anyone who would like the paper and cannot access it this way can of course contact me. Regards, Rick Blute LINEAR TOPOLOGY, HOPF ALGEBRAS AND *-AUTONOMOUS CATEGORIES Richard F. Blute McGill University Abstract The goal of this paper is to construct models of variants of linear logic in categories of vector spaces. We begin by recalling work of Barr, in which vector spaces are augmented with linear topologies to obtain new examples of symmetric monoidal closed (autonomous) categories. The advantage of these categories is that they have large subcategories of reflexive objects which are also autonomous, in fact *-autonomous. Thus, we obtain models of (a fragment of) classical linear logic. These models have an advantage over other models arising from linear algebra in that they do not identify the two multiplicative connectives, tensor and par. Furthermore, the models will be complete and cocomplete. We then extend Barr's work to vector spaces with additional structure, in particular to representations of Hopf algebras. As special cases, we examine cocommutative Hopf algebras, and quasitriangular Hopf algebras, also known as quantum groups. In the quasitriangular case, the representations actually form a braided *-autonomous category, first defined by the author. They thus give a model of a braided variant of linear logic, also defined by the author. This is the first example of such a model which does not identify the two multiplicative connectives. Hopf algebras, and more generally bialgebras, have been of interest recently as a possible framework for the study of concurrency, in that they encode the paradigm of interleaving processes, also known as fair merge, as well as other structural operations on concurrent processes. This was first observed by D. Benson. As a result of the work in this paper, such bialgebras will yield models of a fragment of linear logic. While these models do not equate the multiplicative connectives they do validate the MIX rule, thus giving models of a slightly larger theory, first studied by Fleury and Retore. Also, if additional restrictions are placed on the Hopf algebra, we obtain models of cyclic linear logic, defined by Yetter. +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ Subject: Zariski Categories Date: Sat, 29 May 93 13:23:26 -0400 From: "Allan Adler" I'm looking at the book Categories of Commutative Algebras, by Yves Diers. Before plunging into the details, I'm wondering about a couple of things: (1) Does Grothendieck's theorem about faithfully flat descent work in the setting he develops? (2) What he calls algebraic spaces seem more like "bunches of varieties". The terminology "algebraic spaces" as used by Artin means something else. So does the notion of algebraic space in the sense of Artin have a place in this generalization? Allan Adler ara@altdorf.ai.mit.edu +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ Subject: Re: coequalisers & visit From: Paul Taylor Date: Thu, 27 May 1993 15:32:11 +0100 Apologies for broadcasting a message which was intended to be a personal reply! Paul Taylor +++++++++++++++++++++ note from moderator: and my apology to Paul that the usual intercept failed; my instructions to the person temporarily minding the list were incomplete. Bob +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ Subject: 2-category algebras? Date: Sat, 29 May 93 23:09:51 PDT From: baez@ucrmath.ucr.edu (john baez) We all know about group algebras, and this leads naturally to the idea of a category algebra: form a vector space having as a basis the morphisms in a given category, with the obvious product (taking the product of two morphisms to be zero if the head of one isn't the tail of the other). I used an example of this in my paper "Quantum Gravity and the Algebra of Tangles," but I have never seen a reference to the general concept, and I would appreciate one. What I am now interested in, however, is generalizing this notion to 2-category algebras. This might be related to recent algebraic work of Ruth Lawrence, which I haven't actually seen. Any leads? Regards, John Baez