Michael Barr | 1 Apr 21:44 2000

Curious fact

Has anyone seen this before, or can anyone give a principled
explanation.  Begin with the following observation. Suppose
       del            del
  ... -----> (C_n,d) -----> (C_{n-1},d) ---> ... ---> (C_0,d) --> 0
 is a chain complex of differential abelian groups, except that we
assume d.del = -del.d.  Suppose (C_n,d) is exact for each n. Let C be
the direct sum of the C_n with boundary given by the matrix
          (   d     0     0   ...    )
          (  del    d     0   ...    )
          (   0    del    d   ...    )
          (   .     .     .   .      )
          (   .     .     .    .     )
          (   .     .     .     .    )
 The finite truncations F^n = C_0 +...+ C_n are readily
shown to be exact:  F^0 = C_0 is by hypothesis and there is an exact
sequence     0 --> F^{n-1} --> F^n --> C_n --> 0.  AB5 now shows that
the direct limit, which is C, is exact.

Of course, this is going to be false for a category, such as compact
abelian groups, that is not AB5.  Except it is true.  Using duality, we
can translate it to the following statement for abelian groups.  Suppose
       del            del
  ... <----- (C_n,d) <----- (C_{n-1},d) <--- ... <--- (C_0,d) <-- 0
 is a cochain complex of differential abelian groups, except that we
assume d.del = -del.d.  Suppose (C_n,d) is exact for each n. Let C be
the direct product of the C_n with boundary given by the matrix
          (   d    del    0   ...    )
          (   0     d    del  ...    )
          (   0     0     d   ...    )
          (   .     .     .   .      )
(Continue reading)

Michael Barr | 4 Apr 00:12 2000


A day after I sent my previous note, I realized the (or an) answer.  In
fact, I seem to have discovered a new infinite exactness condition that
is between AB4 and AB5 and, inevitably, I call AB4.5.  So far I know
only that it is implied by AB5, implies AB4 and, since module categories
satisfy both AB5 and AB4.5*, it is definitely weaker than AB5.  I do
not, at this time, know that it is stronger than AB4.

Here is how it works.  Call a poset superdirected if it is directed and
all down segments are finite.  The natural numbers is one example and
the set of finite subsets of any set is another.  If I is superdirected,
A an abelian category and F,G:  I --> A are two diagrams, say that a
natural transformation alpha:  F --> G is supernatural (OK, suggestions
for better names welcome) if for any i in I, the following:  Look at the
diagram consisting of all the Fj for j =< i and all the Gj for j < i.
The arrows in the diagram are all the alpha j, for j =< i, as well as
all the arrows from the restrictions of F and G. The diagram has a
cocone to Gi and that cocone is monic (meaning the natural map from the
colimit to Gi is monic) for each i in I, call alpha supernatural.  Now
the condition is that whenever alpha is supernatural, the induced colim
F --> colim G is monic.

To see that this implies AB4, suppose for all x in X, A_x >--> B_x.  Let
I consist of all the finite subsets of X.  For i in I, let Fi be the
direct sum of all the A_x, x in i and Gi be the direct sum of the
correspnding B_x.  The supernaturality is satisfied and hence the sum of
the A_x maps monically to the sum of the B_x.

The application to my question comes as follows.  To recall, I am
supposing that
       del            del
(Continue reading)

Michael Barr | 4 Apr 17:08 2000

just to be sure (fwd)

Of course, Peter is correct below, since Gi is not part of the diagram
(although Fi is).

One more thing.  The reason that B^n --> B^{n+1} is monic (which is
crucial) is that they are subgroups of F^n and F^{n+1} resp.

One thing I found curious is that in any commutative diagram with exact

         0 ----> A -----> B -----> C -----> 0
                 |        |        |
                 |        |        |
                 |        |        |
                 v        v        v
         0 ----> A' ----> B' ----> C' ----> 0

if C ---> C ' is monic, then so is A' +_A B ---> B'.  Well it turns out
that there is an exact sequence

    0 ---> ker (C --> C') ---> A' +_A B ---> B' 

I don't see this as coming from the snake lemma, but who knows.

---------- Forwarded message ----------
Date: Tue, 4 Apr 2000 09:33:34 -0400 (EDT)
From: Peter Freyd <pjf <at> saul.cis.upenn.edu>
To: barr <at> barrs.org
Subject: just to be sure

 The first inequality below should be  j < i?
(Continue reading)

Robert A.G. Seely | 5 Apr 03:18 2000

Categories with finite products and coproducts

We wish to announce the following paper, which has been placed on the
triples web and ftp site (urls given below).

                       Finite sum - product logic

            J.R.B. Cockett                   R.A.G. Seely
         University of Calgary     and     McGill University
         robin <at> cpcs.ucalgary.ca           rags <at> math.mcgill.ca

Brief Abstract:
In this paper we describe a deductive system for categories with finite
products and coproducts, prove decidability of equality of morphisms
via cut elimination, and prove a "Whitman theorem" for the free such
categories over arbitrary base categories.  This result provides a nice
illustration of some basic techniques in categorical proof theory, and
also seems to have slipped past unproved in previous work in this field.

Since this material might seem rather close to the sort of categorical
proof theory done in the past 2-3 decades, we feel we ought to point
out some features which distinguish it from what others have done.
Some comments concerning its novelty might help the reader attune
himself to some points that otherwise might slip past unnoticed.

We present a correspondence between the doctrine of categories with
finite sums and products (without any assumption of distributivity),
and a "Lambek style" deductive system. But note that unlike the work
of Joyal's on the bicompletion of categories, our construction of the
free category does not use an inductive chain of constructions,
alternating between completions and cocompletions.  In this finite
(Continue reading)

Riccardo Focardi | 5 Apr 12:39 2000

WITS'00 -- last call for paper

Apologies for multiple copies.

                       Last Call for Papers

                            Workshop on
               Issues in the Theory of Security (WITS '00)

                 University of Geneva, Switzerland
                           7,8 July 2000


                     Co-located with ICALP '00,
                 the 27th International Colloquium
              on Automata, Languages, and Programming
                        (9 to 15 July 2000)


   Submission of papers:          *** 15  April 2000 ***
   Notification of acceptance:        31  May   2000
   Workshop:                          7,8 July  2000

   The IFIP WG 1.7 on "Theoretical Foundations of Security Analysis and
(Continue reading)

Robert A.G. Seely | 7 Apr 00:04 2000

Correction to paper announcement (ftp URL)

Earlier I posted an announcement of a paper

                        Finite sum - product logic


            J.R.B. Cockett                   R.A.G. Seely
         University of Calgary    and      McGill University
         robin <at> cpcs.ucalgary.ca           rags <at> math.mcgill.ca

But there was a slight error in the ftp URL given (the http url was
correct however).  The paper may be found at:

 rags web page:  http://www.math.mcgill.ca/rags/

 or McGill Maths ftp site:  


R.A.G. Seely
<rags <at> math.mcgill.ca>

Claude Auderset | 9 Apr 14:41 2000

CATOP 2000

Conference C A T O P 2 0 0 0 (Third and last announcement)

to be held at the University of Fribourg (Switzerland), 4-6 July, 2000.

TOPIC: It is the aim of this conference to discuss categorical topological
methods that are likely to be mathematically important in the next century.

Furthermore, on Thursday afternoon resp. evening, we shall celebrate the
seventieth birthday of Professor Heinrich Kleisli (Fribourg). Those 
interested in attending only the birthday
celebration or the following banquet should not forget
to register, too; see below. Of course, they need not
pay the registration fee.

Titles of the eight invited two hour lectures:
A. ARHANGEL'SKII (Moscow, Russia): Topological and paratopological
groups and homogeneous spaces.
M. BARR (Montreal, Canada):  The *-autonomous category of Mackey spaces.
MARIA M. CLEMENTINO (Coimbra, Portugal): Closure operators.
KATHRYN P. HESS (Lausanne, Switzerland): Model categories in algebraic
R. LOWEN (Antwerp, Belgium): Approach spaces.
HILARY A. PRIESTLEY (Oxford, England): Duality theory.
D. PUMPLUEN (Hagen, Germany): Convex sets and Saks spaces
(A paradigmatic case of applied category theory).
S. WATSON (York, Canada): How to construct counterexamples in general and
set-theoretic topology usefully with pullbacks.

SHORT COMMUNICATIONS: Persons interested in giving a short communication are kindly asked to send a one
(Continue reading)

Michael Barr | 11 Apr 17:56 2000


The file ab45.zip, that includes both the dvi and ps version, is now
available at ftp.math.mcgill.ca/pub/barr.  It is a preliminary version
because I want to investigate if the condition is really stronger than
AB4.  The following consideration raises the possibility that it might not
be.  One place to look to distinguish AB4* from AB4.5* might be in the
abelian groups of a topos.  But in order for the abelian groups of a topos
to satisfy AB4*, you need AC (in the topos).  But AC implies dependent
choice and then it looks like you have AB4.5*, which really is just like
dependent choice.


Valeria Correa Vaz de Paiva | 14 Apr 19:01 2000

LICS Workshop on Chu Spaces and Applications 25th June 2000,

                    Final CALL FOR PAPERS

                    LICS'2000 Workshop on

               Chu Spaces: Theory and Applications

          Sunday, June 25, 2000, Santa Barbara, California


          ****Submission deadline: April,25, 2000****

A Chu space is a related pair of complementary objects.
Besides having intrinsic interest in their own right, Chu spaces
have found applications to concurrent processes, information flow,
linear logic, proof theory, and universal categories.  The workshop is
concerned with the theory and applications of Chu spaces, as well as
related structures such as the Dialectica construction and double glueing.

The workshop will bring together computer scientists, mathematicians,
logicians, philosophers, and other interested parties to discuss the
development of the subject with regard to its foundations, applications,
prospects, and directions for future work.  Work in the subject is
currently fragmented across several areas: category theory, traditional
model theory, concurrency, and the semantics of programming languages,
and such a workshop can contribute to the coordination and possibly even
some unification of these efforts.

Suggested topics for presentation and discussion include but are by no
(Continue reading)

jvoosten | 14 Apr 16:38 2000

preprints available

The following preprints are available from the WWW:

Jaap van Oosten
Realizability: A Historical Essay

Abstract: historical survey on Realizability. Focuses on
notions of realizability used in the study of metamathematics of
arithmetical theories, and topos-theoretic developments.
Bibliography contains 96 items.24 pages

Lars Birkedal and Jaap van Oosten
Relative and Modified Relative Realizability

Abstract: We approach `relative realizability' from an abstract point
of view, studying internal partial combinatory algebras in an
arbitrary topos E. Let RT(E,A) denote the standard realizability
topos over E w.r.t. A.
We define the notion of `elementary subobject'
in a topos; if, for two internal pca's A and B in E, there is
an embedding which maps A as elementary subobject into B, there
is a local geometric morphism from RT(E,B) to RT(E,A).
Next we study the situation where an internal topology j is given;
we have a tripos over E using only the j-closed subobjects of A,
giving a topos RTj(E,A). RTj(E,A) is a subtopos of RT(E,A) and we
have a pullback diagram of toposes:

    |           |
(Continue reading)