From cat-dist@mta.ca Ukn Jan 3 15:36:39 1994 Received: from bigmac.mta.ca by nimble.mta.ca (5.65/DEC-Ultrix/4.3) id AA09195; Mon, 3 Jan 1994 15:36:37 +0400 Date: Mon, 3 Jan 1994 14:53:57 +0400 (GMT+4:00) From: categories Subject: (not entirely) routine distribution To: categories Message-Id: Mime-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Status: RO X-Status: *************************************************************************** * * * * * Change in Originating Machine for categories list. * * * * * *************************************************************************** With this posting the originating machine for categories changes (to nimble.mta.ca [138.73.1.253].) It is hoped that the change will be seamless, but please bear with us if there are some short-term glitches. There is NO CHANGE in address for the list, nor in the categories-request@mta.ca alias which should now be working. The only changes you should notice are in the `From:' and `To:' fields of a posting: - the `From:' field will now read `categories '; - the `To:' field will now read `categories ' (and not your personal address as has been the case.) You may also note some other changes in the mail-header as you receive it. This is a good time to remind you that a direct reply to a message from categories goes to the list, NOT the originator of the message. Thus it will be posted unless the moderator clearly understands a different intent. Please inform me of any problems you experience. The usual routine distribution follows. ( ... and Happy New Year to all.) Bob Rosebrugh +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ This is the routine distribution for the categories mailing list. It is the file routine.dist in pub/categories at sun1.mta.ca and was last updated on January 2, 1994. Subscribers should note that the From: field of a categories posting is categories (this is different from some other mailing lists, and Usenet newsgroups.) Thus if you reply directly to a posting it will be redirected to the entire list (unless another intention is clearly detected by the moderator). Administrative items (address changes etc.) can be sent to categories-request@mta.ca or directly to the moderator. Usually, items of this sort sent to categories@mta.ca will not be posted. The archives of postings on categories are held at the ftp site sun1.mta.ca (138.73.16.12) in the directory pub/categories. This is a Unix system. The postings are filed in yearly subdirectories called 90, 91 etc. Within those subdirectories there are monthly files, and an annual list of dates and subjects of postings. In the pub/categories directory there is also a file called ftp.sites with information about ftp sites holding files of interest to subscribers. Several TeX diagram macro packages are in the subdirectory macro. Information about ftp sites with holdings of interest is solicited. If you need detailed instructions on how to use ftp, ask anyone knowledgable about the Internet at your site, or write to me. Bob Rosebrugh Phone: +1-506-364-2538 Department of Mathematics and Computer Science Fax: -2210 Mount Allison University Sackville, N. B. E0A 3C0 InterNet: rrosebrugh@mta.ca Canada From cat-dist@mta.ca Ukn Jan 3 22:18:43 1994 Received: from bigmac.mta.ca by nimble.mta.ca (5.65/DEC-Ultrix/4.3) id AA00220; Mon, 3 Jan 1994 22:18:42 +0400 Date: Mon, 3 Jan 1994 21:40:51 +0400 (GMT+4:00) From: categories Subject: doctoral scholarship To: categories Message-Id: Mime-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Status: RO X-Status: Date: Tue, 4 Jan 1994 12:45:53 +1100 From: Barry Jay Doctoral Scholarship School of Computing Sciences University of Technology, Sydney ************************************************** *** Funding is now available for three years *** ************************************************** The scholarship is linked to the "Shape" project, whose goal is to design and implement an efficient, typed programming language for vectors, matrices, and other data structures, based on the separation of data from shape. The project combines both the development of the theory of shapely types with their incorporation in a programming language. The project is based at UTS, but has participants in Calgary and Edinburgh. Applicants will have completed an undergraduate degree at the Honours level. They should also have experience in programming language implementation or semantics, or in category theory. The stipend is $18,679. Funding is for three years, subject to review after the first year. Applicants who are Australian citizens, or permanent residents who have lived continuously in Australia for the last twelve months, would not be required to pay student fees, or taxes on the stipend. For further information, contact Barry Jay (cbj@socs.uts.edu.au). Applications should contain a curriculum vitae and the names, addresses, phone numbers and e-mail of two or three referees from whom confidential reports can be obtained. They should be sent to: Dr C. Barry Jay School of Computing Sciences University of Technology, Sydney PO Box 123 Broadway Australia 2007 Ph: (02) 330-1814 for receipt by 21st January, 1994. From CATEGORIES@mta.ca Ukn Jan 11 19:19:43 1994 Received: from macc2.mta.ca by nimble.mta.ca (5.65/DEC-Ultrix/4.3) id AA01633; Tue, 11 Jan 1994 19:19:41 +0400 Date: Tue, 11 Jan 1994 19:26:14 -0400 (AST) From: CATEGORIES@mta.ca To: rrosebrugh@macc2.mta.ca Message-Id: <940111192615.2040f68c@mta.ca> Subject: strict epi(morphic) family Status: RO X-Status: Date: Tue, 11 Jan 94 13:41:41 +0100 From: Thomas Streicher Does anybody know what is meant by "strict epi" or "strict epimorphic family" ? Maybe it's standard but I couldn't find it in any book available to me ! Thomas Streicher From CATEGORIES@mta.ca Ukn Jan 11 20:56:17 1994 Received: from macc2.mta.ca by nimble.mta.ca (5.65/DEC-Ultrix/4.3) id AA15952; Tue, 11 Jan 1994 20:56:15 +0400 Date: Tue, 11 Jan 1994 19:49:51 -0400 (AST) From: CATEGORIES@mta.ca To: rrosebrugh@macc2.mta.ca Message-Id: <940111194951.2040fea4@mta.ca> Subject: Letter re: The Death of Proof Status: RO X-Status: Note from moderator: Jim sent me a copy the following letter in December, and I received it only last week, with a note mentioning that colleagues suggested it be circulated. The subject is still current despite the further delay awaiting retyping of the letter. Bob Rosebrugh. ++++++++++++++++++++++ Date: Tue, 11 Jan 1994 9:48:00 -0400 (AST) From: Jim Lambek October 18, 1993 The Editor Scientific American, Inc. 415 Madison Avenue New York, NY 10017 USA Dear Sir: As much as I enjoyed reading ``The death of proof'' by John Hogan [October 1993], I feel I should take exception to the statement attributed to Thurston that Godel's incompleteness theorem implies that ``it is impossible to codify mathematics.'' This may be the view accepted by most mathematicians, and perhaps by Godel himself, but it depends on the assumption, implicit in Godel's argument, that the universe of mathematics (by this I mean whatever is described by the language of mathematics) obeys the following principle: if a formula A(x) becomes true when x is replaced by a numeral S ... S0 (successor of ... successor of zero), then the universal statement `for all numbers x, A(x)' is true. This principle is indeed accepted by most mathematicians, but not by intuitionists, followers of L.E.J. Brouwer, who believe in the truth of the universal statement only if the special instances can be seen to be true in a way that is uniform as regards the number of times the successor symbol S appears. How can such an intuitively evident principle fail to hold? Well, intuitionists do accept the following modified principle: if the existential statement `for some number x, B(x)' is true, then some special instance B(S ... S0) must be true. This looks very much like the principle they rejected, but the two principles are only equivalent according to the rules of classical, not intuitionistic, logic. So, what is the universe of mathematics? If we take the language of mathematics to be some form of intuitionistic type theory, we would hope that, among the models of this language, there is a preferred one, call it the universe of mathematics. Indeed, such a model can be constructed from the language itself, and it satisfies the above principle in its modified form. That it does not satisfy the original principle is, in fact, what Godel proved. For classical type theory, no one has yet constructed a preferred model, or any model for that matter, although many such models can be shown to exist in the classical, but not intuitionistic, sense of ``existence.'' Jim Lambek Montreal, Quebec From CATEGORIES@mta.ca Ukn Jan 11 22:38:16 1994 Received: from macc2.mta.ca by nimble.mta.ca (5.65/DEC-Ultrix/4.3) id AA23811; Tue, 11 Jan 1994 22:38:15 +0400 Date: Tue, 11 Jan 1994 19:20:09 -0400 (AST) From: CATEGORIES@mta.ca To: rrosebrugh@macc2.mta.ca Message-Id: <940111192009.2040f573@mta.ca> Subject: Sydney Bushfires Status: RO X-Status: Date: Tue, 11 Jan 94 14:22:20 +1100 From: street@macadam.mpce.mq.edu.au Dear CATEGORIES Many of our kind colleagues have been concerned for the safety of Sydney category theorists. I have had many enquiries by email and phone. We are all safe and without loss of personal property, to the best of my knowledge. The fires have been the worst in New South Wales post european settlement, as far as the area covered and number of fire fronts at one time. Because of the remarkable efforts of the fire fighters (many voluntary, from all over Australia & even some from New Zealand), the death toll was kept down to around 5, including 2 fire fighters, and there were 180 houses lost. Of course, there were many injuries and other property losses. The Royal National Park south of Sydney was 95% burnt; much will begin to regenerate with the next rain, but many animals are dead and the rainforest regions will take 250 years to return to the state they were in last week. The fire is still not dead. Last Thursday during lunch with Todd Trimble (our new Research Fellow from Rutgers) at the Macquarie University Union we saw the beginning of the fire in Lane Cove National Park. This was responsible for the loss of many homes around South Turramurra, West Pymble, West Killara and West Pymble. During lunch with Todd on the Friday, helicopters began taking water from a small lake near the Union building to dump on the fire. Macquarie Centre (a nearby shopping mall) was evacuated on Friday evening as was the Graduate School of Management; but these were all saved. The Kuring-gai Campus of the University of Technology, Sydney, in Lindfield had considerable fire damage (my wife, Margery, has done various courses there). Our Head of School, the number theorist Alf van der Poorten, was one small block away from destroyed houses and bushland. This fire is essentially dead now. The fire in the Blue Mountains west of Sydney rages on out of control, but the efforts to save settlements by backburning and fire fighting have mostly succeeded. The fire in Kuring-gai National Park north of Sydney has charged back and forth with the wind. It destroyed houses on the Pittwater Penninsula on Saturday during the westerly winds then headed back south west with the change of wind on Sunday. Margery was working Sunday afternoon at Belrose Library; as soon as she arrived (by a non-standard route because of road closures just north of Max Kelly's house on Mona Vale Road), Belrose hit the news as the centre of activity. Luckily it stayed north of the Library. But the northern parts of St Ives (Max's suburb), Turramurra (my suburb) and Wahroonga (Bob Walter's suburb - Bob is in Milan, however) were warned to prepare for evacuation. A large nursing home was evacuated. Cooler conditions saved the day. The fire is still active. Yesterday there was some rain which hampered backburning efforts a bit; it was not enough to put out fires, but the overcast conditions and increased humidity helped. Today is still fairly cool (31 degrees C predicted maximum for Sydney) and more humid. Throughout it all, life goes on. In fact, life began. Another beautiful daughter (9lb 12oz), Florence, arrived 'midst the flames on Friday for Dominic and Sally Verity. Other personal news: Bart Jacobs is visiting Macquarie. His wife, Joke, was here, but left last Friday returning to Utrecht. Awaiting her at Amsterdam airport were reporters seeking news of the fires. Joke was on Netherlands National TV. Also, Mike Johnson's student, Richard Buckland is building a house in a little part of the Hawkesbury River (north of Sydney) with only access by boat. Foundations, and floorboards were in place. Last weekend he was going to put up walls, and a lot of wood was at the site. He made several attempts to visit the site over the weekend but was turned back. The good news is that everything is untouched by fire, although it had gone close. Today (Tuesday) is now quite hazy and smokey. Hotter weather is predicted. We are told not to become complacent. Finally, I thought you might find of interest the following letter to the newspaper written by my (22 years old tomorrow) son, Arthur: -------------------- \documentstyle[12pt,a4wide]{letter} \begin{document} \signature{Arthur Street\\32 Katina St\\Turramurra 2074} \begin{letter}{ Letters Editor\\ GPO Box 3771\\ Sydney 2001} \opening{Dear Editor,} In the wake of the bushfires I was intrigued to see the media performing its usual post-crisis contortions in an attempt to find people to blame for the destruction. I can't help but feel that no matter how much we backburn and no matter how draconian the penalties for flicking cigarette butts out car windows, bushfires are inevitable and always have been. As was mentioned by the {\em Herald} recently, Captain Cook was flabbergasted by the number of fires he saw raging up and down the east coast of Australia. Therefore I propose that, rather than blaming individuals and dare I say the greenies, we should blame our forebears for imposing on this `continent of fire' a foreign culture not suited to the conditions. Instead of concreting over the last of our urban bushland, which no doubt some development-motivated doom-mongers will be advocating, the housing developments at the fringes of Sydney should be built to withstand the worst of our bushfires. Perhaps they could be built largely underground, which would also provide a cheap form of temperature control. Who knows, if it were to catch on, the resulting unique architecture could help to forge the Australian identity of the 21st century. \closing{Yours sincerely,} \end{letter} \end{document} ------------------- Best regards, Ross From CATEGORIES@mta.ca Ukn Jan 12 23:52:14 1994 Received: from macc2.mta.ca by nimble.mta.ca (5.65/DEC-Ultrix/4.3) id AA22248; Wed, 12 Jan 1994 23:52:13 +0400 Date: Wed, 12 Jan 1994 23:54:32 -0400 (AST) From: CATEGORIES@mta.ca To: rrosebrugh@macc2.mta.ca Message-Id: <940112235432.20410a57@mta.ca> Subject: question on homotopies Status: RO X-Status: Date: Wed, 12 Jan 94 13:16:22 EST From: Michael Barr In the category of chain complexes (over some abelian category) it is clear that if you identify homotopic arrows, you will also invert homotopy equivalences. Does anyone know if the converse is true? If you invert homotopy equivalences, do you wind up identifying homotopic arrows? What if you replace homotopy by homology? Does inverting maps that induce isomorphism on homology have the effect of identifying maps that induce the same map on homology? Michael From CATEGORIES@mta.ca Ukn Jan 12 23:52:22 1994 Received: from macc2.mta.ca by nimble.mta.ca (5.65/DEC-Ultrix/4.3) id AA22283; Wed, 12 Jan 1994 23:52:21 +0400 Date: Wed, 12 Jan 1994 23:55:02 -0400 (AST) From: CATEGORIES@mta.ca To: CATEGORIES@mta.ca Cc: pratt@cs.stanford.edu Message-Id: <940112235502.20410c64@mta.ca> Subject: An object of formulas Status: RO X-Status: Date: Wed, 12 Jan 94 19:38:12 -0500 From: "Charles F. Wells" This message concerns the idea that one could carry out the usual construction in classical logic of formulas, terms, theories, interpretations, and so on in a suitable category that has recursion. Formulas, terms and proofs are all inductively defined, after all. For example, one might have an object of formulas that is the solution of a recursion problem and an arrow "interpretation" (also the solution of a recursion equation) from that object to a category object. I believe I recently saw a paper that does something like this, but I can't remember it and can't find it. Although I saw it recently, it may not be a recent paper; I believe I came across it in the process of accumulating papers for my outline of sketches. Anyone know of any work like this? -- Charles Wells, Department of Mathematics, Case Western Reserve University 10900 Euclid Avenue, Cleveland OH 44106-7058, USA Phone 216 368 2880 or 216 774 1926 FAX 216 368 5163 From CATEGORIES@mta.ca Ukn Jan 13 02:31:22 1994 Received: from macc2.mta.ca by nimble.mta.ca (5.65/DEC-Ultrix/4.3) id AA19277; Thu, 13 Jan 1994 02:31:20 +0400 Date: Wed, 12 Jan 1994 23:54:31 -0400 (AST) From: CATEGORIES@mta.ca To: rrosebrugh@macc2.mta.ca Message-Id: <940112235432.20410c59@mta.ca> Subject: re: strict epi(morphic) family(3 responses) Status: RO X-Status: Date: Tue, 11 Jan 94 18:11:05 EST From: Walter Strictly epic families (of morphisms with common codomain) are used in SGA4. I used them again in my paper with Reinhard Boerger in the Cahiers (vol 32, 1991, pp257ff) which contains exact definitions and a bit of discussion. In the case of singleton families, these are regular epis in the sense of Gabriel-Ulmer and of Kelly. I hope that this answers Thomas Streicher's question. Walter Tholen. ++++++++++++++++++++++++++++++++++++++++++++ Date: Tue, 11 Jan 94 17:07:51 EST From: Michael Barr It is, to my knowledge standard and is identical to extremal epi or extremal epimorphic family. For one, it means it factors through no proper subobject of the codomain. For a family, all with the same codomain, it means there is no proper subobject of the codomain that factors all of them. In a regular category, a strict epi is regular. In a wide complete category (every class of subobjects has an intersection), a strict epi is in a certain sense a composite of a class of regular epis. You may need cokernel pairs to do that. I don't know any such simple characterization for families. Michael +++++++++++++++++++++++++++++++++++++++++++ Date: Wed, 12 Jan 94 09:52:25 +0100 From: Markus Wolf > Date: Tue, 11 Jan 94 13:41:41 +0100 > From: Thomas Streicher > Does anybody know what is meant by "strict epi" or "strict epimorphic > family" ? > Maybe it's standard but I couldn't find it in any book available to > me ! > Thomas Streicher Hmm, not quite sure, but in the book "Category Theory, An Introduction" by H. Herrlich and G. Strecker there is a definition of strict mono in the exercises. According to this text a strict monomorphism is a morphism $f$ such that: whenever $h$ is a morphism with the property that for all morphisms $r$ and $s$, $r\circ f= s\circ f$ implies that $r\circ h=s\circ h$, then there exists a unique morphism $k$ such that $h=f\circ k$. Probably you get a strict epi if you modify the condition according to the property of epimorphisms being righ-cancellable instead of left-cancellable. There was no reference to "strict monomorphic family" :( Markus Wolf From CATEGORIES@mta.ca Ukn Jan 13 03:38:59 1994 Received: from macc2.mta.ca by nimble.mta.ca (5.65/DEC-Ultrix/4.3) id AA26181; Thu, 13 Jan 1994 03:38:58 +0400 Date: Wed, 12 Jan 1994 23:54:32 -0400 (AST) From: CATEGORIES@mta.ca To: rrosebrugh@macc2.mta.ca Message-Id: <940112235432.20410e5a@mta.ca> Subject: Re: Letter re: The Death of Proof Status: RO X-Status: Date: Tue, 11 Jan 94 22:13:52 PST From: pratt@cs.stanford.edu I am very much in favor of constructive logic in the sense of proof in lieu of truth. This replaces truth-valued entailments, that is, implication as a preordering of propositions, with set-valued entailments, that is, implication as homsets whose elements are interpreted as proofs, or moves in a space of perspectives. This branch of logic is a rich application area for category theory, whose cartesian closed fragment is nicely developed in Jim and Phil's book. To the same degree, I am opposed to the mysticism implicit in the traditional "it may sound the same but it's provably different" defense of propositional intuitionism. Goedel defused this argument along lines that can be made quite pragmatic as follows. Intuitionistic arithmetic is just classical arithmetic with some "surely"'s strategically placed in the wording of some theorems, where "surely" abbreviates "not not". Real-world customers of mathematics pay no attention to these "surely"'s, for the simple reason that, while they know full well what to do with the theorems, they have no idea to what use to put the "surely"'s. No engineering project has ever been made one whit more hazardous by casual neglect of "surely"'s appearing in its intuitionistically correct arithmetic. Deriving those theorems classically yields no more than what can be obtained by treating all the "surely"'s in the intuitionistic derivations as noise words to be ignored. From the point of view of correctness then, "surely" is merely harmless. From a computational point of view a marginally more concrete statement is possible. Dropping "surely" from pure propositional logic reduces the computational complexity of its satisfiability problem from PSPACE-complete (Statman) to NP-complete (Cook). Thus "surely," and hence intuitionism in the permitted-middle sense, does nothing to render the propositional content of an argument any easier to follow, and may well make it harder. If Jim has something more constructive in mind than this, e.g. along the lines of categorial logic, it would be nice to understand the details. In a suitable setting for example, it may be possible to imbue "surely" with enough real-world significance to change the practical import of arithmetic statements using it. I maintain that any defense of this brand of intuitionism can be clarified, and hence made more convincing, by phrasing it as a raison-d'etre for "surely," or double negation, which, as Goedel was the first to see, conveniently localizes the significance of intuitionism by presenting it as an expansion of the language of classical logic with a unary operator. -- Vaughan Pratt ------- End of Forwarded Message From CATEGORIES@mta.ca Ukn Jan 13 21:30:15 1994 Received: from macc2.mta.ca by nimble.mta.ca (5.65/DEC-Ultrix/4.3) id AA08875; Thu, 13 Jan 1994 21:30:14 +0400 Date: Thu, 13 Jan 1994 21:29:55 -0400 (AST) From: CATEGORIES@mta.ca To: rrosebrugh@macc2.mta.ca Message-Id: <940113212955.20411c5e@mta.ca> Subject: Re: An object of formulas Status: RO X-Status: Date: Thu, 13 Jan 1994 10:02:22 -0500 (EST) From: MTHFWL@ubvms.cc.buffalo.edu Perhaps what Charles Wells was reading was SLNM 661 on "indexed categories", where recursion is put to such uses. From CATEGORIES@mta.ca Ukn Jan 13 23:14:07 1994 Received: from macc2.mta.ca by nimble.mta.ca (5.65/DEC-Ultrix/4.3) id AA00784; Thu, 13 Jan 1994 23:14:06 +0400 Date: Thu, 13 Jan 1994 21:28:52 -0400 (AST) From: CATEGORIES@mta.ca To: rrosebrugh@macc2.mta.ca Message-Id: <940113212853.2040f5aa@mta.ca> Subject: Re: question on homotopies Status: RO X-Status: >From MAS013@bangor.ac.uk Thu Jan 13 13:16:59 1994 Date: Thu, 13 Jan 94 9:03 GMT >From Tim Porter. In reply to Mike Barr's question, think of a cylinder generating the homotopy. The inclusions into the two ends are homotopy equivalences. (There are various cylinders possible; one due to Kleisi some years back.) Invert the homotopy equivalences and homotopic maps become identified. This was discussed in detail and more generality in Grothendieck's Pursuing Stacks. Happy New Year to all and sundry, Tim mas013@uk.ac.bangor From CATEGORIES@mta.ca Ukn Jan 14 02:57:36 1994 Received: from macc2.mta.ca by nimble.mta.ca (5.65/DEC-Ultrix/4.3) id AA20553; Fri, 14 Jan 1994 02:57:34 +0400 Date: Thu, 13 Jan 1994 21:28:02 -0400 (AST) From: CATEGORIES@mta.ca To: rrosebrugh@macc2.mta.ca Message-Id: <940113212803.20411ada@mta.ca> Subject: Re: strict epi(morphic) family, question on homotopies Status: RO X-Status: Date: Thu, 13 Jan 94 14:28:52 EST From: Vladimir Voevodsky -Does anybody know what is meant by "strict epi" or "strict epimorphic -family" ? -Maybe it's standard but I couldn't find it in any book available to -me ! -Thomas Streicher For a category which has fiber products the definition looks as follows (there are LATEX notations below). A family of morphisms $\{f_i:X_i\rightarrow Y\}$ in a category $C$ is called a stric epimorphic family if for any object $Z$ in $C$ the set $Hom(X,Z)$ is the equalizer of the maps $\prod_i Hom(X_i,Z)\rightarrow \prod_{i,j} Hom(X_i\times_Y X_j,Z)$ induced by the projections. If $C$ does not have fiber products one has in the definition above to replace $X_i\times_Y X_j$ by the fiber product of the corresponding representable functors and to consider morphisms in the category of functors from $C^{op}$ to $Sets$ (taking $Z$ to be a representable functor). A more sophisticated way to say the same thing is to say that a strict epimorphic family is a covering family in the canonical topology on $C$. All this should be in SGA4 and the definition for categories with fiber products should be in SGA1. -In the category of chain complexes (over some abelian category) -it is clear that if you identify homotopic arrows, you will also -invert homotopy equivalences. Does anyone know if the converse is -true? If you invert homotopy equivalences, do you wind up identifying -homotopic arrows? What if you replace homotopy by homology? Does -inverting maps that induce isomorphism on homology have the effect of -identifying maps that induce the same map on homology? -Michael The answer to the first question I guess is positive (and we do not need the original category to be abelian - just additive). The proof should look as follows. Let $f:X\rightarrow Y$ be a morphism which is homotopic to zero. We have to show that it is zero in the category localized with respect to homotopy equivalences. It follows from the fact that it can be factorized through the cone of the identity morphism $X\rightarrow X$ which is homotopy equivalent to zero. The answer to the second one is most definitely negative. In fact the statement is true if and only if the original abelian category is semi-simple. The localization with respect to "homological equivalences" i.e. quasi-isomorphisms is the derived category. Any extension in the original abelian category gives us a morphism in the derived one which is zero on (co)homology. Vlaidmir Voevodsky. From cat-dist Fri Jan 14 12:52:05 1994 Bcc: cdl1 -- Nagwa Abdel-Mottaleb , Samson Abramsky , Murray Adelman , Pierre Ageron , Moez Alimohamed , Roberto Amadio , Simon Ambler , Marko Amnell , Nils Andersen , "Jose Bacelar.Almeida" , John Baez , Clem Baker-Finch , Luis Soares Barbosa , David Benzvi , Jon Berrick , Renato Betti , blaaberg , Michael Blair , Andreas Blass , Rick Blute , Reinhard Boerger , Felipe Bracho , Torben Brauner , Simon Brock , Ronnie Brown , Kim Bruce , Richard Buckland , Manuel Bullejos , "Scot L. Burson" , Aurelio Carboni , Bruce Carpenter , Ross Casley , East Anglia Categories , Genova Categories , Hagen Categories , LFCS Categories , McGill Categories , qmw Categories , Saarlandes Categories , Sydney Categories , Tasmania Categories , Stephen Chase , Andy Chen , Roberto Chinnici , "B.P. Chisala" , Jin-Young Choi , Po-Hsiang Chu , Robin Cockett , Steve Cooper , "L. Coppey" , Simon Courtenage , Sjoerd Crans , Roy Crole , John Crow , Bob Rosebrugh Date: Fri, 14 Jan 1994 12:51:20 +0400 (GMT+4:00) From: categories Subject: Fuzzy + To: categories Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Status: RO X-Status: Date: Fri, 14 Jan 1994 09:05:25 +0100 From: Axel Poigne I yesterday attended a talk about fuzzy logic (I know this to be ``degoutant'', but...) where a ``Lukaciewicz norm'' was discussed as a t-norm. If I recollect correctly, a t-norm is a has a binary operator _\wedge_ which is associative, commutative, and monotonic, the latter being a mystery, the order being due to the real interval [0,1]. Moreover it seems that a negation \neg is assumed to exist, since an operator \vee is defined by de Morgan law. Quite clearly, min determines a norm as well as the multiplication. It seems to be an assumption that negation is always \neg a = 1-a. Now the Lukaciewicz norm is of the form a \wedge b = min{a + b, 1}. As consequence, a \vee b = max{a + b - 1, 0}. This norm satisfies a \wegde \neg a = 0 and a \vee \neg a = 1, but \vee and \wedge are not distributive, which is true for the other norms. (I hope this to be a correct recollection of what I heard) Trying to make head and tail of this, I wonder whether one really should say that one has a lower semi-lattice for the order, or even an Heyting algebra (in fact the \sqcap and \bigsqcup is about in all the arguments), and just add a binary monotonic, etc operator _ \otimes _ (replacing the \wedge in the t-norm). This structure rather looks like a quantale (units are available as well). I have no idea how negation fits the picture, but it reminds me of classical linear logic. Does this ring a bell ? I am just puzzled, having no idea about fuzzy logic, and little knowlege about linear logic. I know that Michael Barr has written a paper on Fuzzy sets as toposes but he uses only geometric logic, meaning a Heyting algebra. Axel A related question : these people seem to use \bigsqcup in general to compute suprema. It appears to be more consistent to use \bigoplus on occasions. How would this be defined in linear logic ? (Sorry, my linear logic is very poor) From cat-dist@mta.ca Ukn Jan 14 13:18:16 1994 Received: from bigmac.mta.ca by nimble.mta.ca (5.65/DEC-Ultrix/4.3) id AA08758; Fri, 14 Jan 1994 13:18:15 +0400 Date: Fri, 14 Jan 1994 12:56:25 +0400 (GMT+4:00) From: categories Subject: I like my coffee crisp To: categories Message-Id: Mime-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Status: RO X-Status: Date: Fri, 14 Jan 94 9:21:59 EST From: Al Vilcius This is an appeal for help to my friends and acquaintances on CATEGORIES: I have been enlisted to give a talk on "Fuzzy vs. Probability Theory" to an audience in finance whose backgrounds include applied mathematics, physics, engineering, and finance. The audience is not familiar with categories, no less toposes, which means that subtleties such as adding fuzzy equality to yield variable sets (sheaves) would be lost. Nevertheless, they are intrigued by the "fuzzy stuff" that is currently popular. My predicament is then to choose between: (1) torturing my conscience by giving an insubstantial and superficial talk on memberships vs distribution functions; (2) torturing the underlying mathematics into layman's prose. I am hoping that some of the learned readers of CATEGORIES may have already performed torture # 2 in a humane fashion (either in public or in private) and have some material and/or suggestions on how best to commit this heinous act. My preferred approach would be a la M. Barr via variable sets and sheaves, combined with the description of fuzzy and probabilistic algebraic theories given by E. Manes. I am already aware of many other fine (and some not so fine) works on fuzzy sets and fuzzy logic, however, I don't know how to make these understandable to non-categorists. I may well have to resort to torture # 1, but would like to avoid doing so if possible. All comments and suggestions, either privately to me at vilcius@clid.yorku.ca or publicly on CATEGORIES, on how I could have my "coffee crisp" would be most welcome. Thank you ............................... Al Vilcius, Toronto /\ / / \ / /--->\ / / \/ From cat-dist@mta.ca Ukn Jan 14 22:00:51 1994 Received: from bigmac.mta.ca by nimble.mta.ca (5.65/DEC-Ultrix/4.3) id AA02115; Fri, 14 Jan 1994 22:00:50 +0400 Date: Fri, 14 Jan 1994 21:53:59 +0400 (GMT+4:00) From: categories Subject: simple characterization of weak cartesian closedness To: categories Message-Id: Mime-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Status: O X-Status: Date: Fri, 14 Jan 94 18:55:12 +0100 From: Thomas Streicher I wonder whether the following trivial observation is generally known : a category C with finite products is WEAKLY CARTESIAN CLOSED iff for all objects A , B in C the functor C( _ x A , B) is a retract of a representable functor. (The embedding part of the retraction gives a choice of functional abstraction which is stable under substitution) and the projection part gives evaluation). Especially this entails that if C has splitting of idempotents then the notions of cartesian closedness and weakly cartesian closedness are equivalent. I don't think that the remark above is a deep insight !! BUT usually people refer to the quite heavy machinery of Hayashi's semifunctors when they speak about the categorical semantics of typed lambda calculus without eta-rule. Thomas Streicher From cat-dist@mta.ca Ukn Jan 14 22:13:22 1994 Received: from bigmac.mta.ca by nimble.mta.ca (5.65/DEC-Ultrix/4.3) id AA06984; Fri, 14 Jan 1994 22:13:21 +0400 Date: Fri, 14 Jan 1994 22:04:18 +0400 (GMT+4:00) From: categories Subject: cantor-bernstein To: categories Message-Id: Mime-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Status: O X-Status: Date: Fri, 14 Jan 94 15:44:32 EST From: Peter Freyd Pierre Ageron asked (way back on 1 Dec): The statement and the AC-free proof of Cantor-Schroeder-Bernstein's theorem have obviously some categorical content. Has this been already investigated ? The property, when it holds, is an important property on the category. It is, however, a rare property. There are, as usual, different ways to interpret the property in general categories. I would opt for the following: CANTOR-SCHROEDER-BERNSTEIN PROPERTY: If two objects be retracts of each other they are necessarily isomorphic. I trust that CSB holds for any boolean topos. (Anyone want to confirm?) Kaplansky in his booklet on infinite abelian groups pointed out that CSB holds in the category of countable torsion abelian groups (as a consequence of the Ulm invariants). He raised it as one of three test problems for advances in the theory of abelian groups. Does CSB continue to hold, for example, if countablility is dropped? (Kaplansky did not, of course, talk about retracts. He talked about two groups appearing as direct summands of each other.) Someone found a counterexample in the latter 50's. (Anybody know who?) If _A_ and _B_ are categories, _A_ a retract of _B_, it is routine that a counterexample for CSB in _A_ is transported to a countexample in _B_. _Abelian_Groups_ is a retract of _Topological_Spaces_ (via Moore spaces and homology) hence there are a pair of spaces which appear as retracts of each other but are different enough to have different homology groups. That fact became better known in the late 50's than the fact about abelian groups. (And in the late 50's it was damned difficult to explain why it should be viewed as a trivial corollary.) There's a stronger property: if two objects be retracts of each other the retraction maps are isomorphisms. The two most immediate examples are the categories of finite sets and of finite dimensional vectors spaces. But note that any category that is locally finite (i.e. all hom-sets are finite)--or any linear category that is locally finite dimensional--immediately inherits the property. By moving to a 2-category setting one may state the obvious general theorem of which these are special cases. I am not sure if any of this should be viewed as having "categorical content." best thoughts, peter From cat-dist@mta.ca Ukn Jan 14 22:19:20 1994 Received: from bigmac.mta.ca by nimble.mta.ca (5.65/DEC-Ultrix/4.3) id AA09262; Fri, 14 Jan 1994 22:19:19 +0400 Date: Fri, 14 Jan 1994 22:12:16 +0400 (GMT+4:00) From: categories Subject: syntactic criterion for join? To: categories Message-Id: Mime-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Status: O X-Status: Date: Fri, 14 Jan 1994 16:47:01 -0500 From: David Espinosa Does anyone know a syntactic criterion for the existence of a natural transformation join : TTA -> TA for a given endofunction T built from +, *, -> ? There is a well-known (correct me if I'm wrong) syntactic criterion for covariance which determines whether T can be extended to an endofunctor. Can this criterion be extended to the existence of join? Also, does anyone know a reference for the covariance criterion? David From cat-dist@mta.ca Ukn Jan 14 22:23:22 1994 Received: from bigmac.mta.ca by nimble.mta.ca (5.65/DEC-Ultrix/4.3) id AA11191; Fri, 14 Jan 1994 22:23:21 +0400 Date: Fri, 14 Jan 1994 22:15:51 +0400 (GMT+4:00) From: categories Subject: Re: Fuzzy + To: categories Message-Id: Mime-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Status: O X-Status: Date: Fri, 14 Jan 94 13:18:44 EST From: Michael Barr One thing to say is that I did not write a paper on fuzzy sets as toposes, but someone named Eytan did. I wrote a paper on fuzzy sets as non-toposes and it differs from Eytan's in being correct. On the other hand, fuzzy sets are a quasi topos, which means they do have a first order logic. That said, it has to admitted that the first order logic is probably not what they really had in mind as fuzzy logic and what they did have in mind (using operators like truncated sum and negations like - minus is closer to linear logic than to classical, even intuitionistic classical, logic. I once started to write a paper on this, but have not completed it it; maybe one day I will. And, BTW, Andy Pitts, unbeknownst to me, also once wrote a paper on fuzzy sets as a non-topos. His is also correct. Michael From cat-dist@mta.ca Ukn Jan 14 22:27:53 1994 Received: from bigmac.mta.ca by nimble.mta.ca (5.65/DEC-Ultrix/4.3) id AA13408; Fri, 14 Jan 1994 22:27:52 +0400 Date: Fri, 14 Jan 1994 22:19:28 +0400 (GMT+4:00) From: categories Subject: Re: I like my coffee crisp To: categories Message-Id: Mime-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Status: O X-Status: Date: Fri, 14 Jan 94 12:28:42 PST From: "Michael J. Healy (206) 865-3123" > Date: Fri, 14 Jan 94 9:21:59 EST > From: Al Vilcius > > This is an appeal for help to my friends and acquaintances on > CATEGORIES: > > I have been enlisted to give a talk on "Fuzzy vs. Probability > Theory" to an audience in finance whose backgrounds include > applied mathematics, physics, engineering, and finance. The > audience is not familiar with categories, no less toposes, which > means that subtleties such as adding fuzzy equality to yield > variable sets (sheaves) would be lost. Nevertheless, they are > intrigued by the "fuzzy stuff" that is currently popular. > > My predicament is then to choose between: > > (1) torturing my conscience by giving an insubstantial and > superficial talk on memberships vs distribution functions; > > (2) torturing the underlying mathematics into layman's prose. > > I am hoping that some of the learned readers of CATEGORIES may > have already performed torture # 2 in a humane fashion (either in > public or in private) and have some material and/or suggestions > on how best to commit this heinous act. > > My preferred approach would be a la M. Barr via variable sets and > sheaves, combined with the description of fuzzy and probabilistic > algebraic theories given by E. Manes. I am already aware of many > other fine (and some not so fine) works on fuzzy sets and fuzzy > logic, however, I don't know how to make these understandable to > non-categorists. I may well have to resort to torture # 1, but > would like to avoid doing so if possible. > > All comments and suggestions, either privately to me at > vilcius@clid.yorku.ca or publicly on CATEGORIES, on how I could > have my "coffee crisp" would be most welcome. > > Thank you ............................... Al Vilcius, Toronto > > /\ / > / \ / > /--->\ / > / \/ > > I have a related predicament. I'm an industrial mathematician with a need to learn what I can as soon as possible about a mathematical background for fuzzy logic. I am also furiously learning what I can about category theory and logic in connection with some work in formal methods for software engineering and machine learning (neural networks). So I really need to find an appropriate, no-nonsense (i.e., mathematical) formalism that meets all these requirements; given that, I can afford to invest considerable effort learning it. My current choice is to study categorical or category-related theories, and am currently reading up on Steven Vickers' work on topological systems as well as Goguen and Burstalls' work on institutions. If anybody has information that might help, or could elaborate on your reply to Al Vilcius so that a categorical novice might understand as well, I would be most grateful. I did study topology and algebra in grad school many years ago. Thank you, Mike Healy mjhealy@atc.boeing.com From cat-dist@mta.ca Ukn Jan 16 12:52:30 1994 Received: from bigmac.mta.ca by nimble.mta.ca (5.65/DEC-Ultrix/4.3) id AA08390; Sun, 16 Jan 1994 12:52:29 +0400 Date: Sun, 16 Jan 1994 12:37:25 +0400 (GMT+4:00) From: categories Subject: Acyclic models To: categories Message-Id: Mime-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Status: RO X-Status: Date: Sat, 15 Jan 94 11:43:33 EST From: Michael Barr There have been two apparently quite different categorical versions of acyclic models. The first, as found for example in Barr-Beck, COCA, 1966, says that if K = {Kn}, augmented over K(-1) and similarly L were chain complex functors and G is a cotriple such that (Kn)epsilon: (Kn)G --> Kn has a natural splitting when n >= 0 and if the complex LG --> L(-1)G --> 0 has a natural contracting homotopy, then any natural transformation K(-1) --> L(-1) can be extended to a unique up to homotopy map K --> L. In many cases the required naturality is too hard to verify (or false) and so a second form of the theorem is used. Here we simply suppose that the complex (Kn)G* --> Kn --> 0 is acyclic (an easy consequence of the splitting above), that LG --> L(-1)G --> 0 is acyclic and that K(-1) is isomorphic to L(-1) and conclude that H(K) is isomorphic to H(L). (Kn)G* stands for the standard powers-of-G resolution coming from eps. This version is easy to apply, but suffers from three defects. First, it works only in the case of isomorphism, not arbitrary maps. Second, it does not in itself give naturality, although that could probably be remedied by using a category of relations. Third, and probably most important, it gives no uniqueness. This means, for example, that although you can use it (in conjunction with an argument involving simplicial subdivision) to show that singular and simplicial homology of triangulated spaces are isomorphic, you cannot show this way that the isomorphism is induced by the inclusion of the simplicial chains into the singular ones. I have recently discovered a version of acyclic models that repairs all three defects. Moreover, it gives a single proof of both forms as well as third form involving what I will call weak homotopy equivalence. (This is not a Quillen model category in general, although there would appear to be considerable overlap.) Let C be the category of chain complexes of functors from some category X to an abelian category A. Say that an arrow K --> L in C is a weak homotopy equivalence if for each object x of X, Kx --> Lx is a homotopy equivalence (has a homotopy inverse and homotopies, etc., but not assumed natural). Let Sigma stand for one of the classes: (a) homotopy equivalences (b) weak homotopy equivalences (c) homology isomorphisms and let D denote the category of fractions gotten from C by inverting Sigma. Let (G,eps) be a pair consisting of an endofunctor on X and a natural transformation G --> Id. Say that the augmented object K --> K(-1) --> 0 of C is Sigma-trivial if the 0 endomorphism is in Sigma. Say that the object K of C is G presentable (w.r. to Sigma) if for each n >= 0, the chain complex (Kn)G* --> Kn --> 0 is Sigma-trivial and K is G acyclic (w.r. to Sigma) if KG --> K(-1)G --> 0 is Sigma-trivial. Then Theorem: If K is G presentable and L is G acyclic, both w.r. to Sigma, then any natural transformation K(-1) --> L(-1) can be extended in D to an arrow, unique in D, K --> L. In case (a), this is the theorem of Barr-Beck, 1966 and in case (c), this repairs the three defects cited above, while case (b) appears to be genuinely new. The proof is embarrassingly easy. Consider the diagram (alpha K)G* K(eps*) K(-1)G* <----------- KG* ---------> K | | | | v (alpha L)G* L(eps*) L(-1)G* <----------- LG* ---------> L alpha K and alpha L are the augmentation arrows. The G-presentability implies that K(eps*) is in Sigma and the G-acyclicity that (alpha L)G* is. When these are inverted, we get the desired map K --> L as the composite. A paper on the subject will be posted in the usual ftp location within a week or two. From cat-dist@mta.ca Ukn Jan 16 12:53:10 1994 Received: from bigmac.mta.ca by nimble.mta.ca (5.65/DEC-Ultrix/4.3) id AA08568; Sun, 16 Jan 1994 12:53:09 +0400 Date: Sun, 16 Jan 1994 12:44:32 +0400 (GMT+4:00) From: categories Subject: Re: cantor-bernstein To: categories Message-Id: Mime-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Status: O X-Status: Date: Sat, 15 Jan 94 11:36:22 EST From: Michael Barr One additional example and you don't even need retracts. In the category of finitely generated modules over a commutative ring, all epis are isos. As a result, if you have epis in both directions, they are isos. So the dual category category is S-B. This is fairly easy if the ring has ACC, but there is a trick that works for any ring to reduce it to that case. Since f.d. vector spaces are self-dual, this example encompasses that one. Michael From cat-dist@mta.ca Ukn Jan 17 09:36:47 1994 Received: from bigmac.mta.ca by nimble.mta.ca (5.65/DEC-Ultrix/4.3) id AA22458; Mon, 17 Jan 1994 09:36:46 +0400 Date: Mon, 17 Jan 1994 09:26:04 +0400 (GMT+4:00) From: categories Subject: Re: simple characterization of weak cartesian closedness To: categories Message-Id: Mime-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Status: RO X-Status: Date: Mon, 17 Jan 94 9:44:41 MET From: Simone Martini Thomas Streicher asks >> whether the following trivial observation is generally known: >> >>a category C with finite products is WEAKLY CARTESIAN CLOSED iff >>for all objects A , B in C the functor C( _ x A , B) is a >>retract of a representable functor. I cannot say about "generally known", but.. this property it is quoted as one of the elementary characterizations of wCCC in a paper of mine (Categorical Models for non-extensional lambda-calculi, Mathematical Structures in Computer Science (1992), vol 2, pag 327--357). The paper, which has a definite didactic pace, discusses also the case where there is only an epy natural transformation from C(_,A=>B) to C( _ x A , B), which gives models of typed, non extensional, Combinatory Logic; and it gives conditions on the existence of models of type-free lambda-calculus as reflexive objects in wCCCs. Simone Martini Universit\`a di Pisa, Dipartimento di Informatica. From cat-dist@mta.ca Ukn Jan 17 09:40:11 1994 Received: from bigmac.mta.ca by nimble.mta.ca (5.65/DEC-Ultrix/4.3) id AA22486; Mon, 17 Jan 1994 09:40:10 +0400 Date: Mon, 17 Jan 1994 09:29:33 +0400 (GMT+4:00) From: categories Subject: Re: simple characterization of weak cartesian closedness To: categories Message-Id: Mime-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Status: RO X-Status: Date: Mon, 17 Jan 1994 11:37:33 +0100 (MET) From: Raymond Hoofman Quoting Thomas Streicher, > I wonder whether the following trivial observation is generally known > : > > a category C with finite products is WEAKLY CARTESIAN CLOSED iff > for all objects A , B in C the functor C( _ x A , B) is a > retract of a representable functor. Yes, this is the "degenerate" case of a semi-adjunction between a functor G and a semi-functor F: the semi-isomorphism D(F(-), ...) \cong_{s} C(-, G(...)) becomes a retraction (see [1], also [2]). > I don't think that the remark above is a deep insight !! > BUT usually people refer to the quite heavy machinery of Hayashi's > semifunctors when they speak about the categorical semantics of typed > lambda calculus without eta-rule. However, if the products of your typed lambda calculus also do not satisfy the eta-rule, the semi-isomorphism above does not degenerate, and it is less obvious how to give a simple characterization without semi-functors (apart from saying that the Karoubi envelope of the category is Cartesian closed). [1] The theory of Semifunctors, R. Hoofman, MSCS 3 [2] Collapsing Graph models by preorders, R. Hoofman & H. Schellinx, LNCS 530 With kind regards, Raymond Hoofman. From cat-dist@mta.ca Ukn Jan 17 16:49:30 1994 Received: from bigmac.mta.ca by nimble.mta.ca (5.65/DEC-Ultrix/4.3) id AA23804; Mon, 17 Jan 1994 16:49:29 +0400 Date: Mon, 17 Jan 1994 16:18:00 +0400 (GMT+4:00) From: categories Subject: Fuzzy references To: categories Message-Id: Mime-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Status: O X-Status: Date: Mon, 17 Jan 1994 12:57:49 -0400 From: Mike Wendt ========================================================================== Hi Al: I'm not sure if this is what you want but here are a couple of references I've noticed recently (my search for categorical-measure-theory-type stuff): Bandemer, H., Nather, W, "FUZZA DATA ANALYSIS," Theory and Decision Library, Kluwer Academic Press, Series B, Vol. 20 (Norwell, Mass., 1992). Rodabaugh, S., Klement, E., Hoehle, U. (eds.), "APPLICATIONS OF CATEGORY THEORY TO FUZZY SUBSETS," Kluwer Academic Press, Series B, Vol. 14 (Norwell, Mass., 1992). I'm sorry, I can't give you a review of these books yet. I have only peeked in the first one. It seems interesting enough and is at an introductory level. Regards, -Mike Wendt ========================================================================== From cat-dist@mta.ca Ukn Jan 17 16:49:47 1994 Received: from bigmac.mta.ca by nimble.mta.ca (5.65/DEC-Ultrix/4.3) id AA23830; Mon, 17 Jan 1994 16:49:47 +0400 Date: Mon, 17 Jan 1994 16:24:16 +0400 (GMT+4:00) From: categories Subject: Re: Fuzzy + To: categories Message-Id: Mime-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Status: RO X-Status: Date: Mon, 17 Jan 94 15:36:35 +0100 From: Pierre Ageron In my thesis "Structure des logiques et logique des structures", I tried (very shortly) to understand what the algebraic and categorical counterparts of fuzzy logic are. There are different proposals in the literature, the reason is that there are plenty of interesting operations on the interval [0,1] and that it is very difficult to tell which ones are relevant for fuzzy logic. The most general axiomatization was given by Rene Guitart in his 1979 thesis (or a 1982 paper in the Cahiers). He considered complete ordered abelian monoids (in their 1990 book, Barr and Wells restricted to complete Heyting algebras). I observed that every complete ordered abelian monoid has a canonical Lafont algebra structure: this means that (this) fuzzy logic is the extension of intuitionistic linear logic with infinitary versions of the additive connectives "plus" and "with". Guitart defined the notion of "algebraic universe": essentially a category equipped with a monad P looking like the monad of subsets on Ens (I mean Set !). This notion subsumes the notion of elementary topos and allows to give higher order semantics for logics other than intuitionistic logic. In the case of fuzzy logic, the point is that every complete ordered abelian monoid defines such a structure on Ens. The Kleisli category of P is the category of fuzzy relations. All this is explained in my thesis using the notations of linear logic. All that framework gives Tarskian semantics for (propositional or higher order) fuzzy logic. It is not clear whether there are Heytingian semantics for fuzzy logic, i.e. a proof theory. The difficulty is that every small complete category is a poset (but this result by Freyd uses AC, so hope remains...) Pierre AGERON From cat-dist@mta.ca Ukn Jan 17 16:50:40 1994 Received: from bigmac.mta.ca by nimble.mta.ca (5.65/DEC-Ultrix/4.3) id AA24033; Mon, 17 Jan 1994 16:50:39 +0400 Date: Mon, 17 Jan 1994 16:26:39 +0400 (GMT+4:00) From: categories Subject: Re: cantor-bernstein To: categories Message-Id: Mime-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Status: RO X-Status: Date: Mon, 17 Jan 94 10:13:02 EST From: Peter Freyd Mike Barr writes: One additional example and you don't even need retracts. In the category of finitely generated modules over a commutative ring, all epis are isos. As a result, if you have epis in both directions, they are isos. So the dual category category is S-B. This is fairly easy if the ring has ACC, but there is a trick that works for any ring to reduce it to that case. Wonderful thought: all epis are isos. Anyway, I see a proof that any epi endo on a finitely presented module over a commutative ring is iso, but finitely generated? There's a metaprinciple that says that a result like this should generalize from commutative to PI rings (that is, rings that satisfy some non-trivial Polynomial Identity). Can anyone confirm? A corollary would be that in any additive category if two objects each appear as retracts of the other, and if the ring of endomorphisms of one of them is a PI ring then the retractions are isos. best thoughts, peter From cat-dist@mta.ca Ukn Jan 17 22:08:34 1994 Received: from bigmac.mta.ca by nimble.mta.ca (5.65/DEC-Ultrix/4.3) id AA17367; Mon, 17 Jan 1994 22:08:34 +0400 Date: Mon, 17 Jan 1994 21:46:07 +0400 (GMT+4:00) From: categories Subject: mathematics made hard To: categories Message-Id: Mime-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Status: RO X-Status: Date: Mon, 17 Jan 94 17:49:08 EST From: Peter Freyd This is about the opposite of category theory. I'm going to give a soft proof of something and ask how to get the hard proof. All of this because of Mike Barr's note about modules of commutative rings. Let M be a finitely presented module over a commutative ring R and f:M -> M an epimorphic endomorphism. We will show that f is necessarily an isomorphism. First specialize to the case that R is Noetherian. The kernels of the powers of f form an ascending chain of submodules of M, hence must stabalize. That is, there k+1 k k+1 is a natural number k such that Ker(f )= Ker(f ). Since f is epi, it is a cokernel for its kernel and there must exist g:M -> M k+1 k such that f g = f . (I'm composing maps in the diagramatic order.) Using for the second time that f is epi we may cancel to obtain fg = 1. Since fgf = f1 we cancel once more (using that f is epi for the third time) to obtain gf = 1. Now, let r and n be natural numbers and r n R -> R -> M -> O an exact sequence. There must be an rxn matrix K, an rxr matrix A' an nxn matrix A, another nxn matrix B, and an nxr matrix C such that KA = A'K BA + CK = I. (K describes the map r n n from R to R that defines M, A describes the endomorphism on R r that "lifts" f, A' describes the endomorphsim on R . Since f is n+r n epi the map R -> R obtained by stacking A and K is also n n+r epi, hence it has a left-inverse (B,C):R -> R .) Specialize to the case that R is the the "generic ring", that is the ring generated by the 2nn+2nr+rr entries of K,A,A',B,C with nr+nn equations. We may infer that there is an rxr matrix X and an nxr matrix Y such that KB = XK AB + YK = I. The entries of X and Y are necessarily given by polynomials in the generating "variables" and the last two matrix equations must result in rr+nr equations that are direct consequences of the nr+nn defining equations. Hence the original theorem works for any finitely presented module over any commutative ring. Now for the hard part: what are these polynomials? In the case n = 1 its easy (and reveals quickly the need for commutativity). Try it for n=2, r=1. Given: ac+be = ga ad+bf = gb hc+ie+la = 1 hd+if+lb = 0 jc+ke+ma = 0 jd+kf+mb = 1 find, for a start, a polynomial on these variables, x, such that ah+bj = xa ai+bk = xb. From cat-dist@mta.ca Ukn Jan 17 22:18:57 1994 Received: from bigmac.mta.ca by nimble.mta.ca (5.65/DEC-Ultrix/4.3) id AA21023; Mon, 17 Jan 1994 22:18:56 +0400 Date: Mon, 17 Jan 1994 22:05:50 +0400 (GMT+4:00) From: categories Subject: Re: cantor-bernstein To: categories Message-Id: Mime-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Status: RO X-Status: Date: Mon, 17 Jan 94 20:15:09 EST From: Michael Barr > Mike Barr writes: > > One additional example and you don't even need retracts. In the category > of finitely generated modules over a commutative ring, all epis are > isos. As a result, if you have epis in both directions, they are > isos. So the dual category is S-B. This is fairly > easy if the ring has ACC, but there is a trick that works for any > ring to reduce it to that case. > > Wonderful thought: all epis are isos. Anyway, I see a proof that any > epi endo on a finitely presented module over a commutative ring is > iso, but finitely generated? > > There's a metaprinciple that says that a result like this should > generalize from commutative to PI rings (that is, rings that satisfy > some non-trivial Polynomial Identity). Can anyone confirm? A corollary > would be that in any additive category if two objects each appear as > retracts of the other, and if the ring of endomorphisms of one of them > is a PI ring then the retractions are isos. > > best thoughts, > peter > > I will try to recall the argument (on-line). Given an epi-endomorphism f, look at the ascending chain ker(f), ker(f^2), ker(f^3),.... In the noetherian case, this stabilizes so that ker(f^n) = ker(f^{n+1}). Assume thatn is as small as possible, so that ker(f^{n-1}) < ker(f^n). Choose an element x in the ker of f^n, not in the lesser one. x = f(y) for some y, since f is onto. 0 = f^n(x) = f^{n+1}(y), so that 0 = f^{n}(y) = f^{n-1}(x), a contradiction. That takes care of the noetherian case and doesn't even use commutativity, it would seem. For the general case, suppose R is the ring, M the module, f: M --> M the endomorphism and x an element with f(x) = 0. Now pick a set of generators for M, say y_1,...,y_n. What you have to do is to find a suitable finite subset of R, with just the right elements in it to express all the f(y_i), x and at least one preimage of each y_i as linear combinations of the y_i using coefficients from that subset. Now let S be the subring of R generated by that finite set of elements and N be the least S-submodule of M containing all the y_i. If I have left anything required out of S, add that too. Anyway, S is noetherian (this does use commutativity, I believe) and f induces a counter-example on N. I believe this argument is due to one of the Rutgers people like Faith or Osofsky, but I am far from certain of that. It will be true for PI rings if affine PI rings have acc on left ideals. For commutative rings it is essentially the Hilbert basis theorem. Michael From cat-dist@mta.ca Ukn Jan 19 22:39:16 1994 Received: from bigmac.mta.ca by nimble.mta.ca (5.65/DEC-Ultrix/4.3) id AA04251; Wed, 19 Jan 1994 22:39:15 +0400 Date: Wed, 19 Jan 1994 22:19:51 +0400 (GMT+4:00) From: categories Subject: RE Fuzzy + To: categories Message-Id: Mime-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Status: RO X-Status: Date: Wed, 19 Jan 1994 11:45:07 -0600 From: Lawerce Neff Stout I've done quite a lot of work on categories of fuzzy sets. The main paper is in the volume edited by H\"ohle and Rodabaugh referred to earlier. Barr is correst that fuzzy sets form a quasitopos, but the logic of that quasitopos is that of the underlying set category, hence not interesting as a place to do fuzzy mathematics. The fuzzy connectives come from a second monoidal closed structure obtainable from, for example, the t-norms usually referred to in the fuzzy literature. This gives a very satisfactory logic if one uses what I called unballanced subobjects (the map involved is both monic and epic). There is a weak representor for these subobjects (representation is not unique though there is an ordering on maps which allows a canonical choice of representative to be made) allowing an internal representation of a large fragment of higher order fuzzy logic. I have a more recent paper (to appear in the proceedings of the 1992 Linz seminar, being published by Kluwer sometime later this year) in which I look at categories of fuzzy sets with values in a Quantale or Projectale. That paper is available from me by e-mail (I don't have ftp facilities available). It includes a characterization of categories of fuzzy sets in terms of the representability of the logic and the property of being topological over Sets. Larry Stout From cat-dist@mta.ca Ukn Jan 21 09:51:34 1994 Received: from bigmac.mta.ca by nimble.mta.ca (5.65/DEC-Ultrix/4.3) id AA04197; Fri, 21 Jan 1994 09:51:33 +0400 Date: Fri, 21 Jan 1994 09:30:23 +0400 (GMT+4:00) From: categories Subject: categorical treatment of F_omega? To: categories Message-Id: Mime-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Status: RO X-Status: Date: Thu, 20 Jan 1994 17:24:00 -0500 From: David Espinosa 1. Could someone send me a good reference for a categorical treatment of the Girard / Reynolds F_2 polymorphic type system? That is, polymorphic functions as (some form of) natural transformations? 2. More importantly, has there been a categorical treatment of Girard's F_omega type system? David From cat-dist@mta.ca Ukn Jan 22 13:58:28 1994 Received: from bigmac.mta.ca by nimble.mta.ca (5.65/DEC-Ultrix/4.3) id AA01235; Sat, 22 Jan 1994 13:58:27 +0400 Date: Sat, 22 Jan 1994 13:49:21 +0400 (GMT+4:00) From: categories Subject: Terminology question To: categories Message-Id: Mime-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Status: O X-Status: Date: Sat, 22 Jan 1994 2:44:17 -0500 (EST) From: D_FELDMAN@UNHH.UNH.EDU Is there a standard terminology for the following sort of gadget or something very similar? Define a {\em ??????} to be a pair $(S,F)$ consisting of a category $S$ and a functor $F$ from ${\bf S}$ to ${\bf Bij}$, the category of finite sets and bijections, satisfying\\ (i) If $F(s_1)=t_1$ and $\tau:t_1\rightarrow t_2$, then there exists a unique object $s_2\in {\bf S}$ and a unique ${\bf S}$-morphism $\sigma:s_1\rightarrow s_2$ such that $F(\sigma)$=$\tau$.\\ (ii) For $t \in {\bf Bij}$, $F^{-1}(t)$ is an (effectively computable) finite set. David Feldman From cat-dist@mta.ca Ukn Jan 24 13:43:31 1994 Received: from bigmac.mta.ca by nimble.mta.ca (5.65/DEC-Ultrix/4.3) id AA08176; Mon, 24 Jan 1994 13:43:30 +0400 Date: Mon, 24 Jan 1994 13:15:21 +0400 (GMT+4:00) From: categories Subject: Re: Terminology question To: categories Message-Id: Mime-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Status: O X-Status: Date: Mon, 24 Jan 1994 16:13:07 +0000 (GMT) From: Edmund Robinson > > Date: Sat, 22 Jan 1994 2:44:17 -0500 (EST) > From: D_FELDMAN@UNHH.UNH.EDU > > Is there a standard terminology for the following sort of gadget or something > very similar? > > Define a {\em ??????} to be a pair $(S,F)$ consisting of a category $S$ and > a functor $F$ from ${\bf S}$ to ${\bf Bij}$, the category of finite > sets and bijections, satisfying\\ > (i) If $F(s_1)=t_1$ and $\tau:t_1\rightarrow t_2$, then there exists a > unique object $s_2\in {\bf S}$ and a unique ${\bf S}$-morphism > $\sigma:s_1\rightarrow s_2$ such that $F(\sigma)$=$\tau$.\\ > (ii) For $t \in {\bf Bij}$, $F^{-1}(t)$ is an (effectively > computable) finite set. > > David Feldman > > I think this would traditionally be described as a "finite discrete opfibration (over Bij)". The functors corresponding to condition (i) are discrete opfibrations, and the finite comes from condition (ii). Neither of these uses any special property of Bij (such as the fact that it is a groupoid). It might be more modern to use "cofibration" instead of "opfibration". See Barr & Wells "Toposes, Triples and Theories" p231 ex [OPF] for more conventional definitions, and perhaps Benabou "Fibred categories and the foundations of naive category theory" (J. Symbolic Logic (50) No. 1, 1985, 10-37) for more of an indication of why these sorts of structures are so common. Another way of looking at the structure would be to turn it around and say that you have a functor G: Bij -> FiniteSet given on objects by G(t) = F^{-1}(t). best wishes, Edmund Robinson From cat-dist@mta.ca Ukn Jan 25 07:26:29 1994 Received: from bigmac.mta.ca by nimble.mta.ca (5.65/DEC-Ultrix/4.3) id AA26948; Tue, 25 Jan 1994 07:23:14 +0400 Date: Tue, 25 Jan 1994 07:21:14 +0400 (GMT+4:00) From: categories Subject: Re: Terminology question To: categories Cc: cdl2 -- France Dacar , Robert Dawson , "Oege de.Moor" , "Valeria de.Paiva" , "Ruy de.Queiroz" , "Fer-Jan De.Vries" , Kyung-Goo Doh , James Dolan , Xiaomin Dong , Winfried Drecmann , Dominic Duggan , Gerald Dunn , Hans Dybkjaer , Abbas Edalat , David Espinosa , Michel Eytan , Joe Fasel , David Feldman , Zbigniew Fiedorowicz , Juarez Muylaert Filho , Stacy Finkelstein , Kathleen Fisher , Maria Frade , Peter Freyd , Tom Fukushima , Jonathan Funk , Fabio Gadducci , Vijay Gehlot , Wolfgang Gehrke , Silvio Ghilardi , Paul Glenn , Joseph Goguen , Marek Golasinski , Al Goodloe , Bob Gordon , Francoise Grandjean , John Gray , Luzius Grunenfelder , Stefano Guerrini , Alessio Guglielmi , James Harland , Robert Harper , Magne Haveraaen , "Michael J. Healy" , Michel Hebert , Murray Heggie , Luis Javier Hernandez , Walt Hill , SATO Hiroyuki , Bernard Hodgson Message-Id: Mime-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Status: O X-Status: Date: Tue, 25 Jan 1994 10:18:25 +0000 From: Steven Vickers Do others suffer the same heartsink as I do when confronted with a posting like this? >Define a {\em ??????} to be a pair $(S,F)$ consisting of a category $S$ and >a functor $F$ from ${\bf S}$ to ${\bf Bij}$, the category of finite >sets and bijections, satisfying\\ > (i) If $F(s_1)=t_1$ and $\tau:t_1\rightarrow t_2$, then there exists a >unique object $s_2\in {\bf S}$ and a unique ${\bf S}$-morphism >$\sigma:s_1\rightarrow s_2$ such that $F(\sigma)$=$\tau$.\\ > (ii) For $t \in {\bf Bij}$, $F^{-1}(t)$ is an (effectively >computable) finite set. For human readers (and after all, is this message _ever_ going to be presented to a Latex interpreter?) most of the $'s and \'s here are not only completely unnecessary, but, worse, a positive barrier to understanding. I would expect - but this is something that can be put to the test - that even people completely familiar with Latex would find it easier to read the following version. It certainly involves less typing. >Define a ?????? to be a pair (S,F) consisting of a category S and >a functor F from S to Bij, the category of finite >sets and bijections, satisfying - > (i) If F(s_1)=t_1 and tau:t_1 -> t_2, then there exists a >unique object s_2 in S and a unique S-morphism >sigma: s_1 -> s_2 such that F(sigma)=tau. > (ii) For t in Bij, F^{-1}(t) is an (effectively >computable) finite set. (I have ignored the puzzle of whether {\bf ...} is mathematically meaningful - in the original $S$ turns into ${\bf S}$. If it _is_ mathematically meaningful, then in Latex it should be macroized.) Steve Vickers. p.s. Having rephrased the question, I still don't know the answer - sorry. From cat-dist@mta.ca Ukn Jan 25 12:17:27 1994 Received: from bigmac.mta.ca by nimble.mta.ca (5.65/DEC-Ultrix/4.3) id AA28518; Tue, 25 Jan 1994 12:17:27 +0400 Date: Tue, 25 Jan 1994 11:47:26 +0400 (GMT+4:00) From: categories Subject: Re: cantor-bernstein To: categories Message-Id: Mime-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Status: RO X-Status: Date: Wed, 19 Jan 1994 09:37:14 -0500 From: Stephen Chase With regard to the remarks of Barr and Freyd on surjective endomorphisms of finitely generated modules: I haven't digested those remarks, but here is a slick proof of the result, communicated to me years ago by Bill Waterhouse (instead of reduction to the Noetherian case, it uses localization): It is enough to prove bijectivity at all localizations, so we can assume that the commutative ring A is local with maximal ideal m. Given a surjective endomorphism f of a finitely generated A-module M, let F be a finitely generated free A-module mapping onto M so that the mapping induces an isomorphism F/mF ----> M/mM. Let K = Ker(F ---> M). f then lifts to an endomorphism g of F, which is an isomorphism because it is so mod m. Then g(K) is contained in K, and to prove f is bijective we need only show g'(K) is likewise contained in K (with g' the inverse of g). But g satisfies its characteristic polynomial, which has invertible constant term det(g) (up to sign); thus g' is a polynomial in g and so maps K into itself. I haven't seen this proof in the literature. However, the following related reference might be of interest: M. Orzech, L. Ribes, "Residual finiteness and the Hopf property in rings", J. Algebra 15 (1970), 81-88. Sincerely, Steve Chase From cat-dist@mta.ca Ukn Jan 25 12:22:48 1994 Received: from bigmac.mta.ca by nimble.mta.ca (5.65/DEC-Ultrix/4.3) id AA28645; Tue, 25 Jan 1994 12:22:48 +0400 Date: Tue, 25 Jan 1994 11:53:49 +0400 (GMT+4:00) From: categories Subject: terminology To: categories Message-Id: Mime-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Status: RO X-Status: [Note from moderator: 1. The two posts following are being forwarded, but I don't feel that this list is really the place for a long discussion of suitable notation for e-mail, so I hope that any discussion will be short] Date: Tue, 25 Jan 94 08:37:53 EST From: Peter Freyd I certainly agree with Steve's point. But I would go further: Define a ?????? to be a pair (*S*, F) consisting of a category *S* and a functor F from *S* to *Bij* , the category of finite sets and bijections, satisfying - (i) If F(S ) = T and f:T -> T' , then there exists a unique object S' in *S* and a unique morphism g: S -> S' such that F(g) = f. (ii) For T in *Bij*, F (T) is an (effectively computable) finite set. But: I must confess that I also experience a little "heartsink" when I see a list of addresses as long as that above. best thoughts, peter ++++++++++++++++++++++++++++++++++++++++++++ Date: Tue, 25 Jan 94 9:51:20 EST From: Al Vilcius Referring to the "rephrased" question of Steve Vickers: > > Do others suffer the same heartsink as I do when confronted with a posting > like this? > > >Define a {\em ??????} to be a pair $(S,F)$ consisting of a category $S$ and > >a functor $F$ from ${\bf S}$ to ${\bf Bij}$, the category of finite ...... Yes, I certainly do, and much prefer the "humanized" alternative: > > >Define a ?????? to be a pair (S,F) consisting of a category S and > >a functor F from S to Bij, the category of finite ...... > -- /\ / Al Vilcius, Toronto / \ / /--->\ / / \/ From cat-dist@mta.ca Ukn Jan 27 12:30:09 1994 Received: from bigmac.mta.ca by nimble.mta.ca (5.65/DEC-Ultrix/4.3) id AA27146; Thu, 27 Jan 1994 12:30:08 +0400 Date: Thu, 27 Jan 1994 11:53:21 +0400 (GMT+4:00) From: categories Subject: RE: terminology To: categories Message-Id: Mime-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Status: RO X-Status: Date: Wed, 26 Jan 1994 2:35:50 -0500 (EST) From: D_FELDMAN@UNHH.UNH.EDU Thank you to all those who responded, including those who pointed out my e-faux pas. Incidently, the complaint about S versus {\bf S} alerted me to a typo in a paper under preparation (these should have been the same) and so I am especially grateful for that. David Feldman From cat-dist@mta.ca Ukn Jan 31 16:29:46 1994 Received: from bigmac.mta.ca by nimble.mta.ca (5.65/DEC-Ultrix/4.3) id AA01906; Mon, 31 Jan 1994 16:29:45 +0400 Date: Mon, 31 Jan 1994 15:59:00 +0400 (GMT+4:00) From: categories Subject: New address of Fer-Jan de Vries To: categories Message-Id: Mime-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Status: RO X-Status: Date: Mon, 31 Jan 1994 20:17:52 +0100 From: F.J.de.Vries@cwi.nl CWI, January 31, 1994 Dear Colleague. The coming year I will live and work in Japan. My addresses will be the following: Office: from March 1st, 94, onwards NNT, Communication Science Laboratories Hikaridai, Seika-cho, Soraku-gun, Kyoto 619-02 Phone +81-7749-5-1841, Facsimile +81-7749-5-1851 Email ferjan@progn.kecl.ntt.jp Home: from Feb 1st, 94, onwards Seresu-Gakuenmae 305 Gakuen-Naka 1-1542-190 Nara-shi, Nara 631 Phone: yet unkown... Sayonara, Fer-Jan de Vries.