September 1992 - Categories - categories.org.au

None
by Paul Taylor 30 Sep '92

30 Sep '92

Be careful about epimorphisms of categories.

1 0

Re: Comparison between Functor Categories (2 postings)
by street＠macadam.mpce.mq.edu.au 30 Sep '92

30 Sep '92

Dear Steve Sorry to cause you grief with the "fully faithful" terminology which is common in categorical papers, but perhaps not textbooks. The French use "pleinement fidele". The point about Cauchy-Morita completion is this: we cannot recapture a category A from its presheaf category P(A); we can only capture, up to equivalence, the Cauchy completion Q(A) of A. Given F : A --> B, if F* (or P(F) : P(B) --> P(A)) is fully faithful then the same will be true for Q(F) replacing F. For ordinary categories, Q(A) is the completion of A wrt splitting idempotents; ie, the full subcat of P(A) consisting of retracts of representables. Hence my point about F being surjective on objects up to retraction. [For additive categories, Q(A) is the full subcat of P(A) (additive ab-gp-valued presheaves) consisting of retracts of finite direct sums of representables.] +++++++++++++++++++++++++++++++++++++++++++++

1 0

Comparison between Functor Categories
by MAS034＠BANGOR.AC.UK 30 Sep '92

30 Sep '92

Dear Colleagues, let F:C -> D be a functor between two small categories. Its induced functor F^*:Fun(D,Set) -> Fun(C,Set) has both a left adjoint L and a right adjoint R. 1. Under which precise conditions on F is L F^* = Id. 2. Under which precise conditions on F is R F^* = Id. 3. Under which precise conditions on F is F^* R = Id. 4. Under which precise conditions on F is F^* L = Id. Does anybody know any answers to one of these queries? What happens if equality is replaced by natural equivalence? Does anybody know of good references to these or similar problems? Markus Pfenniger Andy Tonks School of Mathematics School of Mathematics Dean Street Dean Street Bangor, LL57 1UT Bangor, LL57 1UT UK UK ==============================================================================

6 8

None
by Robert Tennent 28 Sep '92

28 Sep '92

I'd just like to put in a plug for the philosophy behind John Reynolds's package. It doesn't attempt to perform miracles (such as global layout), but does look after messy low-level details such as shading of arrows by vertex labels. Furthermore, it has a two-level structure which allows an expert to do non-standard things without complicating life for the beginner. Bob Tennent ==============================================================================

1 0

None
by street＠macadam.mpce.mq.edu.au 28 Sep '92

28 Sep '92

I'll sit alongside Vaughan on the J"urgen Koslowski driven 2D-bandwaggon. Might I also mention strings, links, and Penrose tensor notation. I have seen papers where these are done well, but I imagine with great effort. It should be possible to describe horizontal layers with plugs for vertical stacking during which the joins are smoothed. --Ross +++++++++++++++++++++++++++++++++++++++++++++++++++++++++

1 0

Re: Diagrams in LaTeX (3 postings)
by barr＠triples.Math.McGill.CA 28 Sep '92

28 Sep '92

Ok, but that is not really a reply to a request for what is the best syntax. I tend towards the syntax of xypic, even though I think the program itself has a flaw. Obviously, you can then go on to create your own macros starting with it. I don't actually use xypic, but if I were starting fresh.... Michael +++++++++++++++++++++++++++++++++++++++++++++++++++++++++

1 0

Diagrams in LaTeX
by barr＠triples.Math.McGill.CA 27 Sep '92

27 Sep '92

A new version of LaTeX is being produced and I have agreed to participate in a subproject to decide on the best syntax for commutative diagrams. I am not at all sure that I know what the best syntax is. Mine is good for some purposes; not so good for others. There are a set of macros by Kris Rose (not specifically for LaTeX, but they will work with it) that really produce good results, but not if you put long labels on diagrams. They can be modified to work better in that case, but then get much more complicated. Then there are Paul Taylor's macros, which have advantages, but are certainly inferior to Rose's (the latter use their own fonts, which is a large reason for their superiority). Anyway, I welcome all suggestions. Michael Barr ==============================================================================

4 4

Diagrams in (La)TeX
by koslowj＠math.ksu.edu 27 Sep '92

27 Sep '92

(Yes, I'm still around --- and hope to be until December.) Concerning the recent discussion of diagrams in LaTeX: I hope that any solution that is eventually adopted is not limited to LaTeX, but can become the standard for users of plain TeX as well as of AMS(La)TeX. Moreover, the syntax should be flexible enough to allow the design of various kinds of diagrams, *and* allow customization: i.e., if I want a square like f A -------------> B | | | | g | | h | | V V C -------------> D k I want to be able to *define* a macro \square with (maybe) 8 parameters that can be called like \square AfBghCkD on top of whatever underlying syntax is provided. Moreover, I want to be able to chose the direction of the arrows (and maybe even the type of arrow) when specifying its label. E.g., \square AfB{\dl g}{\dl h}CkD should reverse the arrows g and h. Even if the new standard comes with certain pre-defined diagrams, it should be easily extensible with user-defined ones. There is another issue: 2-cells! Just look at the ever-growing importance of 2-categorical ideas. It would be highly desirable to have support for pasting 2-cells. After some experiments trying to add these (or trying to write a \cube macro) I very soon ran out of macro parameters (for a cube you need 20, while TeX only allows you 9). One can get around this limitation, but the end user should not have to bother with this. What we need is a 2 level syntax. The base level should take care of the proper placement of objects and arrow labels, while the second level should give the user easy access to a standard repertoire of diagrams that can be extended if necessary. cheers, J"urgen - J"urgen Koslowski | If I don't see you no more in this world Department of Mathematics | I meet you in the next world Kansas State University | and don't be late! koslowj(a)math.ksu.edu | Jimi Hendrix (Voodoo Chile) ==============================================================================

1 0

LICS 93 call for papers
by daniel leivant 22 Sep '92

22 Sep '92

Eight Annual IEEE Symposium on LOGIC IN COMPUTER SCIENCE June 20-23, 1993, Montreal, Quebec (Canada) CALL FOR PAPERS The LICS Symposium aims for wide coverage of theoretical and practical issues in computer science that relate to logic in a broad sense, including algebraic, categorical and topological approaches. Suggested, but not exclusive, topics of interest include: abstract data types, automated deduction, concurrency, constructive mathematics, data base theory, finite-model theory, knowledge representation, lambda and combinatory calculi, logical aspects of computational complexity, logics in artificial intelligence, logic programming, modal and temporal logics, program logic and semantics, rewrite rules, logical aspects of symbolic computing, problem solving environments, software specification, type systems, verification. PROGRAM CHAIR: Moshe Y. Vardi IBM Research Almaden Research Center, K53-802 650 Harry Rd. San Jose, CA 95120-6099, USA vardi(a)almaden.ibm.com, vardi(a)almaden.bitnet Phone: (408) 927-1784 Fax: (408) 927-2100 PROGRAM COMMITTEE: M. Abadi (DEC SRC), S. Abramsky (Imperial Coll.), B. Bloom (Cornell), P. Clote (Boston Coll.), P.J. Freyd (Univ. of Pennsylvania), D. Harel (Weizmann Inst.), K.G. Larsen (Aalborg Univ.), P. Lescanne (CRIN and INRIA-Lorraine), D. McAllester (MIT), J. Meseguer (SRI), D. Miller (Univ. of Pennsylvania), Y. Moschovakis (UCLA), N. Shankar (SRI), C. Talcott (Stanford), M.Y. Vardi (IBM Almaden), and P. Wolper (Univ. of Liege). LICS GENERAL CHAIR: Robert Constable Department of Computer Science Cornell University Ithaca, NY 14253 rc(a)cs.cornell.edu CONFERENCE CO-CHAIRS: Mitsu Okada Prakash Panangaden Department of Computer Science School of Computer Science Concordia University McGill University Montreal Montreal H3G 1M8 Quebec, Canada H3A 2A7 Quebec, Canada okada(a)concour.cs.concordia.ca prakash(a)cs.mcgill.ca PAPER SUBMISSION: 10 hard copies of a detailed abstract (not a full paper) and 20 additional copies of the cover page should be RECEIVED by DECEMBER 8, 1992 by the PROGRAM CHAIR (Attn: LICS). Authors without access to reproduction facilities may submit a single copy of their submission. Authors will be notified of acceptance by February 14, 1992. Accepted papers in the specified format for the symposium proceedings will be due April 6, 1993. The cover page of the submission should include the title, authors, a brief synopsis, and the corresponding author's name, address, phone number, fax number, and e-mail address if available. Abstracts must be in English, clearly written, and provide sufficient detail to allow the program committee to assess the merits of the paper. References and comparisons with related work should be included. It is recommended that each submission begin with a succinct statement of the problem, a summary of the main results, and a brief explanation of their significance and relevance to the conference, all suitable for the non-specialist. Technical development of the work, directed to the specialist, should follow. Abstracts of fewer than 1500 words are rarely adequate, but the total abstract, should not be longer than 10 typed pages with roughly 35 lines per page. If the authors believe that more details are essential to substantiate the main claims of the paper, they may include a clearly marked appendix to be read at the discretion of the committee. Late abstracts, or those departing significantly from these guidelines, run a high risk of rejection. The results in the submission must be unpublished and not submitted for publication elsewhere, including proceedings of other symposia or workshops. All authors of accepted papers will be expected to sign copyright release forms, and one author of each accepted paper will be expected to present the paper at the conference. The symposium is sponsored by the IEEE Technical Committee on Mathematical Foundations of Computing in cooperation with the Association for Symbolic Logic and the European Association of Theoretical Computer Science. Cooperation with the ACM is anticipated. ORGANIZING COMMITTEE: M. Abadi, S. Abramsky, S. Artemov, J. Barwise, M. Blum, A. Bundy, S. Buss, E. Clarke, R. Constable (Chair), E. Engeler, J. Gallier, U. Goltz, Y. Gurevich, S. Hayashi, G. Huet, G. Kahn, D. Kapur, C. Kirchner, R. Kosaraju, J. W. Klop, P. Kolaitis, D. Leivant, A. Meyer, G. Mints, J. Mitchell, Y. Moschovakis, A. Pitts, G. Plotkin, S. Ronchi Della Rocca, G. Rozenberg, A. Scedrov, D. Scott, J. Tiuryn, M. Vardi, R. de Vrijer PUBLICITY CHAIR: Daniel Leivant Department of Computer Science Indiana University Bloomington, IN 47405, USA lics(a)cs.indiana.edu ==============================================================================

1 0

From triposes to assemblies
by cxm7＠pop.cwru.edu 22 Sep '92

22 Sep '92

------------- Jaap van Oosten's dissertation uses triposes to develop numerous realizability toposes, and incidentally raises the question as to which of them can be presented as the effective reflection of a category of assemblies. The answer is that all of his tripos constructions actually include constructing such assemblies. I will spell this out in some generality. Let N be any partial combinatory algebra (see Jaap's dissertation p.35). Write e.m for the result of applying an element e of N to another element m. The notation suggests the natural numbers taken as codes of partial recursive functions, but everything here works for any PCA. For any subsets W and V of N, we call an element e of N a "modulus" mapping W to V iff for every m in W the value e.m is defined and is in V. More generally, we say e maps one list of subsets W1, W2, W3... to another V1, V2, V3... iff e simultaneously maps each Wi into Vi. By a "tripos based on N" I mean a tripos such that for some subset Sub of some cartesian power of the powerset of N: 1) The fiber Sigma(X) over any set X consists of suitable pairs <alpha,t> with alpha a function from X to Sub and t coding some further structure. The pre-order says <alpha,t> is smaller than <alpha',t'> iff there is a modulus mapping alpha to alpha' and that modulus meets conditions which may depend on t and t'. 2) The action of any function f:X___>Y is by composition. Given any function from Y to Sigma, compose with f to get one from X to Sigma. For many realizabilities the tags "t" are superfluous. But in extensional realizability, for example, a member of Sigma(X) is an X-tuple of subsets of N, tagged by an equivalence relation on each one and moduli must preserve those relations. We say an element x of X is "minimally realized" by a given alpha in Sigma(X) iff alpha(x) is minimal in Sigma(1). As in any tripos we define a "relation in the sense of the tripos" on a set X to be a member of the fiber over XxX. The tripos construction of the topos works by taking as objects all pairs (X,=) where "=" is a partial equivalence relation in the sense of the tripos on the set X. The arrows are all functional relations between these pers, and the result is a topos. But in a tripos based on N we can instead take only those pairs (X,=) such that <x,y> is minimally realized by = unless x=y. These generalize the canonically separated objects in the effective topos. Together with the same arrows they form a regular category. Every partial equivalence relation on X in the sense of the tripos contains a canonically separated = such that, for any pair <x,y> non-minimally realized in the relation both <x,x> and <y,y> are non-minimally realized in =. By the soundness of tripos logic, equivalence relations and functional relations IN THE CATEGORICAL SENSE in the regular category correspond exactly to those in the tripos sense. I.e. the tripos's topos is also the effective reflection of this regular category. It only remains to note that a canonically separated = virtually is an assembly and for this special case the functional relations correspond to actual functions between carriers with moduli. A canonically separated = on X amounts to a function from X to Sigma taking each x in X to the value =<x,x>. If Sub is contained in the powerset of N then such a function gives a relation from X to N and can be given in terms of caucuses: for each n in N the n-th caucus of the assembly is the set of all x in X related to n. If Sub is contained in the I-fold cartesian power of the powerset then we get a distinct series of caucuses for each i in I. For each i we will call these the i-caucuses, so that for each n in N there is an n-th i-caucus. The tags "t" in the fibers can be kept as tags on the assemblies. The "carrier" of = is the set of all x in X with <x,x> non-minimally realized by =. A functional relation F in the sense of the tripos from (X,=) to (Y,=') amounts to an ordinary function F from the carrier of = to the carrier of =', which has a modulus. Here "modulus" means an element e of N which, for each x in the carrier of =, maps the Sigma element =<x,x> to the Sigma element ='<Fx,Fx> compatibly with the tags. In other words, let Sub be a subset of the I-fold cartesian power of the powerset of N. Then a modulus for F is a member e of N such that: for every i in I and n in N, if a member x of X is in the n-th i-caucus of = then e.n is defined and Fx is in the e.n-th i-caucus of ='; and e meets any conditions set by tags on = and ='. On his p.4 Jaap gives data for a tripos for each of some dozen kinds of realizability. His Sigma for each kind is our Sigma, and specifies what PCA each kind uses. His material implications tell which moduli are allowed. The present construction applied to his Kleene tripos gives the familiar assemblies for the effective topos. It should be clear that such assemblies and tags restricting the moduli can be described directly. On that approach, you have to show that they give a cartesian closed regular category with weak subobject classifier. That verification will be a lot like checking the Beck condition and the generic predicate in a tripos. In effect, the regular category uses the same data as the tripos only without the indexed pre-order structure. Any such regular category has a topos as effective reflection, and forms the separated objects of the topos. The method is due to Freyd and can be gleaned from Freyd and Scedrov _Categories, Allegories_. The actual statement and proof are given in Ch.25 of my _Elementary categories, elementary toposes_. Again, it is a close parallel to part of the proof that triposes give toposes, but omits much. ==============================================================================

1 0