Subj:	Integration of Yoneda
Date: Tue, 1 Sep 92 14:06:05 +1000
From: street@macadam.mpce.mq.edu.au

In 1968, I was a postdoc at the University of Illinois auditing John Gray's
graduate course on categories. I believe John had learned that every
functor into sets was a canonical colimit of representables from
Gabriel-Zisman: I don't think they give a reference.

Coming out of his work on extraordinary naturality with Sammy and on
enriched functor categories, Max Kelly had defined (sometime between La
Jolla and 1967) the notion of "end" for enriched categories. While browsing
in the Illinois Math Dept Library I actually READ Yoneda's paper "On Ext
and exact sequences" J Fac Sci U Tokyo 8 (1960) 507-576. I saw that Yoneda
had already discovered ends for additive categories, but had not called
them that. Yoneda used the integral notation for ends, which I recommended
to Brian Day and Max, and they adopted it for their SLNM 106 article. I was
learning lots about comma categories from Gray and enjoying translating it
into ends to extend the results to enriched categories. 

Therefore, I claim that Yoneda pre 1960 was well aware of:

(i) the end formula nat(f,g) = end(f->g) for the set (or object) of natural
transformations;

(ii) the coend formula 
                        f = coend(A(a,-)*f)
expressing each functor into sets (the base) as a canonical colimit of
(generalised) representables ("Fourier-like theorem"); 

(iii) the Lemma which category theorists associate with his name, viz,     
            
                        end(A(a,-)->f) = fa. 

[I write *, -> for tensor, cotensor, resp.]

I also suspect Isbell must have known of the adequacy of the canonical
embedding into presheaves in "Adequate subcats" Ill J 4 (1960) 541-552 but
have no time now to check.
Best regards,
         _________________________________________________________
        /          Ross STREET, Professor of Mathematics          \
       / School of Mathematics, Physics, Computing and Electronics \
      /     Macquarie University, New South Wales 2109, AUSTRALIA   \
     /       Telephone: 61-2-805-8946   Facsimile: 61-2-805-8241     \ 
    /-----------------------------------------------------------------\

==============================================================================
Subj:	CTCS Conference
Date: Wed, 2 Sep 92 15:44:45 BST
From: David Rydeheard <david@computer-science.manchester.ac.uk>




                                 1993
              ********* Preliminary Announcement ***********
              *                                            * 
              *    CATEGORY THEORY AND COMPUTER SCIENCE    *
              *    ------------------------------------    *
              *                                            *  
              *          Fifth Biennial Meeting            * 
              *                                            *
              **********************************************
                       
                                CTCS-5
    
                 Dates: 7th-10th September 1993.
                 Venue: CWI, Amsterdam, The Netherlands.


The fifth of the biennial conferences on category theory and computer science
is to be held in Amsterdam in 1993. 

The purpose of the conference series is the advancement of the foundations of
computing using the tools of category theory, algebra, geometry and logic.
Whilst the emphasis is upon applications of category theory, it is recognised
that the area is highly interdisciplinary and the organising committee welcomes
submissions in related areas. Topics central to the conference include:
        *   The semantics of computation
        *   Program logics and specification
        *   Type theory and its semantics
        *   Domain theory
        *   Linear logic and its semantics
        *   Categorical programming
Submissions purely on category theory are also acceptable as long as the
applicability to computing is evident.

Previous meetings have been held in Guildford (Surrey), Edinburgh, Manchester
and Paris. The format of this fifth meeting is to differ from previous meetings. Abstracts of talks are to be submitted to the organiser (details below).
These will undergo a preliminary selection procedure and authors will be
notified of the result.  Proceedings of the conference will appear in a special issue of the
journal Mathematical Structures in Computer Science.  All contributors
to the conference will be invited to submit full papers to the special issue.
Submissions will undergo the usual refereeing process for MSCS,
which accepts only very high standard contributions.

Organising and program committee:  
      S. Abramsky,  P.-L. Curien, P. Dybjer, G. Longo, G. Mints, 
      J. Mitchell, E. Moggi, D. Pitt, A.Pitts, A. Poigne, D. Rydeheard, 
      F-J. de Vries, E. Wagner.

IMPORTANT DATES

      Submission of abstracts of talks     25th May 1993
      Notification of acceptance           1st July 1993

Submission of Abstracts.
 
      Authors should send 3 hard copies of an abstract and a cover
      page (preferably in 11pt LaTeX format) to: 

          Dr. David Pitt, 
          Department of Mathematics
          University of Surrey,
          Guildford, Surrey GU2 XH
          United Kingdom.

          email: d.pitt@mcs.surrey.ac.uk 
      Authors without access to reproduction facilities may submit a 
      single copy of their submission. 

      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 should consist of no more than 3 (three) A4 sides (not 
      including references). They must be in English, clearly written, and 
      provide sufficient detail to allow the program committee to assess 
      the merits of the paper.  Each submission should make clear the 
      advances made by the authors, the relevance to the subject, the 
      background involved and the relationship to other work in the
      area. 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.

Local Arrangements: These will be notified later. The local co-ordinator is:

	  Dr. Fer-Jan de Vries
	  Department of Software Technology
   	  CWI
	  Kruislaan 413
	  1098 SJ Amsterdam
	  The Netherlands

          email: F.J.de.Vries@cwi.nl
==============================================================================
Subj:	paper available by ftp
Date: Thu, 3 Sep 1992 14:18:24 +0100 (BST)
From: Samson Abramsky <sa@doc.ic.ac.uk>

The following paper is now available by anonymous ftp from
theory.doc.ic.ac.uk, in papers/Abramsky. Anyone needing a hard copy
should send me their postal address.

--------

\documentstyle[11pt]{article} 


\begin{document} 
\bibliographystyle{alpha}
\title{Games and Full Completeness for Multiplicative Linear Logic}
\author{Samson Abramsky and Radha Jagadeesan \\
Imperial College.}

\maketitle

\begin{abstract}
We present a game semantics for Linear Logic, in which formulas denote
games and proofs denote winning strategies.  We show that our semantics
yields a categorical model of Linear Logic and prove  {\em full
completeness} for Multiplicative Linear Logic with the MIX rule: every
winning strategy is the denotation of a unique cut-free proof net.  A key
role is played by the notion of {\em history-free} strategy; strong connections
are made between history-free strategies and the Geometry of Interaction.
Our semantics incorporates a natural notion of polarity, leading to a
refined treatment of the additives.  We make comparisons with related work
by Joyal, Blass {\it et al}. 
\end{abstract}

\end{document}

==============================================================================
Subj:	Re: 4 colours
From:	Richard Wood <rjwood@cs.dal.ca>
Date:	Tue, 8 Sep 1992 11:43:01 -0300

Please also note "A categorical characterization of the four colour 
theorem"by Barry Fawcett, Canad. Math. Bull. Vol. 29 (4), 1986, perhaps the
main result of which is the equivalence of the four colour theorem
with the statement that epimorphisms are surjective in the category
of planar graphs.

Wood
==============================================================================
Subj:	Commutative Diagrams in TeX - NEWS
Date:        Mon, 07 Sep 92 17:14:06 ADT
From:     Paul Taylor <pt@doc.ic.ac.uk>

		===============================================
		Commutative Diagrams in TeX - towards version 4
		===============================================

This message brings news of the development of my TeX package for drawing
"commutative" diagrams, which is now widely used in the category theory and
theoretical computer science communities. It is being sent directly to all of
the users I know of (who have requested it by electronic mail or FTP from me,
or asked questions about it), but as I know the package has been passed on,
I would be grateful if you would
  **************************************************************************
  * copy this message to anyone to whom you have given the package itself. *
  **************************************************************************

The package was originally advertised on the "types" and "categories"
electronic mailing lists in July 1990. In the following eighteen months some
fixing of bugs took place, but there was little substantial change.

Since April 1992, I have re-written most of the code, largely with a view
to improving the geometrical layout of the diagrams. Before completing this
work and calling it version 4, I would like some feedback from users.

One of the areas which I have neglected in the past (largely because TeX makes
it so difficult) is diagonal arrows. The code for drawing these using LaTeX
line segments has been re-written: now the closest available slope is chosen
automatically and the commands have names similar to the horizontals and
verticals.

However to do a better job of diagonals (and in future to support curved lines)
some extension to TeX is needed. Being extensions they are necessarily not
standard. Three possibilities are:
(1) additional fonts (as, for example, used by Spivak's Lamstex). However my
    experience of design-size fonts and linear logic symbols suggests that for
    users without expert knowledge or control of their local TeX systems this
    is more trouble than it's worth.
(2) PostScript is, I believe, now almost universally used as the language in
    which TeX documents are sent to a printer. PS commands can be embedded in
    DVI files and incorporated in the PS translation without extra system or
    user files or any user intervention. This is to some extent dependent on
    which DVI->PS translator is used. In the new version this is exploited
    in an option to implement diagonals by rotating horizontals, which works
    with Tomas Rokicki's "dvips".
(3) TPIC is a graphics extension of TeX which uses a simpler set of embedded
    commands. These can be used to draw diagonal lines and curves but not to
    perform rotations; they are, however, understood by Vojta's "xdvi" as well.
    Another option in the new version uses these to draw diagonal lines.

Besides diagonals, the code for adjusting horizontal and vertical arrows has
been completely rewritten and does a much better job of the geometry. Many of
the problems with alignment, positioning and gaps have been fixed automatically,
and greater control is given to the user to adjust those which cannot be.
There are also several new options for the placement of the finished diagram
on the page.

Arrow commands are now declared in a much simpler way. The declaration
	\newarrow{CrossedInto}{hook}-+->
is now all that is needed to define the example \rCrossedInto in the manual,
along with the corresponding left, down, up and diagonal commands. Another
option makes a consistent selection of arrowheads for all arrows, from a choice
of vee, LaTeX, curlyvee, triangle and blacktriangle.

So much for selling you the new version. The reason for mailing you and asking
for comments before completing what I intend to do for version 4 is that I want
to get feedback on the following questions:

(1) Can you use FTP (file transfer protocol)? This is the easiest method of
    distribution for me and for you, and there is now a huge volume of public
    domain software available by this method. My archive is called
	theory.doc.ic.ac.uk	(146.169.2.37)
    and the diagrams package is in the directory /tex/contrib/Taylor/tex.
    Please try to fetch the new version and manual by this method.

(2) If you can't use FTP, and your electronic mail passes via non-ASCII
    machines (particularly BITNET), what characters tend to get corrupted?
    The new version uses a restricted character set to avoid this problem.

(3) Do you have available for printing final copy a printer which understands
    Adobe PostScript, for example an Apple or Sun laserwriter?  Who is the
    author of the DVI->PS translation program you use? Please fetch the new
    version, try the PostScript option and tell me if you have any difficulty
    printing. (You may have to change the \verbatim@ps@special macro if you
    don't use Rokicki's dvips: if so, please send me details.)
    You can preview with a PS previewer such as PageView under OpenWindows or
    GhostView/GhostScript under Xwindows.

(4) Do your DVI translators and previewers understand TPIC \specials (as used
    in eepic.sty)? Please try the TPIC option. I would like to know whether
    it is worth putting effort into PostScript, TPIC or some other method.

(5) Have you defined your own arrow commands using \HorizontalMap, \VerticalMap
    or \DiagonalMap?  Please use "grep alMap *.tex *.sty" or some similar
    command to find out, and tell me if you have used any components other
    than those in the source of version^3. It is in your interests to do this,
    because \newarrow defines arrow commands in a different way.

(6) Please tell me if you have any difficulty adapting to the new version, or
    any general comments about doing so which might be of benefit to other
    users.

(7) Other comments: have you used other packages for drawing diagrams? Do you
    have applications for my package other than the categorical diagrams for
    which it was designed? What do you see as the major limitations of the
    package? What persuaded you to use it, or not to use it?

Version numbers:
 2    was circulated to some people in September 1989
 3.16 was advertised on types & categories in July 1990 and emailed to those
      who asked for it.
 3.18 was the final bug-fix before the re-write began in April 1992.
 3.20 introduced error-recovery, and \newarrow for horizontals & verticals
 3.22 completely rewrote the reformatting program for h & v and corrected
      numerous alignment errors; introduced options in square brackets
 3.23 fixed a catastrophic error in nested diagrams
 3.24 (current) extended \newarrow to diagonals, added trigonometry code,
      rewrote code for drawing LaTeX diagonals, introduced PostScript and
      TPIC diagonals, consistent choice of arrowheads.
It will be called "version 4.0" when the diagonals are adjusted to meet their
endpoints (the one remaining big project, which could not be done before the
others above) and I have dealt with my list of minor quibbles.

Paul Taylor,						7 September 1992
Department of Computing,
Imperial College of Science, Technology & Medicine,	+44 71 589 5111 x 5057
180 Queen's Gate,					+44 71 581 8024 (FAX)
South Kensington,
London SW7 2BZ, UK					pt@doc.ic.ac.uk
==============================================================================
Subj:	Extraductions from topos theory
Date: Wed, 09 Sep 92 12:49:48
From: sjv@doc.ic.ac.uk (Steve Vickers)

It's common and not unreasonable to give an introduction to topos theory by 
starting from motivations in various subjects including algebraic topology 
and geometry. MacLane and Moerdijk explain these motivations in some detail, 
and of course the original papers on toposes presupposed knowledge of 
algebraic geometry.

But I feel that I understand toposes better than the motivating subjects.

Does anyone know of any good "extraductions from" topos theory that use 
topos intuitions to help introduce the concepts and methods of algebraic 
topology and algebraic geometry?

Steve Vickers.
==============================================================================
Subj:	Re: 4 colours
Date: Tue, 8 Sep 92 13:31:07 EDT
From: pavlovic@triples.Math.McGill.CA (Dusko Pavlovic)

Thanks, Richard. As you could see if you FTP-ed my note, I did quote
Barry Fawcett's characterisation (and thanked Robert Pare for
mentioning it to me). I also explained that Fawcett's approach is, in
a sense, dual to mine. I hope I'll be able to say more about this in
another note.
	Best regards,
	Dusko Pavlovic
==============================================================================
Subj:	Re: Extraductions from topos theory
From: ramu@cadsun.corp.mot.com
Date: Wed, 9 Sep 92 09:25:17 CDT

-> Date: Wed, 09 Sep 92 12:49:48
-> From: sjv@doc.ic.ac.uk (Steve Vickers)

-> Does anyone know of any good "extraductions from" topos theory that use 
-> topos intuitions to help introduce the concepts and methods of algebraic 
-> topology and algebraic geometry?

A. Koch, Synthetic Differential Geometry, Cambridge University Press,
1980 (?). 

--Ramu Iyer

Email: ramu@cadsun.corp.mot.com

==============================================================================
Subj:	FMCS workshop report
Date: Tue, 15 Sep 92 11:15:05 -0700
From: David B. Benson <dbenson@eecs.wsu.edu>

	Foundational Methods in Computer Science:
	A workshop on applications of categories
		in computer science

		1992 May 30-31

		Sloan Hall
	School of Electrical Engineering and Computer Science
	Washington State University, Pullman WA 99164-2752


The workshop was organized by David B. Benson with assistance from
Purandar Bhaduri.  Robin Cockett and Dwight Spencer helped set the
workshop scope and atmosphere.   Notably, the workshop was almost
entirely organized via email.  Essentially only the preregistration fees
passed through the postal services.

The invited hour speakers were Robin Cockett, Steve Bloom, Ernie Manes,
and Bob Walters.  The workshop was preceeded by a one day introduction
to categories.  A majority of the workshop participants attended these
tutorials.

The workshop was informal, even casual.  Everyone seemed to enjoy and
profit from this organization of a workshop around an idea and style
which has many applications.

In keeping with the spirit of sharing the latest scientific and technical
information, there will be no workshop proceedings.  We expect many of
the presentations to develop into monographs and journal papers.


Scientific program
------------------

Friday, 1992 May 29

0900-1130 Introduction to categories for computer science  (D. B. Benson)
1300-1430 Introduction to monads (E. G. Manes)
1530-1700 Introduction to categorical logic (P. Bhaduri)

Saturday, 1992 May 30

0900-1000 Robin Cockett: Distributive Matters, Data, Charity and Programming
1020-1040 Tom Fukushima		Monads in Charity
1040-1100 Dick Kieburtz		Involution and Duality
1120-1140 Jim Hook		Program Development inspired by monads
1140-1200 Juergen Koslowski	Computational monads in programming languages

1400-1500 Steve Bloom:	 Iteration Theories and Initiality
1520-1540 Francoise Bellegarde	ASTRE: Program transformation and rewriting
1540-1600 Purandar Bhaduri	Functorial view of concurrency
1600-1620 Mike Levy (for Bill Wadge) Monads and intensionality
1620-1640 Rakesh Dubey		On a general definition of safety and liveness

Sunday, 1992 May 31

0900-1000 Ernie Manes:	 Boolean categories
1020-1040 John MacDonald    	Soft Adjunction I, Introduction
1040-1100 Art Stone          	Soft Adjunction II, Examples

1300-1400 Bob Walters:	 An imperative language based on distributive categories
1420-1440 Carolyn Brown		A categorical approach to concurrency
1440-1500 Wafaa Khalil		A universal IMP(G) program
1500-1520 Eric Wagner		About and around distributive categories


Participants (27)
------------

Karl Abrahamson		<karl@eecs.wsu.edu>
Francoise Bellegarde	<bellegar@cs.wwu.edu>
David B. Benson 	<dbenson@eecs.wsu.edu>
Purandar Bhaduri	<pbhaduri@eecs.wsu.edu>
Steve Bloom 		<bloom@sparc1.stevens-tech.edu>
Carolyn Brown 		<cbrown@cs.chalmers.se>
Robin Cockett 		<robin@cpsc.ucalgary.ca>		
Rakesh Dubey		<rdubey@eecs.wsu.edu>
Tom Fukushima 		<fukushim@cpsc.ucalgary.ca>	
Mike Herman
James Hook 		<hook@cse.ogi.edu>	
Wafaa Khalil 		<moynham_w@maths.su.oz.at>
Dick Kieburtz 		<dick@aquila.cse.ogi.edu>		
J"urgen Koslowski 	<koslowj@cis.ksu.edu> 		
Mike Levy 		<michael_levy@csr.uvic.ca>	
John C. MacDonald	<macstone@bcu.ubc.ca>	
Ernest G. Manes 	<manes@math.umass.edu>
Neal Nelson 		<nealn@cse.ogi.edu>
Raja Nagarajan		<raja@cpsc.ucalgary.ca>
Tom Rigles		<TRIGLES%ewuvms.BITNET@CORNELLC.cit.cornell.edu>
Marc Schroeder
Tim Sheard 		<sheard@cse.ogi.edu>	
Dwight L. Spencer 	<dwights@cse.ogi.edu>	
Art Stone 		<macstone@bcu.ubc.ca>
Eric Wagner 		<wagner@watson.ibm.com>
Bob Walters 		<walters_b@maths.su.oz.au>	
Barry Yee


ftp sites
---------

Here are ftp sites at which preprints of presented or related papers
may be obtained.

maths.su.oz.au
	anonymous login
	your email address as password
	directory sydcat

cpsc.ucalgary.ca
	anonymous login
	ident as password
	directories: pub/charity for the charity system
		     pub/charity/PAPERS for papers related to charity


ftp.eecs.wsu.edu
	anonymous login
	your email address as password
	directory pub/papers
	


-- submitted by
David B. Benson
School of Electrical Engineering and Computer Science
Washington State University
Pullman WA 99164-2752
==============================================================================
Subj:	operads and n-cats
Date: Thu, 17 Sep 92 13:54:24 GMT-0400
From: jds@rademacher.math.upenn.edu

\magnification = \magstep2
\centerline{GRADUATE STUDENT ALGEBRA SEMINAR}
\centerline{CONFORMAL FIELD THEORY }
\vskip3ex
\centerline{Tuesdays at Noon}
\vskip2ex
\centerline{Room ?4E17? DRL}
\vskip2ex
\centerline{Introduction and Overview}
\vskip2ex
\centerline{Y.-Z. Huang}
\vskip2ex
\centerline{Tuesday September 15}
\vskip3ex
\vskip3ex
\centerline{CONFORMAL FIELD THEORY SEMINAR}
\vskip3ex
\centerline{Tuesdays at 3:10}
\vskip2ex
\centerline{Room ?4E17? DRL}
\vskip2ex
\centerline{Introduction to Operads}
\vskip2ex
\centerline{Jim Stasheff - UNC and U Penn}
\vskip2ex
\centerline{Tuesday September 22}
\vskip3ex
An operad is an algebraic/topological gadget for keeping track of
multiparameter families of maps $X^n\rightarrow X^k$.  Originally 
invented for the homotopical characterization of iterated (based)
spaces of loops, the special example of disks within disks within disks...
has recently been observed within conformal field theory.
There is also some relevance to n-categories.
\end
==============================================================================
Subj:	LICS 93 call for papers
Date:        Tue, 22 Sep 92 02:55:05 ADT
From: "daniel leivant" <leivant@moose.cs.indiana.edu>

                    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@almaden.ibm.com, vardi@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@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@concour.cs.concordia.ca    prakash@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@cs.indiana.edu
==============================================================================
Subj:	From triposes to assemblies
Date: 21 Sep 92   16:58:04 EST
From: <cxm7@pop.cwru.edu> Colin McLarty

-------------

	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.

==============================================================================
Subj:	Comparison between Functor Categories
Date: Wed, 23 Sep 92 14:17 GMT
From: MAS034@BANGOR.AC.UK

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
==============================================================================
Subj:	Re: Comparison between Functor Categories
Date: Wed, 23 Sep 92 14:19:16 EDT
From: barr@triples.Math.McGill.CA (Michael Barr)

The first thing to note is that your question, as stated, is
meaningless.  The proper statement is that the induced functor has
left and rights adjoints.  If for one of them, one of the composites
you mention is naturally equivalent to the identity, then another
could be chosen (using AC) for which the composite in question was
equal to the identity.  On the other hand, in the usual set theory,
the usual construction that shows that adjoint exists will use more
complicated sets than the functor and thus the composite will never
be the identity.  Thus the only question that can meaningfully
raised is when one or the other of the composites is naturally
equivalent to the identity.  I think sufficient conditions are
known, although I don't recall them offhand, but it seems awfully
unlikely to me that useful necessary and sufficient conditions are
known.

Michael Barr
==============================================================================
Subj:	Re: Comparison between Functor Categories
Date: Thu, 24 Sep 92 12:40:45 +1000
From: street@macadam.mpce.mq.edu.au

Since L and R are only determined up to isomorphism, how can one ask 
for equalities like F^* R = Id? 
Ross
==============================================================================
Subj:	Diagrams in LaTeX
Date: Thu, 24 Sep 92 14:51:44 EDT
From: barr@triples.Math.McGill.CA (Michael Barr)

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
==============================================================================
Subj:	Re: Comparison between Functor Categories
Date: Thu, 24 Sep 92 11:09:50
From: sjv@doc.ic.ac.uk (Steve Vickers)

>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
  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
<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<

I don't know the answers. However, I can describe an analogous context (ring 
theory) where there is a surprising answer to 2: the appropriate analogue 
holds iff F is an epimorphism. Perhaps someone already knows whether the 
corresponding conjecture is true in the category (or monoid) context, and 
anyway perhaps the different perspective will cast light on the problem.

First, as Mike Barr points out, natural equivalence is the appropriate 
property to look for, and in fact I don't know how you might go beyond the 
question of when the units or counits of the adjunctions are natural isos.

If R is a ring, then the category of (right, say) modules over R is very 
like a functor category. R _is_ a category (one object, lots of morphisms), 
and a module is a functor from R to Abelian Groups. Of course, it's more 
special than that, because we also require that the functor should preserve 
the additive structure. However, the idea that a functor F from a category C 
to Sets is a kind of module is quite a natural one. The "elements of the 
module" are the elements of the sets F(i) where i ranges over objects of C, 
and a morphism f: i -> j of C "acts on" the elements (at least, those in 
F(i)) by xf = F(f)(x). You'll see this more clearly in the case where C is a 
monoid (only one object).

This perspective is explained in Popescu, "Abelian categories with 
applications to rings and modules" (LMS Monographs 3, Academic Press, 1973).

It extends readily to "ringoids", i.e. categories enriched over Abelian 
groups (Barry Mitchell "Rings with several objects", Advances in Mathematics 
37 (1972) 1-161).

If F: R -> S is a ring homomorphism, then you get a functor F^*: Mod-S -> 
Mod-R ("restriction of scalars") with left adjoint L, M |-> M tensor_R S, 
and right adjoint R, M |-> S hom_R M.

It is known that the counit of the adjunction L -| F^* is a natural iso if 
and only if F is an epimorphism in the category of rings. (See, e.g., 
Stenstro"m "Rings of Quotients", Springer 1975.) (Note that epimorphisms are 
not always surjective - e.g. the embedding of the integers in the rationals 
is epi.)

This is also true for ringoids (I believe it's in Mitchell's paper).

It's conceivable that the direct analogue holds for categories, i.e. (2) (in 
suitable form) iff F is an epimorphism in the category of (small) 
categories, though at first glance the proof in Stenstro"m doesn't seem to 
generalize.

If you look into this, I'd suggest you study the monoid case first.

Steve Vickers
==============================================================================
Subj:	Re: Diagrams in LaTeX
From: cbj@dcs.ed.ac.uk
Date: Fri, 25 Sep 92 11:11:13 +0100


Michael Barr writes:

> 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.

.....

> (the latter [Rose's macros] use their own fonts, which is a
> large reason for their superiority).


Without having any knowledge of Rose's package, I would much prefer to
have complete flexibility in the choice of labels. Two reasons for
this are: 

(i) labels in the diagrams should agree with those in the text, and;
(ii) fonts change more rapidly than diagram styles. 

One further point comes to mind. If other fonts can't be imported,
then perhaps other macros can't be used either. For example, one might
use arrays to label linear transformations. I suggest as a design
criterion that 

	Any box should be admissible as a label.

Barry Jay
==============================================================================
Subj:	Re:  Comparison between Functor Categories
Date: Fri, 25 Sep 92 15:37:23 EDT
From: pavlovic@triples.Math.McGill.CA (Dusko Pavlovic)

>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.

(I guess some people know the precise answers at once, but don't
bother to tell us. Here is what I figured.)

Suppose, as M.Barr and R.Street promptly suggested, that the equalities in the
query denote the natural isos. Of course,
	* 1 and 2 are equivalent: they mean that F^* is fully faithful; and
	* 3 and 4 are equivalent: they say that the essential morphism
	of toposes R: (D,Set)-->(C,Set) is an injection.

A sufficient condition for 1 and 2 is that F:C-->D is a stably initial
functor.  (Initial functors are orthogonal to discrete opfibrations:
cf. e.g. "The comprehensive factorisation of a functor" by Street and
Walters, early seventies. Now F^* is pulling back of discrete
opfibrations along F. Use orthogonality to show that it is fully faithful.)

A sufficient condition for 3 and 4 is that F is fully faithful. (Just
write down the pointwise Kan-extension formula for L (or R): to
calculate F^*L(G) at X from C, we use the diagram obtained by
projecting the comma category F/FX to C; we apply G on this diagram
and calculate the colimit. When F is fully faithful, this diagram is
just a cocone to X - so the colimit is GX.)

Now what are the necessary conditions?

	Best regards,
	Dusko Pavlovic
==============================================================================
Subj:	Re: Diagrams in LaTeX
From: Paul Taylor <pt@doc.ic.ac.uk>
Date: Fri, 25 Sep 1992 18:54:07 +0100

Mike Barr has pointed out that some La/TeX packages for commutative diagrams
or general graphics use specially provided fonts.  My own experience with
*any* divergence from the fonts provided in bog-standard TeX distribution
causes more trouble than it's worth: witness the design size (Sauter) fonts
in particular. (Incidenatlly, these are now no longer used by default in our
local LaTeX implementation, and so should not be needed when fetching dvi files
from our archive at theory.doc.ic.ac.uk).

*Not* using extra fonts is listed as one of the design criteria of my diagrams
package.  Nevertheless, unlike any of the others I've seen (including Mike's)
it does provide facilities for you to define arrow heads in terms of whatever
fonts you like. If there is demand (which I haven't heard) I am willing to
include macros for using other fonts within my package.

However fonts are a red herring: where Mike came in was on the *syntax* of
macros for expressing diagrams. With respect, but since he has thrown down
this gauntlet, I find it amazing that the author of a package with as bizzare
a syntax as his, who has submitted to this list a LaTeX document which
directly conflicts with the recent developments in LaTeX, should be involved
in proposing an authoritative syntax.

A great deal of thought and work has gone into the design of the language in
my package. Indeed there are many features I could have added but haven't
because I haven't thought of the right language for expressing them.

=============

Last week I was reading a recent paper which used my diagrams (I'm not going
to say whose). The version used must have been about five years old and
really made me cringe, because of the bugs in it which were fixed long ago.
If you have a version dated before July 1990 or which is undated *PLEASE*
throw it away and use a new one. The diagrams look so much better nowadays!
If there are any problems, I shall be happy to help.

Paul

==============================================================================
Subj:	Re: Diagrams in LaTeX
Date: Fri, 25 Sep 92 20:11:01 EDT
From: barr@triples.Math.McGill.CA (Michael Barr)

I should clarify, for the benefit of those who think I meant that
xypic (the package in question) uses its own fonts for the arrow sources
or labels, I should clarify that it uses the ordinary TeX fonts except for
the arrows.  These are built from line segments at 256 different slopes,
giving angular resolution of 256/180 = .7 deg and 512 half arrowheads
giving arrowheads at that many angles.  The arrowheads are extremely 
graceful, more elegant than those in ordinary Tex and massively more
elegant than those of latex.  Other than that, it uses whatever your
symbol font is.  For example, you could substitute the concrete math
fonts, if you wanted.  

I have gotten several replies, the most interesting from David Benson
who feels that xypic is probably the best, but that there shouldn't
be just one, but a choice.  He feels that a package that makes it
hard to draw a complicated diagram that *also* has complicated arrow
labels should be encouraged, so that people tempted to use such a
horror be discouraged.  Perhaps I have stated it a bit more strongly than
he would, but that is the thrust of his remarks.

Michael
==============================================================================
Subj:	Diagrams in (La)TeX
From: koslowj@math.ksu.edu (Juergen Koslowski)
Date: Sat, 26 Sep 92 11:54:27 CDT

(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@math.ksu.edu      |                         Jimi Hendrix (Voodoo Chile)
==============================================================================
Subj:	Re: Comparison between Functor Categories
Date: Sat, 26 Sep 92 14:43:15 +1000
From: street@macadam.mpce.mq.edu.au

There is a need to say a few more elementary things on this question. My
initial reply was short because I was busy teaching an intensive on-campus
distance course, and I hoped someone else would respond in more detail. 

    The equality question is meaningless. Also, the term "natural
equivalence" is a term used "classically" by category theorists, but not a
very good one; I suggest we should try to avoid it since "equivalence"
means something else.

    Let F : C --> D be a functor and let L --| F* --| R as in the question.
Let 
   e : L F* --> 1,  n : 1 --> F* L,  e' : F* R --> 1,  n' : 1 --> R F*
be the counits and units for the adjunctions.

Fact 1: 
    n invertible iff L fully faithful iff R fully faithful iff e'
invertible.

Fact 2:
    e invertible iff F* fully faithful iff n' invertible.

So there are really only two problems (as I just notice Dusko Pavlovic has
pointed out): 
        (a) when is L fully faithful?
        (b) when is F* fully faithful?

Answer to (a): L fully faithful iff F is fully faithful.
Proof: Since we are taking Kan extensions along F of functors into Set,
there are formulas for L (pointwise left Kan extension). Any formula can be
used to show F fully faithful implies n invertible, so L is fully faithful.
This must be in all the textbooks (eg Mac Lane). Conversely, there is a
square which commutes up to isomorphism (or equality if we choose L
suitably on representables) involving L, two Yoneda embeddings, and F^op :
C^op --> D^op. If L is fully faithful, so is F^op (since the Yon embs are),
and so, so is F./////

Now some comments on (b): 

        (i) Let's call F a "localization" when there exists a set S of
arrows in C for which F is the universal functor out of C inverting the
arrows of S. Given F, if there is an S, the set of arrows inverted by F is
the largest such S. Localizations are bijective on objects. Localizations
are coinverters of natural transformations between functors into C. If F is
a localization, it follows that F* is an inverter of some natural
transformation and hence is fully faithful.

        (ii) F* fully faithful does NOT imply F localization. For, if F
induces an equivalence of categories on the cauchy (idempotent splitting)
completions of C, D it will still have F* fully faithful, but need not have
F bijective on objects. 

        (iii) F* conservative (= reflects isos) iff e epic iff each object
d of D is a retract of an object Fc for c in C.

        (iv) These things suggest to me that the answer to (b) could be: 
    "F* fully faithful iff each object of D is a retract of an object in
the image of F, and F = G H with G fully faithful and H a localization".

However, localizations in Cat are notoriously difficult to characterize
(easier in Lex, Rex, Pb, . . .).  

The above goes over to enriched categories with appropriate change in the
notion of cauchy completion (and epic in (iii) becomes extremal epic); eg,
additive categories for the context of Steve Vickers' response.  
           
Regards,
Ross

==============================================================================
Subj:	Re: Diagrams in LaTeX
Date: 26 Sep 92 15:36:10 PDT (Sat)
From: pratt@cs.stanford.edu


I didn't reply to the diagram syntax question because I couldn't come
up with a phrasing of my druthers that adequately hid how much larger
my eyes were than my mouth.  But J"urgen just now expressed what I
really wanted beautifully, so let me add my vote to his request.

-Vaughan Pratt
==============================================================================
Subj:	Re: Diagrams in LaTeX (3 postings)
Date: Sun, 27 Sep 92 12:13:12 EDT
From: barr@triples.Math.McGill.CA (Michael Barr)

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

+++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Date: Mon, 28 Sep 92 09:53:52 +1000
From: street@macadam.mpce.mq.edu.au

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

+++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Date: Mon, 28 Sep 92 09:45:29 BST
From: Robert Tennent <rdt@dcs.ed.ac.uk>

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

==============================================================================
Subj:	Re: Comparison between Functor Categories
From:	Al Vilcius <vilcius@mathstat.yorku.ca>
Date:	Mon, 28 Sep 1992 00:51:48 -0400

In the Comparison between Functor Categories question from Bangor
Sept 23, we had a functor F:C->D, but now instead of Set, consider an
arbitrary category A and the induced functor  A^F:A^D->A^C.
Left and right adjoints, when they exist, are patched together from Kan
extensions.  For any particular  T  in A^C, we could have Ran_F(T),
Lan_F(T) in A^D  with  n.t.(S,Ran_F(T)) iso n.t.(A^F(S),T)
or  n.t(Lan_F(T),S) iso n.t.(T,A^F(S))  which occurrences we call right
or left Kan extensions of T along F.  These are approximations of the
variable object  T  by images of A^F, which I think of heuristically as a
sort of Dedekind cut situation, in my own naive way, as follows:
think of those S in A^D for which SF<=T and call the Lower
also think of those S for which T<=SF and call them Upper
here SF=A^F(S) of course, and X<=Y just means there is some n.t. X->Y.
Then A^F images of Lowers approximate T from below, and Uppers from
above.  Of course we proceed to look for best approximations.
Among Lowers, the closest image to T (w.r.t. <=) would be the sup, and
among Uppers it's the inf, corresponding to pointwise Kan ext. as limits.
So  T  gets caught in a squeeze play (like a real number), but still
might have lots of room to bounce around.

Back to the Bangor question (as least partly), we could ask what happened
if T got hit on the nose by A^F with some Z in A^D? ie. ZF->T is identity
n.t.  Surely Z is then the best approx. to T from above and below since
it is bang on.  But does Z have to be (iso to) a Kan ext. of T along F?
(which it needs to be if it is going to participate in any adjoint for
A^F).  Consider left extensions (inf of Uppers): from  ZF=T<=SF  we need
to produce a n.t. Z->S.  Again heuristically, the temptation is to cross
off F on the right in a kind of epi maneuver, which relates to Steve
Vickers' comment for rings.  By the way, the very nice perspective on
modules SJV mentioned also appears as Exercise 3(b) Chap VII p.415 in 
Mac Lane/Moerdijk '92 "Sheaves..".  But epi for F seems too strong to be
necessary, whereas the nice suggestion of Ross Street that each object of
D should be a retract of an object in the image of F with F factoring in
a certain friendly way looks really neat. Still, not clear it should be
necessary.
Anyway, might help to think about it in different ways.
Cheers ........................................Al Vilcius, Toronto
==============================================================================
Subj:	Re: Comparison between Functor Categories
Date: Tue, 29 Sep 92 10:38:15
From: sjv@doc.ic.ac.uk (Steve Vickers)

Some not very exciting developments:

If F: C -> D is a functor, then the question was about when F*: S^D -> S^C 
was full and faithful.

(Incidentally, it took a lot of headache before I convinced myself that 
"fully faithful" just meant "full and faithful". I couldn't find the phrase 
defined in any of the standard texts. Is its mellifluousness really enough 
to justify its use?)

My conjecture was that that this happens iff F is an epimorphism of 
categories.

This can't be correct. An epimorphism must be surjective on objects 
(otherwise you can map the objects not in the image to distinct isomorphic 
copies), but if F is any equivalence then F* is as well, and hence full and 
faithful.

(So my account of Mitchell's results for ringoids as opposed to rings was 
probably oversimplified.)

I assume that "epimorphism", with its demands of on-the-nose equality, is 
simply not a good notion in the 2-categorical context of categories.

In the monoid case, we do have an implication in at least one direction 
(adapted from the argument for rings):

Suppose C and D are monoids. If F* is full and faithful, then F is an 
epimorphism (of monoids).

Proof: Let G,H: D => E with F;G = F;H. E is a D-set, with action

  ed = e.H(d)

Consider the function G: D -> E. This is a homomorphism of C-sets, for

  G(dc) = G(d).G(F(c)) = G(d).H(F(c)) = G(d)F(c) = G(d)c

Hence by fullness of F* (note that faithfulness is automatic in this 
context), it is a homomorphism of D-sets, so for any d in D we have

  G(d) = G(1d) = G(1)d = 1.H(d) = H(d)

Remaining questions:

* Is the converse true in the monoid case?
* Is there a 2-categorical generalization of epi that (includes equivalences 
and) restores the original conjecture?

Steve Vickers.
==============================================================================
Subj:	Re: Comparison between Functor Categories
Date: Tue, 29 Sep 92 11:30:25 EDT
From: barr@triples.Math.McGill.CA (Michael Barr)

Just a quick comment on Steve Vickers' post.  This ought to be well
known, but either it isn't as well known as I thought, or people
aren't thinking of it in this connection.  If C --> D induces an
equivalence between idempotent completions (for example, if it is
inclusion of C into its idempotent completion), then the induced
Set^D --> Set^C is an equivalence.  In fact, the analagous statement
is true for any base that is itself idempotent complete.  Now of
course an inclusion of monoids that had that property would already
be an equivalence since the effect of idempotent completion is to
add more objects, but (effectively) no more arrows.  On the other
hand, for a monoid with many objects (aka a category), the situation
is quite different.  On the other hand, it might be useful to
confine the discussion to idempotent complete categories to avoid
this particular problem.

Michael
==============================================================================
Subj:	Re: Comparison between Functor Categories (2 postings)
Date: Wed, 30 Sep 92 12:00:29 +1000
From: street@macadam.mpce.mq.edu.au

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.]


+++++++++++++++++++++++++++++++++++++++++++++
From: Paul Taylor <pt@doc.ic.ac.uk>
Date: Wed, 30 Sep 1992 11:45:33 +0100

Be careful about epimorphisms of categories.

