Subject: Re: Categories of relational structures
Date: 03 May 1993 14:01:26 -0400 (EDT)
From: Paul Glenn <GLENN@CUA.EDU>

>Define a relational structure (A,R) to consist of a set A and a
>n-ary relation on A for some ordinal n.  A homomorphism
>f:(A,R)->(B,S) is a function f:A->B between the underlying sets
>of two relational structures of the same arity, such that f(R) c
>S.  Write Str_n for the category of all n-ary relational
>structures and homomorphisms between them, and Str for the sum
>in CAT of Str_n over all ordinals n. 
>1.  What is the term for the notion of full subcategory of
>either Str_n or Str?  Failing that, what would be a suitable
>term?  Relational categories?  Categories of relational
>structures?
>
>Familiar examples of such categories and an upper bound on their
>arities include those of groups (3), rings (4), fields (4),
>lattices (3), vector spaces over the field K (1+max(|K|,2)),
>directed graphs (2), posets (2), and categories (3).
>
>I would expect complete lattices, complete Boolean algebras,
>topological spaces, and hypergraphs not to embed in Str_n for
>any n, because their structural elements (subsets, e.g. open
>sets) have no fixed cardinality bound, unlike n-tuples.  A
>pointer to a proof of such nonembedding, or a demonstration of
>how to embed them, would be greatly appreciated.  Since the
>concept is such a natural one, this question must surely have
>been looked at before.
>
>2.  What generalizations of Str or Str_n have been considered? 
>One can make Str a bit more "communicative" by permitting
>homomorphisms between dissimilar structures (A,R), (B,S) of
>respective arities m<n. Do this by padding out (A,R) to arity n
>by defining R$(n) to be the set of n-tuples of A whose first m
>elements satisfy R.  This probably looks about as useful today
>as the telephone did in 1879.


I can offer a few comments on arity concerning your category of
"relational structures" Str. 

First, with regard to the list of examples where you mentioned an
"an upper bound on their arities", I wondered if you meant (e.g.
for groups) the *least* n such that groups embed into Str_n? That
would be n=3 in the group case since each group's multiplication
table can be regarded as a 3-ary relation R where  (a,b,c) in R
iff ab=c. For *any* n>3 one can define (for any group) an n-ary
relation S where (a1,...,an) belongs to S iff a1 ... an = 1. The
mult table for the group determines S and is recoverable from S.
Thus a group embeds in Str_n for any n>3. However, n=3 is minimal
for groups.

Second, an n+1-ary relation R on S0 x ... x Sn spawns an infinite
family of relations of all arities. These are generated by two
operations: 
(1) Projection: the image of R in the composition R >--->
(product all j) Sj  ----> (product all j except i) Sj.
(Simplicially speaking, this is the "i'th face" of R, i=0,...,n).

(2)  Repetition of coordinates: 
R x Si >---> S0 x ... x Si x Si x ... x Sn. (Simplicially
speaking, this is the "i'th degenerate image" of R). There are
equations, the "simplicial identities", which equate the various
relations obtained this way.

While none of these relations derived from R contain "new"
information, they provide a useful alternative for defining
homomorphisms between relations of different arities. Here's what
I have in mind. Let R >--> A^m and S >--> B^n be relations , m
and n arbitrary. Then define a homomorphism from (R,A) ---> (S,B)
as the composite (R,A) --> (R',A) --> (S,B) where R' >---> A^n is
a "simplicial image" of R >--> A^m obtained by some sequence of
projection and repetition operations described above, and where
(R',A) ---> (S,B) is a homomorphism in Str_n. This strikes me as
being perhaps more "natural" (though more restrictive) than the
"padding out" process you mentioned in your post.

With this definition of homomorphism, an n-ary relation R >-->
A^m corresponds to a functor (delta/[m])^op --> Sets. (Delta =
cat of finite totally ordered sets and non-decreasing maps). The
category Str can be viewed, equivalently, as: (1) fibred over
delta (i.e. there's a discrete opfibration Str --> delta^op), or
(2) a coalgebra for a certain cotriple on Cat, the (ordinary)
category of small categories. (This must be qualified slightly
since Str isn't small). The details of these assertions are in a
paper I've written (I'd be glad to send a preprint). In that
paper, I viewed monics R >--> A^(m+1), (more generally, A >-->
A0 x ... x Am) as formulas in a first order theory.

+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Subject: Paper available
From: raymond@fwi.uva.nl (Raymond Hoofman )
Date: Tue, 4 May 1993 11:27:41 +0200 (MET DST)

The following paper is available by anonymous ftp: 

                Remarks on the Theory of Semi-Functors
                       R. Hoofman & I. Moerdijk

Abstract: "By establishing an appropriate equivalence, we show that the 
theory of semi-functors can be fully embedded in the theory of (ordinary)
functors. As a result, standard properties and constructions on functors 
extend automatically to semi-functors."

FTP instructions:

> ftp vera.fwi.uva.nl
> Name: anonymous
> Password: [your email address]
> cd pub/illc/raymond
> binary
> get rsf.dvi.Z                               (dvi-format)
> get rsf.ps.Z                                (ps-format)
> quit
> uncompress rsf.ps
> uncompress rsf.dvi


With kind regards,
Raymond Hoofman.
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Subject: Categories of relational structures
From: Jiri Rosicky <rosicky@queen.math.muni.cs>
Date: Thu, 6 May 1993 15:17:23 +0200 (MET DST)

There is a book devoted to these questions: A.Pultr and V.Trnkova,
Combinatorial, Algebraic and Topological Representations of Groups,
Semigroups and Categories, North Holland 1980.
The question whether complete lattices, etc. can be embedded into
Str_n depends on what one means under embedd. If it is a full embedding,
the problem is set-theoretical. 
                               
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Subject: Categories of relationl structures
Date: Thu, 6 May 93 12:10:59 EDT
From: es@math.mcgill.ca (Elaine Swan)

If I am not mistaken, every small category and every algebraic
category can be fully embedded into Str. This seems to follow from old results
of the Czech school of category theory, see e.g. J. Algebra 11(1969),
159-212 and references listed there. If my memory does not deceive me,
the same is true for every concrete category, provided one accepts
Vopenka's Principle.

From: Jim Lambek <lambek@triples.math.mcgill.ca>
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Subject: latest update to ctcs
Date: Fri, 7 May 93 08:35:31 EDT
From: barr@triples.Math.McGill.CA (Michael Barr)

A major update to ctcs is available for anonymous ftp from 
triples.math.mcgill.ca in /pub/barr under the name ctcsupdate.  Both
the tex (latex) and dvi files are available.  The tex file requires
diagram.tex and bezier.sty to run.  diagram.tex is in /pub/texmacros.

Michael Barr
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Subject: Terminal coalgebras
Date: Fri, 7 May 93 14:40:02 EDT
From: barr@triples.Math.McGill.CA (Michael Barr)

 
A new version of my paper, ``Terminal coalgebras in well-founded sets'',
now retitled, ``Terminal coalgebras for endofunctor on sets'' is now
availiable for anonymous ftp in triples.math.mcgill.ca in
/pub/barr/termobj.tex and /pub/barr/termobj.dvi. The version
reflects changes that I have made as a result of a several conversations
I had with Peter Aczel recently concerning the original version.  I
mistakenly attributed to him several statements that he apparently did
not make in his talk in September, 1989 at the Manchester meeting and
which did not appear in the published version of the talk.  I apologize
for this.  In any case, only about a quarter of this paper was on the
subject of that talk and that is the only part that has been changed
non-trivially.
 
Michael Barr
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Subject: paper available by ftp
Date: Sat, 8 May 93 12:45:36 +0200
From: moggi@diana.disi.unige.it (Eugenio Moggi)

----------------------------
The following paper is available via ftp from Imperial College.
The procedure follows the title and abstract

A Semantics for Evaluation Logic
Eugenio Moggi
DISI, Univ. of Genova
viale Benedetto XV 3, 16132 Genova, ITALY
moggi@disi.unige.it

Abstract

This paper proposes a topos-theoretic semantic for the
modalities and evaluation predicate of Pitts' Evaluation Logic, and
introduces several predicate calculi (ranging from Horn sequents to
Higher Order Logic), which are sound and complete w.r.t. natural classes
of models.  It is shown (by examples) that many computational monads
satisfy the additional properties required by the proposed semantics.
 
------------------

        ftp theory.doc.ic.ac.uk
        login: anonymous
        password: <your email address>
        cd /theory/papers/Moggi
        binary
        get ELT.dvi.Z
        -or-
        get ELT.ps.Z



+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Subject: Announcement of summer school
From: TEMPUS <tempus@queen.math.muni.cs>
Date: Thu, 6 May 1993 09:51:46 +0200 (MET DST)


    Tempus Summer School for Algebraic and Categorical Methods

                       in Computer Science



                       Second Announcement



                   Brno, June 28 - July 3, 1993



 Sponsored  by the European Community TEMPUS office the organizers

 are pleased to announce an intensive course designed to serve its

 students as a forum for exchange of ideas between the disciplines

 of mathematics and computer science.





 Courses:



 P. J. Freyd (Philadelphia), Cartesian Logic and Cartesian

                             Categories



 Y. Lafont (Paris), Linear Logic



 J. Lambek (Montreal), Categories and Deductive Systems





 C. P. Stirling (Edinburgh), Modal and Temporal Logics for
                             Processes



 G. Winskel (Aarhus), Models and Logic for Concurrent Computation







 Special lecture:



 D. S. Scott (Linz), The Theory of Domains: Origin, Development,

                     Future





 Lectures  will be  held  starting  Monday  morning, June  28, to
 Saturday noon, July 3; Wednesday afternoon is reserved for social

 activities. Each course will consist of five lectures,one lecture

 per day. There will be a reception for participants on the evening

 of Sunday, June 27th. An afternoon-excursion will be organized,

 followed by a conference dinner.



 Fees:



 Conference  fee is 220 DM, (tuition 100 DM, accomodation 120 DM).

 Price includes  accomodation  in double  bedrooms, breakfast  and

 lunch. The tuition fees can be supported by the organizers for a

 limited number of participants. Please apply!



 Registration:

 Please  send name,  address (including e-mail, if  available) and

 gender to the organizing office by May 20, 1993.Please indicate

 if you  plan to bring a guest or indicate the name of participant

 with whom you wish to share accommodation.







 Organizing Committee:



 Jiri Rosicky

 Anna Sekaninova

 Jan Slovak





                              Address:



                              TEMPUS SUMMER SCHOOL

                              Department of Algebra and Geometry

                              Masaryk University

                              Janackovo nam. 2a

                              662 95  BRNO

                              The Czech Republic



                              e-mail: tempus@queen.math.muni.cs

                              fax: 42-5-74 55 10

                              (later 42-5-41 21 03 37)

                              phone: 42-5-74 56 66



+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Subject: paper on FTP
Date: Mon, 10 May 93 00:39:40 EDT
From: pavlovic@triples.Math.McGill.CA (Dusko Pavlovic)

A paper on categorical proof theory

			MAPS II:
	CHASING PROOFS IN THE LAMBEK-LAWVERE LOGIC
	by Dusko Pavlovic

is available by anonymous FTP from triples.math.mcgill.ca.  The file
is called mapsII, and there are -A4 and -US formats, in .dvi and .ps
files. Please let me know if you have any problems with these files.

-- Regards, Dusko


			Abstract

In the Lambek-Lawvere logic, propositions and proofs are presented as
objects and arrows in a category. It is the categorical embodiment of
the strong constructivist paradigms of propositions-as-types and
proofs-as-constructions, which lie in the foundation of computational
logic. But a third paradigm arises here, not available elsewhere: the
idea of logical-operations-as-adjunctions. It opens a possibility of
genuinely categorical proof theory.

In the present paper, we study the Lambek-Lawvere version of regular
logic: the $\{\wedge,\exists\}$-fragment of the first order logic with
equality. The corresponding categorical structure is regular
fibration. The examples include stable factorisations, sites,
triposes. Regular logic is exactly what is needed to talk about maps,
as total and single-valued relations. However, when enriched with
proofs-as-arrows, this familiar concept must be supplied with an
additional conversion rule, connecting the proof of the totality with
the proof of the single-valuedness. We explain the logical meaning of
this and describe conditions under which every map in a regular
fibration corresponds to a unique arrow in the base category. When
this is the case, a natural fragment of generalized regular logic, in
the Lambek-Lawvere style, reduces to regular logic of sites.
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Subject: room mate for UACT meeting?
Date: Wed, 12 May 93 17:06:08 +0200
From: ABERNE@dhvrrzn1.uni-hannover.dbp.de

Is anybody interested in sharing a residence hall room at the UACT worshop
in Berkeley in July? Non-smokers preferred.

J"urgen Koslowski
c/o aberne@dhvrrzn1.uni-hannover.dbp.de
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Subject: Preliminary notice of workshop
From: H.GUSTAFSON@qut.edu.au
Date: Wed, 12 May 93 13:28:16 +1000
Sender: piggy@hilbert.maths.utas.edu.au

The following is a preliminary notice of the 1993 Workshop in Categories, 
Computing and Combinatorics, for your interest:

*************************************************************** 

		     3C WORKSHOP 93
	 CATEGORIES, COMPUTING AND COMBINATORICS
				   
		   September 1-3, 1993

       School of Computer Science and Engineering
	     University of New South Wales  

 * Preliminary announcement and call for participation *


This is the second in a series of _informal_ workshops 
exploring the connections between category theory, logic
theoretical computer science and algebraic combinatorics.
It will provide a forum at which experts and interested
workers from outside the field can exchange ideas.

The scope of the workshop has been significantly widened.
There will be talks in the following general areas:

1.  Categorical logic and categorical models of computation
    (e.g. imperative programming, distributed computing)

2.  The role of category theory in computer system design
    (e.g. object-oriented design, information systems and
    database theory, design process automation)

3.  Applications of category theory to combinatorics and
    combinatorial topology

4.  Algebraic combinatorics and coding theory 

Our emphasis will be on the connections between different
strands of research, and on new ways of thinking about
old problems.  We hope to promote cross-fertilisation
between areas.

There will be a series of tutorials on each of these
areas during the afternoon of Wednesday, September 1;
these will assume only a passing acquaintance with
category theory and/or combinatorics.  They are meant
to provide a suitable background for the more
specialised talks on Thursday and Friday.

We expect a number of international visitors to be
participating: these will include Takayuki Hibi
(Hokkaido; algebraic combinatorics) and Patrick Sol\'e
(Nice; coding theory).  Arrangements for other visitors
have not yet been finalised, but they _tentatively_
include Nicoletta Sabadini (Milan), Lin Ying Ming
(Szechuan), Eric Wagner (IBM Yorktown Heights) and 
Rod Burstall (Edinburgh).

Anyone is welcome to participate.  We intend the talks
to be accessible to people without an extensive background
in category theory and/or combinatorics; one of our major
goals is to make the most recent ideas and results in these
areas available to a wider community.  In particular we
would hope to have a number of industrial participants, as
we did last year.  Research students are also especially
welcome. 

The programme will be finalised in August.  Prospective
speakers should contact Amitavo Islam as soon as possible.
A limited amount of financial assistance is available to
assist speakers travelling from interstate.

Organisers:   Wesley Phoa (UNSW)           general organiser

	      Karl Wehrhahn (Sydney)       combinatorics
	      Dominic Verity (Macquarie)   category theory

	      Amitavo Islam (Sydney)       administration
	      Linda Milne (UNSW)           UNSW arrangements

This workshop is being run in conjunction with the Software
Engineering Research Group (UNSW), the Sydney Category Group,
the CATACOMB Group (Sydney) and the Theory Group (Macquarie).


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

	  3C WORKSHOP 1993 -- REGISTRATION FORM    


Name: _______________________________________________________

Physical address: ___________________________________________ 
      _______________________________________________________ 
      _______________________________________________________
      ______________________________ Phone: _________________

Email address: ______________________________________________


I plan to attend the Wednesday tutorials           [ ]

I would like a delicious and exciting lunch on

			   Thursday ($7)           [ ]
			     
			     Friday ($7)           [ ]

Please attempt to arrange accommodation for me     [ ] 

(Accommodation and lunch arrangements are very tentative at
the moment; please do not send any payment yet.  We only
need an indication of numbers at this stage.)


I would like to give a talk entitled

	______________________________________________________

(Please contact Amitavo Islam separately; you should be prepared
to provide copies of your slides, or a paper, for an informal
proceedings volume to be distributed to participants.)

(Speakers will get a free lunch.)


Send this registration form to

	wes@cs.unsw.oz.au

or

	Wesley Phoa
	School of Computer Science and Engineering
	University of NSW
	Kensington NSW 2033   

************************************************************************
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Subject: coequalisers again
From: Paul Taylor <pt@doc.ic.ac.uk>
Date: Mon, 17 May 1993 13:23:11 +0100

The more I think about coequalisers the less I understand them.

DOES ANYONE KNOW of a category in which REGULAR EPIS DO NOT COMPOSE?
(Maybe the opposite of the category of commutative rings?)

Here is a summary of the results of the previous discussion:

I asked what a REGULAR EPI is. I asked this because the observation that
all monos in a topos are regular is often made immediately after introducing
the subobject classifier, by considering the characteristic map and constantly
true.  This is not a co-equivalence relation, but regular epis are usually
defined in terms of equivalence relations. However if the kernel pair of a map
exists, it coequalises this if it coequalises anything, so the definitions
agree.  You can't do much logic in a category without pullbacks, but Mike Barr
and Peter Freyd gave me generalisations which are applicable without them.

Categories of algebras were the original examples of REGULAR CATEGORIES.
In these there is a factorisation of homomorphisms into regular epis
(which are charactersed as surjections) and monos.  This is stable under
pullback, as is the class of regular epis, and also the class of diagrams
which are kernels and coequalisers.

Does a regular category have all coequalisers?  The definition in the
literature is ambiguous, but I am inclined to agree with that in
"Categories, Allegories" by Peter Freyd and Andre Scedrov (North Holland 1992),
namely that they do not.

Although categories of algebras have all coequalisers, and regular epis are
stable, coequaliser diagrams need not be.  Here is a counterexample in the
category of groups given to me by Peter Freyd.

		    2	-------->   2
	2  >-----> 2		   2   ---->> 2  ---->> 1
	|   |	   |	-------->  |	|		|
	| --	   |	  |	   |  --		|
	|	   |	--	   |			|
	|	   |		   |			|
	|	   V		   |			|
	V	    2	-------->  V			V
	2  >-----> 2               A   -------------->> 3
			-------->   4

Here 2^2 is the four-element normal subgroup of the group of even permuations
on four symbols. The parallel pair consists of the inclusion and the map which
interchanges (12)(34) with (13)(24).  The equalisers and coequalisers are
illustrated and the squares are pullbacks in the obvious way.

There are several reasons why I am interested in all of this.

One of them is the interpretation of WHILE PROGRAMS using coequalisers of
functional relations, which must be stable under pullback. I would like to
be able to embed such a category in a topos. There is an obvious Grothendieck
topology, and the inclusion sends the coequalising maps to epis, but why
should it preserve the coequaliser DIAGRAMS?

(For a draft of a paper on while programs, see
/theory/papers/Taylor/while-1993.dvi at theory.doc.ic.ac.uk)

The other reason is an application to SYNTHETIC DOMAIN THEORY.
See my paper in LICS 1991 (also /theory/papers/Taylor/lics.dvi)
for the background. Eugenio Moggi asked for a good class of monos
(see /theory/papers/Moggi/ELT.dvi) and I was trying to show that
what I called "extremal" monos in my LiCS paper coincided with those which
arise as equalisers of parallel pairs into powers of Sigma.

Somewhat to my surprise, I discovered yesterday that in any category with
kernel pairs and coequalisers of them (NOT NECESSARILY STABLE),
	a map is mono iff it is orthogonal to all regular epis
where "orthogonal" means that the universal property for factorisation
systems is satisfied.  Moreover
	if regular epis compose, (reg.epi)-(mono) is a factorisation
Hence the question above.

Stability of regular epis is sufficient but not necessary to make them
compose.  For SDT I am specifically interested in "Sigma-epis" instead
of monos (maps which internally satisfy the cancellation property for
parallel pairs into the object Sigma, rather than all objects). For reasons
concerned with Eugenio Moggi's Evaluation Logic, we want Sigma-regular
monos to be "topological subspaces", ie that maps to Sigma extend along
the mono.  This is also sufficient to make regular monos compose.

Paul Taylor
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Subject: Workshop on Foundational Methods in Computer Science
Date: Tue, 18 May 93 07:59 PDT
From: hook@hood.cse.ogi.edu (Jim Hook)

**** FMCS UPDATE **** REGISTRATION DEADLINE ****

In my first announcement I neglected to specifiy that I need a firm
count on rooms and meals by Monday, May 24.  Please send email
registration forms by Sunday, April 23, to Kerri Crockett
(crockett@cse.ogi.edu).  

- Jim Hook
  FMCS93 

           **** Announcement and Registration ****

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

		1993 June 4--6

		Reed College, 
		Portland, Oregon

	Sponsored by the Computer Science and Engineering 
	Department at Oregon Graduate Institute of Science
	& Technology and the Department of Mathematics
	at Reed College.

This workshop is an informal, casual meeting to bring together
researchers in mathematics and computer science with a focus on the
application of category theory in computer science.  It is a three day
meeting.  On Friday, June 4, we will have tutorials on category
theory.  On Saturday and Sunday we will have research meetings.  The
workshop will end at noon on Sunday.  All sessions will be held on the
Reed campus which is quiet, beautifully landscaped, and adjacent to a
park and a public golf course.

The registration fee is $60 for regular registration and $45 for
students.  Registration includes breakfasts, refreshments, breaks and
a Chinese buffet.  Dormitory accommodation is available at $3.50 + $20
per night (three nights = $63.50).

Preliminary Schedule highlights:  (Assignment of talks to sessions may
change!) 

Thursday 6/3:
	1800 - 2100  Registration and reception

Friday 6/4:  Tutorials
	Sessions I and II:  Elementary category theory
		David Benson and Bob Walters
	Session III:  Binding Monads to Program Blocks
		Ernie Manes
	Session IV:  Sketches
		Charles Wells

Saturday 6/5:  Research sessions
	Session V:  Monads & Kleisli
		Phil Mulry
		Dick Kieburtz

	Session VI:  Charity
		Robin Cockett	What happened to charity?
		Tom Fukushima	More on monads
		Todd Simpson	Distributive logic

	Session VII:
		Vaughan Pratt	The Symmetry of Satisfaction in
				Much More Detail

	Session VIII:  Concurrency
		Dave Spooner	The Category of Protocols
		Bob Walters	Concurrency and Distributed Processing

Sunday 6/6
	Session IX:
		Charles Wells and Atish Bagchi
				Rules of Inference for Sketches

	Session X: Type theory and Recursion theory
		Several people have tentatively suggested 
		titles along this theme.  



The workshop is happening during the Portland Rose festival.
Highlights of the festival during the workshop include:

6/3 Coronation
6/4 Fireworks spectacular
6/4-6 Rose Festival Carnival on Waterfront
6/4-5 Golf Classic
6/5 Starlight Parade/Run
	A friend who did the run last year reports that it is quite a 
	sight with thousands of people running!


		** Registration **  DUE May 23!

Please send registration information via email to
	crockett@cse.ogi.edu.  
Advance payment is preferred.  Checks should be payable to Oregon
Graduate Institute and should reference FMCS93.  They should be mailed
to:
	FMCS93 (Kerri Crockett)
	Computer Science and Engineering
	Oregon Graduate Institute
	19600 NW von Neumann Dr.
	Beaverton, Oregon  97006



Name:
Affiliation:
Address:
email:
phone:
registration fee (regular = $60, student = $45): _______
Vegetarian banquet meal? (yes/no)

presentation? (yes/no)
title:
likely session:

Accommodation:
dorm rooms:  (list nights needed)
cost = $3.50 + ____ nights * $20 = $__.50

If you want to stay off campus please make those arrangements on your
own.  

Extra Banquet tickets ($25/person):

A few people suggested that it would have been fun to have a T-shirt
from last year's workshop.  Would you be interested in buying a T-shirt
on site when you arrive?  If so, what size?  (Don't send money for
T-shirts with your registrations!)

** Questions? **

If you have any questions or comments, please contact Jim Hook or
Kerri Crockett at OGI.

James Hook             
 hook@cse.ogi.edu       
 Phone: (503) 690-1169  
 Fax:   (503) 690-1553  

Kerri Crockett
 crockett@cse.ogi.edu
 Phone: (503) 690-1640

Department of Computer Science and Engineering
Oregon Graduate Institute of Science & Technology
19600 N.W. von Neumann Drive
Beaverton, OR 97006-1999
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Subject: re: coequalisers again

(note from moderator: 
several posts in reply to Paul's question follow, the delay in resending is due
to my absence and a local shutdown -  Bob)


From:	"G.M. Kelly" <gmkelly@cs.dal.ca>
Date:	Wed, 19 May 1993 20:14:51 -0300

Paul Taylor should look at my very old paper "Monomorphisms, epimorphisms,
and pull-backs", J.Austral.Math.Soc. 9 (1969), 124-142. There he will find
counter-examples as well as theorems. Max Kelly.

+++++++++++++++++++++++++++++++++++
Date: Wed, 19 May 93 19:15:23 EDT
From: barr@triples.Math.McGill.CA (Michael Barr)

Ragular epis that do not compose:  In Cat, which is complete and cocomplete
and is even tripleable over a category (graphs) tripleable over sets,
regular epis do not compose.  Let 2 be the category with two objects and one
non-identity arrow from one to the other.  Let N be the category with
one object and a natural numbers of maps.  Let N_2 be the category with one
object and 2 arrows, one an identity and the other idempotent.  The obvious 
map from N to N_2 is obviously a regular epi and so is the map from 2 to
N that identifies the objects, but the composite is not.

Michael

++++++++++++++++++
From: pavlovic@triples.Math.McGill.CA (Dusko Pavlovic)


 > DOES ANYONE KNOW of a category in which REGULAR EPIS DO NOT COMPOSE?
 > (Maybe the opposite of the category of commutative rings?)

I don't suppose that this is what you mean, but isn't already
something like

	--0--> --a--> --f-->
	--1--> --b-->		a0=a1, fa=fb	

providing an answer to the question as it stands? - Dusko


++++++++++++++++++++++++++++++++++++++++++++++++
Date: Thu, 20 May 93 10:28:54 -0700
From: Art Stone <stone@math.ubc.ca>
Subject:  an answer to Paul Taylor's question


Paul Taylor asks for a category in which REGULAR EPIS DO NOT COMPOSE.  

The short answer is  |Cat .  (Where |x denotes boldface-x, look at the canonical 
presentation, which has length two, of |3  in terms of free categories over 
sets, i.e., coproducts of copies of |2.  The intervening algebras in this 
presentation are free categories over graphs.)

In slightly greater generality, how do we produce examples of categories in 
which there are chains of length  n  of regular epis -- whose composites cannot 
be written as composites of fewer than  n  regular epis (for each n > 1) ?  

When I worried about this several decades ago, Peter Freyd gave an answer, in 
his essentially equationally defined categories [e.g.,  in the early pages of 
his Aspects of Topoi] -- defined by equations on a set of partial as well as 
entire operations -- in which the operations can be ordered so that for each 
partial operation its domain is defined by equations in earlier operations.   
|Cat  is an example when  n = 2.   This leads into the subject of adjoint towers 
[Applegate-Tierney, LNM 137; Adamek-Herrlich-Rosicky c.1987]  To get a tower of 
height  n  over  |Sets^m  (for any  m )  there must be  n  batches of 
progressively "higher" operations, each requiring the last of the preceding 
batches, in the definitions of its domains.

For the |Cat example, the intervening category is directed |Graphs.  The base 
category is respectively  |Sets or |Sets^2 , when we use the usual one-sorted or 
two-sorted definition of "category".  And if we define "category" in terms of 
(commuting) "triangle", in place of "morphism",  then the tower degenerates -- 
after the pattern of the main theorem of Gabriel-Ulmer [LNM 195 and LNM 221].

Now, if |Cat is interesting in this way, what does it mean that 

	|Cat is a topos wrt categories enriched over it

[as remarked by Ross Street several months ago here on the catnet], and what 
modifications are we going to be compelled to make when we attempt to carry 
topos-style thinking from |Sets over to |Cat?

Talk about WHILE programs suggests talk about imperative languages.  Perhaps 
more important, even, than their dealing with STATE is the way imperative 
languages can be explicit about extending or shrinking storage (using pointers).  
Manes and Moggi have shown us how monads can be used to model STATE and given us 
a category theoretic translation of the distinction between call-by-value and 
call-by-name [begin with Moggi's paper on theory.doc.ic.ac.uk].  Is there also
a 2-category theoretic translation of the distinction between call-by-value and call-by-reference, that depends on the difference between the two kinds of
composition we have in 2-categories?  Here I doubt if the base 2-category can
be |Cat.  But |Cat (x) |Cat remains a possibility, where (x) denotes Gray's
assymetric tensor product [LNM 391 and in the Heller-Tierney (ed.)
Eilenberg festschrift].


  Art Stone

+++++++++++++++++++++++++++++++++++++++++++
Date:         Thu, 20 May 93 14:17:35 EDT
From:         Walter Tholen <THOLEN@VM1.YorkU.CA>
Subject:      Coequalizers                 

Regarding Paul Taylor's question, here are some useful references that
contain answers:
G.M. Kelly, Monomorphisms, epimorphisms, and pullbacks, J. Austral. Math
Soc. 9 (1969) 124-142. (Mentions an example of a complete,cocomplete,
wellpowered, cowellpowered additive category due to Isbell in which
reg. epis do  not compose. The following articles deal with long chains
of regular epis; this is a selection only:)
J. MacDonald and A. Stone,The tower and regular decomposition , Cahiers
TGDC 23 (1983) 197-213
R. Bo"rger and W. Tholen,Total categories and solid functors, Can. J.
Math 42(1990) 213-229 (see sections 4 and5)
J. Adamek and W. Tholen, Total categories with generators, J. of Alg.
133 (1990) 63-78 (see section 1)
R. Bo"rger, Making factorizations compositive, Comm. Math. Univ. Carolin.
(1991) 749-759 (see section 3).
The last article mentions one remaining problem on the composition-
cancellation behaviour of regular epis in a category (with kernel pairs
and their coequalizers, say): consider the properties (A) and (B):
  (A) if e is split epi and d is regular epi, then the composite ed of
      first d and then e is regular epi,
  (B) if a composite ed is regular epi, then e is regular epi
one always has that if (A) holds in our category, then also (B) holds.
But what about the converse? (Note that neither property holds true in
general, already Kelly's paper contains a counter-example.)
Regards,
Walter Tholen
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Subject: re: coequalisers again
From: Paul Taylor <pt@doc.ic.ac.uk>
Date: Sat, 22 May 1993 14:59:33 +0100

Thanks to Art Stone in particular and also Mike Barr, Max Kelly,
Dusko Pavolovic and Walter Tholen for their helpful comments, which
I still have to study.

I wonder whether any specialists in group theory or commutative algebra
might be able to find a single example of non-composing regular monos
in the category of groups or of commutative rings. Something like:
(1) a normal subgroup of a centraliser in a simple group, or
(2) A chain of subrings R<S<T such that
      s # 1 = 1 # s   in the tensor  S *_R S   implies s in R
      t # 1 = 1 # t   in the tensor  T *_S T   implies t in S
 but  s # 1 = 1 # s in T *_R T does not imply s # 1 = 1 # s in T *_S T

This would avoid "theological" objections to discussing on-the-nose colimits
in the 1-category of categories.

Paul Taylor
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Subject: re: coequalisers again
Date: 25-MAY-1993 18:55:55.59
From: "Fred E.J. Linton" <FLINTON@EAGLE.WESLEYAN.EDU>

Paul Taylor (pt@doc.ic.ac.uk) asks:

> I wonder whether any specialists in group theory or commutative algebra
> might be able to find a single example of non-composing regular monos
> in the category of groups or of commutative rings.

Alas, every inclusion of a subgroup (monomorphism of groups) is an
equalizer "for free" (a regular monomorphism), so there's no example
of the desired sort in  {Groups} .  (The argument I know is one I learned
from Eilenberg several decades ago; it uses a suitable permutation group
as the target of two homomorphisms (from the larger group) whose equalizer
is precisely the given subgroup.

Cheers.				-- Fred
   
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Subject: re: coequalisers again
From:	Reinhard Boerger <rboerger@mathstat.yorku.ca>
Date:	Tue, 25 May 1993 16:44:43 -0400

It has been known for a long time that all monomorphisms in the category
of groups are regular, therefore the regular monos compose. I do not
know who proved it first. It can be shown directly by representing any
inclusion map, say from H to G, as an equaliser of two arrows from G
to the group of all bijections from the set of all left cosets modulo H 
to itself. Another way is to look at the usual descriptions of amalgamated
products (i.e. poushouts of pairs of monos); then every mono m can be seen
to be the equaliser ofthe two maps forming the pushout of m with itself.

In the category of rings (commutative or not, unital or not), regular monos
do not compose. The problem is stdied in detail in John Isbell's paper
"Epimorphisms and dominions", La Jolla Proceedings, 1965. Similar arguments
work for monoids or semigroups. A nice and easy, but seemingly not very
well-known example is given by Gabriel and Ulmer (LNM 221): let N be
the additive monoid of non-negative integers, let A be the submonoid 
generated by 3 and 5 and B the submonoid generated by 3, 5, and 7. Then
the inclusions from A to B and from B to N can easily be see to be
regular monos, but their composite is not, due to the following nice 
computation: assume f(3)=g(3) and f(5)=g(5) for some morphism from N
to some monoid (multiplicatively written). Then f(7)=f(2)f(5)=f(2)g(5)=
f(2)g(3)g(2)=f(2)f(3)g(2)=f(5)g(2)=g(5)g(2)=g(7). 

Gabriel and Ulmer also prove the (now?) well known fact that in any 
category with finite limits regular epis compose, if they are stable 
under pullback, and they even state their result more generally. Only
recently, I realized that their result easily implies that the class
of regular epimorphisms stable under pullback (i. e. of all morphisms e
such that every pullback of e is a regular epi) is aways closed under
compostion, even if regular epis do not compose.

                                           Greetings

                                       Reinhard Boerger
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Subject: coequalisers & visit
From: Paul Taylor <pt@doc.ic.ac.uk>
Date: Wed, 26 May 1993 17:14:12 +010

Thanks for sending me exactly the kind of counterexample I need for my
foundations book. It will do very nicely as an exercise in the section
on factorisation systems.  I shall have to think a bit more about the
one involving presentations of categories which Art Stone and others
mentioned.

I am coming to Canada for LiCS in Montreal next month. My flight plan
is to arrive in Toronto on Saturday 12 June and return from Montreal
(via (!!) Toronto) after LiCS.  I wonder whether the people at York
would like to hear a seminar from me in return for some local accommodation
for a few days?

Several subjects are on offer: stable domain/category theory (see the papers
in my ftp archive, which I think soem of you already have), intuitionistic
ordinals, synthetic domain theory, as you please.

Paul Taylor
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Subject: linear topology, hopf algebras and *-autonomous categories
Date: Fri, 28 May 93 14:57:23 EDT
From: blute@triples.Math.McGill.CA (Richard Blute)



The following paper is available by anonymous ftp from the site
triples.math.mcgill.ca. It is in the file pub/blute in dvi and ps
format(compressed). Anyone who would like the paper and cannot access
it this way can of course contact me.

Regards,
Rick Blute


       LINEAR TOPOLOGY, HOPF ALGEBRAS AND *-AUTONOMOUS CATEGORIES

                          Richard F. Blute
                          McGill University 


                              Abstract


The goal of this paper is to construct models of variants of linear
logic in categories of vector spaces. We begin by recalling work of
Barr, in which vector spaces are augmented with linear topologies to 
obtain new examples of symmetric monoidal closed (autonomous)
categories. The advantage of these categories is that they have large 
subcategories of reflexive objects which are also autonomous,  
in fact *-autonomous. Thus, we obtain models of (a fragment of) 
classical linear logic. These models have an advantage over other
models arising from linear algebra in that they do not identify the two
multiplicative connectives, tensor and par. Furthermore, the models
will be complete and cocomplete.

We then extend Barr's work to vector spaces with additional structure,
in particular to representations of Hopf algebras. As special cases,
we examine cocommutative Hopf algebras, and quasitriangular Hopf
algebras, also known as quantum groups. In the quasitriangular case, the
representations actually form a braided *-autonomous category, first
defined by the author. They thus give a model of a braided variant of
linear logic, also defined by the author. This is the first
example of such a model which does not identify the two multiplicative
connectives.

Hopf algebras, and more generally bialgebras, have been of interest
recently as a possible framework for the study of concurrency, in that
they encode the paradigm of interleaving processes, also known as fair
merge, as well as other structural operations on concurrent
processes. This was first observed by D. Benson. As a result of the
work in this paper, such bialgebras will yield models of a fragment of
linear logic.

While these models do not equate the multiplicative connectives they
do validate the MIX rule, thus giving models of a slightly larger
theory, first studied by Fleury and Retore. Also, if additional 
restrictions are placed on the Hopf algebra, we obtain
models of cyclic linear logic, defined by Yetter.



+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Subject: Zariski Categories
Date: Sat, 29 May 93 13:23:26 -0400
From: "Allan Adler" <ara@martigny.ai.mit.edu>

I'm looking at the book Categories of Commutative Algebras, by
Yves Diers. Before plunging into the details, I'm wondering about
a couple of things:

(1) Does Grothendieck's theorem about faithfully flat descent work in
    the setting he develops?

(2) What he calls algebraic spaces seem more like "bunches of varieties".
    The terminology "algebraic spaces" as used by Artin means something
    else. So does the notion of algebraic space in the sense of Artin
    have a place in this generalization? 

Allan Adler
ara@altdorf.ai.mit.edu
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Subject: Re: coequalisers & visit
From: Paul Taylor <pt@doc.ic.ac.uk>
Date: Thu, 27 May 1993 15:32:11 +0100

Apologies for broadcasting a message which was intended to be a personal
reply!                  Paul Taylor


+++++++++++++++++++++
note from moderator:

and my apology to Paul that the usual intercept failed; my instructions to 
the person temporarily minding the list were incomplete.

Bob
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Subject: 2-category algebras?
Date: Sat, 29 May 93 23:09:51 PDT
From: baez@ucrmath.ucr.edu (john baez)

We all know about group algebras, and this leads naturally to the
idea of a category algebra: form a vector space having as a basis the
morphisms in a given category, with the obvious product (taking the
product of two morphisms to be zero if the head of one isn't the tail of
the other).  I used an example of this in my paper "Quantum Gravity and
the Algebra of Tangles," but I have never seen a reference to the general
concept, and I would appreciate one.

What I am now interested in, however, is generalizing this notion to
2-category algebras.  This might be related to recent algebraic work
of Ruth Lawrence, which I haven't actually seen.  Any leads?

Regards,
John Baez

