1 Mar 1998 06:24

### Quantifiers for monoids

In studying Algol-like languages, I repeatedly run into operators that
have an interesting structure.  I am wondering if such operators are
studied somewhere.

Consider a monoid <M,*,1> in a CCC.  The operations of interest are
natural transformations E_A : [A => M] -> M that satisfy the following
equations (in the internal language of the CCC):

E_A(\lambda x. 1)  =  1
E_A(\lambda x. a * gx) = a * E_A(g)
E_A(\lambda x. gx * a) = E_A(g) * a
E_A(\lambda x. E_B(\lambda y. hxy)) =
E_B(\lambda y. E_A(\lambda x. hxy))

These operators "feel" like existential quantifiers.  In fact, if M is
a subobject classifier with the monoid structure ofh conjunction, then
the existential quantifier E satisfies all of these equations (though
it is not a natural transformation).

In the applications I am interested in, M is a type of commands, with
* as sequential composition and 1 as the null action.  An example of
E is a local variable declaration.

Is there some algebra or theory related to these kinds of operators?

Cheers,
Uday Reddy


2 Mar 1998 12:16

### Re: Quantifiers for monoids


[Note from moderator: apologies to Dusko for prepending nonsense to his
post, regards, Bob]

Uday S. Reddy:

> Consider a monoid <M,*,1> in a CCC.  The operations of interest are
> natural transformations E_A : [A => M] -> M that satisfy the following
> equations (in the internal language of the CCC):
>
>1)     E_A(\lambda x. 1)  =  1
>2)     E_A(\lambda x. a * gx) = a * E_A(g)
>3)     E_A(\lambda x. gx * a) = E_A(g) * a
>4)     E_A(\lambda x. E_B(\lambda y. hxy)) =
> 			E_B(\lambda y. E_A(\lambda x. hxy))

The naturality of E_A in A seems to be a very strong requirement
(provided that am not misuncerstanding anything, ofcourse).

Let T the terminal object (since 1 already denotes the unit of
M). Equations (1) and (2) imply

E_T(\lambda x. a) = a,

so E_T is iso. The naturality, on the other hand, implies that for
every a,b : T --> A holds

a=>M ; E_T   =   E_A   =   b=>M ; E_T

Such E_A, I think, shouldn't be thought of as a quantifier: modulo


3 Mar 1998 13:46

### Memorial article

The AMS Notices will publish a memorial article for Sammy. These
projects are put together in a hurry and who gets asked to submit
remarks is something of a random process. In this case it's Hyman
Bass, Henri Cartan, Alex Heller, Saunders Mac Lane and I. Hy will
also provide a narrative vita.

Please send me material you'd like included. If I get too many
suggestions, I will, with your permission, not include any of them in
the Notices but will publish -- after the Notices -- memorial pages in
the JPAA.


3 Mar 1998 13:32

### Reddy's question

Uday Reddy poses the following (with a few changes in notation]:

>Consider a monoid  <M,*,e>  in a CCC.  The operations of interest
>are natural transformations  E:[-,M] -> M  that satisfy the
>following equations (in the internal language of the CCC):
>
>               E_A(\x.e)  =  e
>         E_A(\x. a * gx)  =  a * E_A(g)
>         E_A(\x. gx * a)  =  E_A(g) * a
>    E_A(\x. E_B(\y.hxy))  =  E_B(\y. E_A(\x.hxy))

I wonder if naturality is really desired: it would seem to force  M  to
be trivial. By the familiar Yoneda-lemma argument, E  must be constant
as far as the "points" of  [A,M]  are concerned. (Actually one doesn't
need the argument, just the lemma itself; consider the transformation
that  E  induces between set-valued functors  (-,M) -> (1,M); Yoneda
says it must be constant.) The condition

E_A(\x.e)  =  e

forces just which constant it is. That is, for any  f:A -> M  it will
be the case that  E_A  will send  f  to  e.

But then either condition

E_A(\x. a * gx) = a * E_A(g)

or

E_A(\x. gx * a) = E_A(g) * a


4 Mar 1998 13:28

### Master Class in Logic - Reminder

MASTER CLASS IN MATHEMATICAL LOGIC - REMINDER

Dear colleagues,

This is to remind you of the Master Class in Logic
which will be held in Utrecht, the Netherlands, and
for which we posted an ad some time ago.

The deadline for applications of students who wish to participate but do not
need funding is June 1st; students who wish to
apply for a funding may still do so IF THEIR
APPLICATION REACHES US (that is: Marian Brands, at the
Department of Maths., Utrecht University) BEFORE THE
END OF NEXT WEEK.

We let the text of the original message follow:

In the academic year 1998-1999 the Universities
of Utrecht and Nijmegen organize, as part of
the MRI Master Class, a year-long education program
in Mathematical Logic. The program is aimed at
students who intend to enter a Ph.D.-program in the
subsequent year.

The courses are in English and foreign students are
specifically invited to apply. A limited number
of stipends are available.

The contents of the program are detailed
in a brochure which exists both as


4 Mar 1998 05:59

### Re: Reddy's question

Response by Peter Freyd to a question of mine:

> >Consider a monoid  <M,*,e>  in a CCC.  The operations of interest
> >are natural transformations  E:[-,M] -> M  that satisfy the
> >following equations (in the internal language of the CCC):
> >
> >               E_A(\x.e)  =  e
> >         E_A(\x. a * gx)  =  a * E_A(g)
> >         E_A(\x. gx * a)  =  E_A(g) * a
> >    E_A(\x. E_B(\y.hxy))  =  E_B(\y. E_A(\x.hxy))
>
> I wonder if naturality is really desired: it would seem to force  M  to
> be trivial.

Indeed!  (Peter Johnstone and Dusko Pavlovic also pointed out that I
went wrong in asking for naturality.)  Something got lost in
parameters in the interest of abstration seems to have produced a
statement that is quite impossible to satisfy.  My apologies.

Dusko Pavlovic pointed out some of what we could do once we discard
the naturality condition.  The second and third equations can be
regarded as naturality properties by thinking of M and [A,M] as
categories and E_A as a functor.  (That is good, because it singles
out the first equation as a "pretender."  So, I shouldn't be worried
when it breaks.)

On the other hand, I don't know what to make of the fourth equation.
It says that for E_A to be an abstraction operator (tentatively using


4 Mar 1998 17:43

### Uday's question

When reading the last message of Uday Reddy,
I got three ideas.

1) Several people have pointed out that naturality is impossible.
Yet a weaker form of naturality may be appropriate.
Consider existential quantification on sets.
If f: A -> B is a function and p: B -> M (= Bool) a predicate,
then  exists x in A: p(fx)  iff  exists x in f(A): p x
This suggests to require naturality  E_A (p o f) = E_B p
for *epis*  f: A -> B  only.

E_A(\x. E_B(\y.hxy))  =  E_B(\y. E_A(\x.hxy))
This equation looks a bit like the Foubini theorem
in integration theory.
The difference is that in Foubini's theorem,
there is a third mediating term, whose analogue would be
E_(A x B) (\(x,y). hxy) .
[Distinguish the product symbol x in A x B from the variable x.]

3) The analogy with integration also shows that
something may be missing from the present setting:
The integral depends on the function to be integrated
and also on a measure.  It is in fact an operator
I_A: [A->M] x M(A) -> M
where M are the (non-negative?) reals
with the multiplicative monoid structure,
and M(A) is the set of measures on A.
[Distinguish the operator M from the monoid M.
Yet there is some connection: M(1) = M


6 Mar 1998 06:02

### ANNOUNCING: Xy-pic version 3.6 released!

Dear Category Theorists,

Please find enclosed a copy of the TRAILER for a new version of Xy-pic!

Sincerely,
Kristoffer H. Rose

=======================================================================
ANNOUNCING the Xy-pic version 3.6 DIAGRAM TYPESETTING PACKAGE
=======================================================================

This is to announce a release of my diagram typesetting package Xy-pic.

Version 3.6 contains new and improved PostScript fonts donated by Y&Y
Inc. (as well as several minor bug fixes).

-----------------------------------------------------------------------
GENERAL
-----------------------------------------------------------------------

Xy-pic is a package for typesetting a variety of graphs and diagrams
with TeX.  Xy-pic works with most formats (including LaTeX, AMS-LaTeX,
AMS-TeX, and plain TeX), in particular Xy-pic is provided as a LaTeX2e
supported package' (following the CTAN LaTeX2e bundle' standard).

Further specifics of the package are in the distribution README file.

-----------------------------------------------------------------------
NEWS
-----------------------------------------------------------------------


6 Mar 1998 17:23

### Re: Memorial article

Hopefully one of the writers will include
Sammy's work
with John Moore cf. the EMSS

************************************************************
Until August 10, 1998, I am on leave from UNC
and am at the University of Pennsylvania

Jim Stasheff		jds <at> math.upenn.edu

146 Woodland Dr
Lansdale PA 19446       (215)822-6707

Jim Stasheff		jds <at> math.unc.edu
Math-UNC		(919)-962-9607
Chapel Hill NC		FAX:(919)-962-2568
27599-3250

On Tue, 3 Mar 1998, Peter Freyd wrote:

> The AMS Notices will publish a memorial article for Sammy. These
> projects are put together in a hurry and who gets asked to submit
> remarks is something of a random process. In this case it's Hyman
> Bass, Henri Cartan, Alex Heller, Saunders Mac Lane and I. Hy will
> also provide a narrative vita.
>
> Please send me material you'd like included. If I get too many
> suggestions, I will, with your permission, not include any of them in
> the Notices but will publish -- after the Notices -- memorial pages in
> the JPAA.


10 Mar 1998 19:08

### PSSL'66


If you intend to attend, please make the organisation of this meeting
easier by registering now. A detailed program will be circulated soon.

**** Final Announcement and Registration ****

The 66th Peripatetic Seminar on Sheaves and Logic
March 28-29, 1998

University of Birmingham
England

The 66th meeting of the PSSL will be held at the University of
Birmingham, England, over the weekend of 28-29 March 1998. Since its
inception, the focus of the PSSL has broadened and now includes talks
related to category theory, logic and theoretical computer
science. The meetings are informal in nature and talks on work in
progress is welcome.

We have arranged bed and breakfast in the University House which will
cost 23 pounds per night. In addition, a buffet lunch and tea/coffee
will be provided on Saturday and Sunday at a cost of 8 pounds per
day. Student participation is particularly encouraged at this meeting
and hence we have been granted a small fund to help with the costs of
attendence for students. Those interested in this offer should contact
the organisers as soon as possible. All payments should be by cash or
cheque (travellers cheques are acceptable). There are several ATM
machines on campus.

Participants may wish to plan their arrival so that they may attend