September 1991 - Categories - categories.org.au

Call for papers - reminder for participants
by rags＠triples.Math.McGill.CA 26 Sep '91

26 Sep '91

CATEGORY THEORY 1991 - Montreal CALL FOR PAPERS (reminder) To: All participants of the CT'91 meeting in Montreal, June 1991 (including invited speakers, other speakers, and other attendees) As announced at the meeting: The proceedings of this meeting will be published by the American Mathematical Society, we hope before next summer, in the Conference Proceedings series of the Canadian Mathematical Society. These proceedings will be referreed, following the usual journal standards and procedures. We are inviting submissions from invited speakers and ALL other participants. Papers in category theory or its applications in any of the subjects covered at the meeting are welcome. Please send three (3) copies to the address below. (The usual exceptions apply: people in places that cannot provide sufficient xerox facilities may submit one copy; in emergency electronic submissions may be considered---please check with Robert Seely first.) To keep to our schedule, we are asking that submissions be sent before 1 December 1991. (In the event that we exceed our page limit, late submissions may not be considered.) We hope to be able to notify authors of the acceptance of papers by March 1992. Send the three copies (by 1 December 1991) to: Category Theory 1991 - Proceedings c/o R.A.G. Seely Department of Mathematics McGill University 805 Sherbrooke St. W. Montreal, Quebec CANADA H3A 2K6 (email: rags(a)triples.math.mcgill.ca ) (fax: 514 - 398 3899 )

1 0

Re: A diagram lemma
by Fred E.J. Linton 25 Sep '91

25 Sep '91

In a message with [Subject: A diagram lemma] Mike Barr asks: > Has anyone seen the following diagrammatic lemma? Sure -- in the general case. Remember the business about "lim-pacing" functors in Lawvere's Columbia PhD thesis? A functor C ---> D is lim-pacing iff: for every diagram, anywhere, of shape D , if the "restricted" diagram of shape C has a limit, then so does the original one, and the canonical "comparison" between those two limits is an isomorphism. There are n.a.s.c.'s internal to C and D for the lim-pacing condition (some comma category being non-empty and connected); and your "diagrammatic lemma" is just the instance of all these obtained with C = NNO^op and D = (NNO x NNO)^op (and C ---> D the diagonal). [No one would probably want to bother promoting this particular case to the status of a "lemma".] Hope this helps. -- Fred ==================================

5 6

Fred Linton's reply
by barr＠triples.Math.McGill.CA 18 Sep '91

18 Sep '91

Following Fred's lead, I discovered the following in Lawvere's thesis: (reworded to make the language more modern). Suppose u: C --> D is a functor such that C is small (I'm not sure it matters), every coterminous pair of maps in D is the front half of a commutative square and u is cofinal in the sense that for any d in D, there is a c in C and a map uc --> d. Then for any functor f: D --> E any limit of fu is a limit of f. These conditions are readily seen to be satisfied for the inclusion of the diagonal into the double sequence, so Fred's memory is completely accurate on this. Michael =================================

1 0

PJF on Barr on PJF
by pjf＠saul.cis.upenn.edu 14 Sep '91

14 Sep '91

Mike complains when he quotes me as saying: ``The relevant property [of Set] is that all non-zero objects be injective.'' His point is that I am using other properties of the category. Of course I was. I thought I was writing in the context of topoi. (Mike does seem to understand that I was writing in the context of locally complete categories, indeed, he wants to use more local completeness than I was willing to use.) He further writes: The problem is that the composite K >--> A x B --> A isn't necessarily monic.. Given the definition of K and the condition on T it is necessarily monic. I should note here that the argument I gave says that the category of countable sets is an algebraically complete category, that is, every endofunctor has an initial algbra. Adamek has already observed that every endofunctor has an invariant object. His other similar examples work as well: for any cardinal the category of all sets of that cardinality or less is algebraically complete; the category of all vector spaces (for a chosen field) of dimension that cardinality or less is algebraically complete (using the axiom of choice in the non-countable cases). ==============================

1 0

NEW ADDRESS/FTP SITE
by Bob Rosebrugh 12 Sep '91

12 Sep '91

*********************************************************** * * * NEW ADDRESS FOR CATEGORIES * * * *********************************************************** As many of you will have noted, categories is now sent from the internet host: mta.ca Please send mail to categories(a)mta.ca (for postings) or rrosebrugh(a)mta.ca (for administrative messages). *****Note that categories-request is no longer a valid user.***** For about a month, the host mta.bitnet will continue to be available, but the new addresses are evidently preferable and provide more accurate service. ************ ARCHIVES AVAILABLE BY FTP ********************* Anonymous ftp from macc2.mta.ca is also now available. Archives of the categories mailing list are available up to December 1990 (and shortly to June 1991.) in subdirectories of [anonymous.categories] It is also intended that the directory [anonymous.categories.macro] will contain an archive of diagram macro packages for TeX, or pointers to ftp sites offering such packages. Please note the host: macc2.mta.ca DANGEROUS BEND!!!! VMS (Vax) syntax must be used in changing default directories so, for example, to descend from the current directory type cd [.subnode] (change to the `subnode' directory) to ascend one node in the directory tree type cd [-] Example, after anonymous login cd [.categories] (go to the categories directory) dir (what's there?) cd [.cats90] (go to the 1990 archive, CATS90.DIR was in the directory.) dir get 90-06.txt (messages from June 1990) cd [-] (go back up to [.categories]) quit (or exit!) Each directory contains a file named 00README.TXT which explains the directory contents. Any queries or problem reports should be directed to me. Bob Rosebrugh <rrosebrugh(a)mta.ca> ======================================

1 0

PJF's contribution
by barr＠triples.math.mcgill.ca 12 Sep '91

12 Sep '91

When I went to read finally what Peter wrote earlier this week, I realized that there was a problem with it. Not that the conclusion, or even the argument, was wrong (although there are two sentences in it I cannot parse), but the tossed off statement, ``The relevant property ?of Set? is that all non-zero objects be injective.'' But the conclusion is false for the opposite of Set and there _every_ object is injective. So what is really involved? The argument breaks into two parts. First that every pre-invariant T-alg (that is one whose structure TA --> A is 1-1) includes a minimal subobject and that is pre-invariant. As a matter of fact, that is obvious; just take the intersection of all the subobjects. It is trivial in fact to show that that is invariant. But Peter adopts a curiously complicated proof. For clarity (it doesn't actually matter), assume that T preserves _all_ monics. Peter then says that you can begin with 0 and take the image of T0 --> TA --> A and so build up a family of subobjects whose union is this minimal subobject. Well, I thought, if it turns him on... The second part of the proof is to show that this minimal invariant object is initial. I am going to reword Peter's argument in a way that I find a bit more congenial, but it is his argument. Let TA --> A be this minimal invariant algebra and TB --> B be any algebra. Let TC --> C be the smallest subalgebra of A x B. Now C can of course be constructed as the intersection of all the subalgebras of A x B or it can be built up from below. But the first argument works in any sufficiently complete category and we know the result is false in most categories, including ones in which every functor preserves monics. (It is also, of course, false for functors in arbitrary categories that preserves monics.) So what is the crucial difference? Well, if you begin with 0 >--> A x B, the composite 0 >--> A x B --> A is also monic. Then so is the composite T0 >--> T(A x B) --> TA = A (= means the structure map is an isomorphism). Thus the image of T0 >--> T(A x B) --> A x B also has the property that its inclusion followed by the projection on A is monic. And so on. When you take the colimit you get a subalgebra of A x B that maps monically (and, it is easy to show, epically) to A. Thus this is the graph of a map A to B. The rest of the argument is routine. The moral is that the basic thing that is working here is that the colimit of monics is monic. In other words, the accessibility of sets is the crucial property. Of course, other properties are also needed. This very much illustrates the principal of versality Peter made in his recent preprint on algebraically complete categories about the importance of things with both universal and couniversal mapping properties. Later: I just realized that there appears to be a minor flaw in Peter's argument. He writes: ``Now let K be the partial map from A to B whose graph is the image of (T0 -> (TA)x(TB) -> AxB).'' The problem is that the composite K >--> A x B --> A isn't necessarily monic, so K isn't necessarily the graph of a partial function A to B. One way around this is to use the argument I gave in my paper on Terminal objects in well-founded set theory that replaces T by a functor T^# that preserves _all_ monics and has the same initial and terminal object as T. Isn't it amazing how often the empty set comes round and stings us! Michael =================================

1 0

PJF Functors
by barr＠triples.math.mcgill.ca 11 Sep '91

11 Sep '91

A paper has been added to my ftp directory with the above title. It is a preliminary version only. An abstract follows: In a previous paper, we investigated the relation between the initial algebra and terminal coalgebra for an endofunctor on the category of sets. In this one we study conditions on a functor to be PJF, which means that the canonical comparison morphism between those objects is an isomorphism. The /pub/texmacros directory has slightly modified versions of mtex.tex and diagram.tex. The differences are described in a file called changes.tex. Michael ==============================

1 0

peejayeff functors
by barr＠triples.math.mcgill.ca 09 Sep '91

09 Sep '91

I have been trying to figure out a good name for an endofunctor for which the canonical map from the intial algebra to the terminal coalgebra is an isomorphism. After reading the latest from PJF, it suddenly hit me. MB ==============================

1 0

embar cats
by pjf＠saul.cis.upenn.edu 08 Sep '91

08 Sep '91

Barr asks if it is known that the category of sets is an EMBAR CATEGORY, that is, if for every endofunctor on the category of sets it is the case that the canonical map from the initial algebra to the final coalgebra is monic (assuming, of course, that both exist). Herewith is a proof. First, however, some counterexamples. On any category suppose that f: A -> B is a map such that there is no map at all from B back to A. Then there is an endofunctor, T, such that A is an initial T-algebra, B is a final T-coalgebra and f is the canonical map. For example: TX = if there's a map X -> A then A else B. T(x:X -> Y) = if TX = TY then 1:TX -> TY else f: A -> B. This construction says that embar categories are a bit rare. If a topos (indeed, any positive prelogos) is embar then it is two- valued, that is, if there's a proper non-trivial subterminator, 0 < U < 1, then the map U+U -> 1 is not monic but is as required for the above construction. The only boolean embar topoi are well-pointed. Embarcation is therefore very fragile under slicing. (sets)/X is embar iff X = 0 or 1. The category of G-sets is embar iff the group G is trivial but (G-sets)/G is always embar (where the last G means the regular G-set). But booleaness is not necessary for embar. The proof below works for the category of S-sets where S is the sierpinski monoid (0,1 under multiplication). The relevant property is that all non-zero objects be injective. I will say that a PRE-INVARIANT OBJECT for an endofunctor, T, is a _monomorphism_ TA -> A. (If it's an isomorphism it's an invariant object.) A MINIMAL PRE-INVARIANT OBJECT is one that contains no proper pre-invariant objects, that is, one such that for every commutative diagram of monomorphisms: TA' -> TA | | A' -> A it is the case that the horizontal maps are isomorphisms. Recalling the co-Lambek lemma that the structure map of any final coalgebra is an isomorphism one can easily see that the following proposition says that the category of sets is embar: Proposition: Let T be an endofunctor on the category of sets. Any pre- invariant object for T contains a minimal pre-invariant object. Any minimal pre-invariant object is an initial algebra. Proof: If T0 = 0 everything is quite clear. We suppose therefore that T0 is non-empty. Let m: TA -> A be a monic. Let K be the subset of A defined as the image of (T0 -> TA -> A). Let P be the lattice of all subsets of A that contain K. Consider the order-preserving endofunction, t, on P that sends A' to the image of (TA' -> TA -> A). By Tarski, if it isn't the case that there's a minimal pre-fixed point for t. But since T preserves all monomorphisms from non-empty sources, pre-fixed points of t are automatically pre-invariant objects for T. So there. Now suppose that m: TA -> A is minimal pre-invariant. Let b: TB -> B be arbitrary. Now let K be the partial map from A to B whose graph is the image of (T0 -> (TA)x(TB) -> AxB). Let P be the CPO of all partial maps from A to B that contain K. Let t be the order-preserving endofunction that sends a partial map tabled by A' to the partial map tabled by TA' / \ / \ A B TA TB / \ A B. By Scott, if it isn't the case that we have a fixed point for t. The domain of this partial map is a pre-invariant object, therefore it's all of A. The partial map is a map. If there were two T-algebra maps from A to B their equalizer would have to be smaller pre-invariant object. So there aren't two maps. Done. ==============================

1 0

Index for papers at triples
by barr＠triples.math.mcgill.ca 07 Sep '91

07 Sep '91

There is now an Index.barr file in /pub/barr at triples.math.mcgill.ca. I attach that index to this letter. It contains only the papers' titles, but that ought to be enough. I am willing to send an email to anyone who doesn't have anonymous ftp capability. If people send me a note, I will take care of it, but obviously I would prefer it if they could do it themselves. It is also the case that ftp is MUCH more reliable. acclinlo.tex: Accessible categories and models of linear logic ctcsupdate.tex: CTCS update fuzlinlo.tex: Fuzzy models of linear logic hsp.tex: Functorial semantics and HSP type theorems hsppos.tex: HSP type theorems in the category of posets staracll.tex: *-Autonomous categories and linear logic termobj.tex: Terminal coalgebras in well-founded set theory tttcorr.tex: Corrections to TTT =================================

1 0