Richard Blute | 1 Aug 15:18 2006

Octoberfest-Preliminary Announcement

             Preliminary Announcement-Octoberfest 2006

The Category Theory Octoberfest has been a great tradition among category
theorists for several decades now. For the second consecutive year, it
will be held at the University of Ottawa. It will be hosted by the Logic
and Foundations of Computing group (LFC). See our website at The conference will be held on the weekend
of October 21st and 22nd. A webpage for the conference will be available

We will be asking for submissions for talks in early September.
But we wanted to give people information on lodging now, as
Ottawa can be busy that time of year. We have booked a block of rooms

Quality Hotel Downtown Ottawa
290 Rideau Street
Ottawa, ON K1N 5Y3
(P) 613-789-7511

These rooms are held for Friday and Saturday nights. The
group number is 105626 and the group name is "Ottawa U-Math Dept".

The rate is $99.00 plus tax. Guests may
phone the hotel directly at 613-789-7511 to reserve and may
quote either the group name or number to get the preferred
rate. The cutoff for this special rate is September 20th,
but we strongly advise you not to wait that long.

(Continue reading)

J=FCrgen Koslowski | 2 Aug 14:32 2006

PSSL84, first announcement


        84th meeting - first announcement

Dear Colleagues,

The 84th meeting of the seminar will be held at the Department of
Theoretical Computer Science of the Technical University Braunschweig,
Germany, over the weekend of October 14-15, 2006.  As always, he
seminar welcomes talks using or addressing category theory or logic,
either explicitly or implicitly, in the study of any aspect of
mathematics or science.

Following the positive experience at PSSL83 in Glasgow earlier this
year, Samson Abramsky and Bob Coecke have agreed to jointly give a
three talk overview of recent developments in the categorical approach
to quantum informatics.  We hope that professor Reinhard Werner,
mathematical physicist at the TU Braunschweig with special interest in
quantum informatics, can be present as well.

Braunschweig is located about 60 km East of Hannover and about 200 km
West of Berlin.  It can easily be reached by car or train.  The
closest airport is in Hannover; the airport bus to the Hannover train
station takes about 20 minutes, and the train from there to
Braunschweig takes about 40 minutes or less.

Further information on the location of the seminar, along with details
on local travel and accommodation together with an online registration
form can be found at

(Continue reading)

Tom Leinster | 7 Aug 15:36 2006


Dear category theorists,

Here's something that I don't understand.  People sometimes talk about
algebraic structures "satisfying laws".  E.g. let's take groups.  Being
abelian is a law; it says that the equation xy = yx holds.  A group G
"satisfies no laws" if

    whenever X is a set and w, w' are distinct elements of the free
    group F(X) on X, there exists a homomorphism f: F(X) ---> G
    such that f(w) and f(w') are distinct.

For example, an abelian group cannot satisfy no laws, since you could take
X = {x, y}, w = xy, and w' = yx.  There are various interesting examples
of groups that satisfy no laws.

To be rather concrete about it, you could define a "law satisfied by G" to
be a triple (X, w, w') consisting of a set X and elements w, w' of F(X),
such that every homomorphism F(X) ---> G sends w and w' to the same thing.
 A law is "trivial" if w = w'.  Then "satisfies no laws" means "satisfies
only trivial laws".

You could then say: given a group G, consider the groups that satisfy all
the laws satisfied by G.  (E.g. if G is abelian then all such groups will
be abelian.)  This is going to be a new algebraic theory.

What bothers me is that I feel there must be some categorical story I'm
missing here.  Everything above is very concrete; for instance, it's
heavily set-based.  What's known about all this?  In particular, what's
known about the process described in the previous paragraph, whereby any
theory T and  T-algebra G give rise to a new theory?
(Continue reading)

IFIP WG2.2 2006 | 7 Aug 15:20 2006

IFIP WG2.2 anniversary meeting: Last Call for Participation

Note: the meeting is rather exceptional, both for the
quality of the speakers and the form of the talks
(mostly reflections on history and development of concepts)


           IFIP WG 2.2 Anniversary Meeting
                11-13 September 2006
                   Udine, Italy



          Registration page:
          Registration deadline: 31 August 2006.

The meeting fee is 150 Euros. The workshop fee includes lunches,
coffee-breaks, the social dinner and the excursion on Sunday afternoon.

About the WG 2.2

The IFIP Working Group 2.2 was established in 1965 as one of the
first IFIP Working Groups. The primary aim of the WG is to explain
(Continue reading)

George Janelidze | 8 Aug 13:28 2006

Re: Laws

Dear Tom,

"Any theory"?...

If it is about Lawvere theories, we go back to classical universal algebra:

Let V be a variety of universal algebras, X be a fixed infinite set and F(X)
the free algebra on X. A pair (w,w') holds in an algebra A in V if, for
every map f : X ---> A, the induced homomorphism f* : F(X) ---> A makes
f*(w) = f*(w'); and in this case we write A |= (w,w'). Thus |= becomes a
relation between V and F(X)xF(X) (where x is used as the cartesian product
symbol). As every relation does, |= determines a Galois connection between
the subsets in V and the subsets in F(X)xF(X). Galois closed subsets in V
are exactly subvarieties (by definition), and Galois closed subsets in
F(X)xF(X) are called algebraic theories.

Now, as every universal-algebraist knows, every algebra A in V has its
theory T(A) - the one corresponding to the subvariety <A> in V generated by
A. By a classical theorem, due to Garrett Birkhoff, <A> is the smallest
subclass in V containing A and closed under products, subalgebras, and
quotients. Moreover, there is also a well-known completeness theorem for
algebraic logic, according to which T(A) can be described directly (i.e.
without using any algebras other then A and F(X); in the language of
universal algebra it is the fully invariant congruence on F(X) generated by
the intersection of all congruences determined by homomorphisms F(X) --->

If we now move from classical universal algebra to the more elegant language
of Lawvere theories, and begin with such a theory T, then it is better not
to fix X and instead of the pairs (w,w') above talk about pairs of parallel
(Continue reading)

Prof. Peter Johnstone | 8 Aug 10:38 2006

Re: Laws

The following seems so obvious that I suspect it's not what Tom is
really asking for; but it seems to me to be an answer to his
question. A law in Tom's sense is just a parallel pair of arrows
F(X) \rightrightarrows F(1) in the algebraic theory T under
consideration (thinking of T as the dual of the category of
finitely-generated free algebras). To get the theory of algebras
satisfying a given set S of laws, you just need to construct the
product-respecting congruence on T generated by S (i.e., the usual
closure conditions for a congruence, plus the condition that
f ~ f' and g ~ g' imply f x g ~ f' x g'), and factor out by it.

Now any T-algebra A (in a category C, say) corresponds to a product-
preserving functor F: T --> C; and the set of laws satisfied by A
is just the (necessarily product-respecting) congruence generated
by F, i.e. the set of parallel pairs in T having the same image
under F. Is there anything more to it than that?

Peter Johnstone
On Mon, 7 Aug 2006, Tom Leinster wrote:

> Dear category theorists,
> Here's something that I don't understand.  People sometimes talk about
> algebraic structures "satisfying laws".  E.g. let's take groups.  Being
> abelian is a law; it says that the equation xy = yx holds.  A group G
> "satisfies no laws" if
>     whenever X is a set and w, w' are distinct elements of the free
>     group F(X) on X, there exists a homomorphism f: F(X) ---> G
(Continue reading)

flinton | 8 Aug 08:30 2006

Re: Laws

To respond to Leinster's inquiry,

"Laws" (or "equations"), as the set-based universal
algebraists understand them, are ordered pairs of
members of free algebras (i.e., pairs e = (e_1, e_2)
in F x F, for F an algebra free on some set of "free

Actually, far more often than not, the variety of
algebras these F are free in is presented by means
of operations only, and the F are then called
"absolutely free."

A given equation e "holds" in an algebra A with the
given operations iff under each homomorphism from F
to A the elements e_1 and e_2 of F are shipped to
some same value in A.

>From this perspective the Abelianness equation xy=yx
is the pair (xy, yx) in F2 x F2 (F2 denoting the
absolutely free algebra on the two free generators
x & y based on, say, three operations, one binary
(multiplication), one unary (inversion), one nullary
(choice of base point).

The associativity equation x(yz) = (xy)z is another
equation in this sense.

One need not, of course, insist dogmatically on
taking as equations ONLY pairs in absolutely free
(Continue reading)

Peter Selinger | 8 Aug 07:08 2006

Re: Laws

Hi Tom,

a lot is known about this. I will leave it to more qualified others to
give the category-theoretic account.  In set-like language, the answer
to your question is provided by universal algebra.

Denote by Th(G) the theory associated to a particular algebra G (over
a given signature). More generally, to a class of algebras S (all over
the same, from now on fixed, signature), associate Th(S), the theory
of all those equations satisfied by all the algebras in S.  Also, to a
given theory T, let V(T) be the class of all algebras satisfying the
equations in T (also called a variety of algebras).

Birkhoff's HSP theorem states that a class C of algebras is of the
form V(T), for some T, if and only if C is closed under isomorphism,
and under the operations of taking quotient algebras, subalgebras, and
cartesian products. (HSP stands for "homomorphic image, subalgebra,

As a direct consequence, let C=V(Th(G)), the class of all groups
satisfying those equations that a particular group G satisfies. Then C
is precisely the class of groups that can be obtained, up to
isomorphism, from G by repeatedly taking quotients, subalgebras, and
cartesian products. [Proof: certainly, the right-hand side is
contained in C.  Conversely, by the HSP theorem, the right-hand side
class is of the form V(T), for some T.  Since G is in the class, T can
only contain equations that hold in G, thus T is a subset of Th(G). By
contravariance of the "V" operation, it follows that C=V(Th(G)) is a
subset of V(T)].

(Continue reading)

Tom Leinster | 9 Aug 05:56 2006

More laws

Thanks very much to the many people who provided helpful, expert replies.

To recap, I asked (among other things): given an algebra A for some
theory, what can be said about the algebras obeying all the equational
laws that A obeys?

The question was posed in the context of finitary algebraic theories, and
in that context, there's a straightforward description of such algebras:
they are exactly the quotients of subalgebras of (possibly infinite)
powers of A.  As explained by Peter Selinger and George Janelidze, this
comes from Birkhoff's Theorem.

I wanted to understand this particular situation - finitary algebraic
theories and their equational laws - and I do understand it better than I
did before.  However, what I ultimately want to understand is something
slightly different and more general, which I'll now describe.

This will take a while, so I'll start with the punchline: we get some very
simple universal characterizations of some quite sophisticated objects.
For example, we'll get a characterization of the Stone spaces among all
topological spaces, and a construction of the space of Borel probability
measures on a compact space.

Here goes.  Take an algebraic theory and write F for the free algebra
functor.  Any equational law w = w' in a set X of variables generates a
congruence ~ on FX (identify w and w'), hence a quotient map

e: FX ---> (FX)/~.

An algebra A obeys this law iff e is orthogonal to A, i.e. every map FX
(Continue reading)

F W Lawvere | 8 Aug 21:19 2006


A simple answer to Tom Leinster's question involves the Galois connection
well-analyzed by Michel Hebert at Whitepoint (2006): in a fixed category
an object A can "satisfy" a morphism q: F->Q  iff  q*: (Q,A) -> (F,A) is a
bijection. Then for any class of objects A there is the class of "laws" q
satisfied by all of them, and reciprocally. If the category itself is
mildly exact, one could instead of morphisms q consider their kernels as
reflexive pairs. For example, if there is a free notion, a reflexive pair
F' =>F has a coequalizer which could be taken as a law q.

However, the "categorical story" that Tom was missing is not told well
by the "Universal Algebra" of 75 years ago. Unfortunately, Galois
connections in the sense of Ore are not "universal" enough to explicate
the related universal phenomena in algebra, algebraic geometry, and
functional analysis. The mere order-reversing maps between posets of
classes are usually restrictions of adjoint functors between categories,
and noting this explicitly gives further information. For example,
Birkhoff's theorem does not apply well to the question:

"Do groups form a variety of monoids?"

Indeed, does the word "variety" mean a kind of category or a kind of
inclusion functor? In algebraic geometry, an analogous question concerns
whether an algebraic space that is a subspace of another one is closed
(i.e. definable by equations) or not. Often instead it is defined by
inverting some global functions, giving an open subscheme, not a
subvariety, but still a good subspace. The analogy goes still further; a
typical open subspace of X is actually a closed subspace of X x R, and of
course the category of groups does become a variety if we adjoin an
additional operation to the theory of monoids.
(Continue reading)