Subject: categories: Laws

From: F W Lawvere <[email-masked]>
Date: Tue, 8 Aug 2006 15:19:29 -0400 (EDT)

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.

In my thesis (1963)
(now available on-line as a TAC Reprint, and extensively
elaborated on by Linton and others in SLNM 80) I isolated an adjoint pair
"Structure/Semantics" strictly analogous to the basic "Function
algebra/Spectrum) pairs occurring in algebraic geometry and in functional
analysis. In that context, note that the epimorphisms in the category of
theories (categories with finite products) include both surjections (laws
given by equations, dual semantically to Birkhoff subvarieties) as well as
localizations (laws given by adjoining inverses to previously given
operations, semantically corresponding to "open" algebraic subcategories).
Can these "open" inclusions between algebraic categories be characterized
semantically?

The technical notion "Structure of" was motivated by the example of
cohomology operations: in general, the totality of natural operations on
the values of a given functor involves both more operations and more laws
than those of the codomain category. The example illustrates that such
adjoints are of much broader interest than the mere perfect duality that
one might obtain by restricting both sides (one does not expect to recover
a space from its cohomology, and the category of spaces studied is not
even an algebraic category).

As an important further example of a large adjoint which specializes both
to Galois connections in each space as well as to a perfect duality on
suitable subcategories, consider Stone's study of the relation between
spaces and real commutative algebras; for computational purposes,
the spaces of the form C(X) need to receive morphisms from algebras A
(like polynomial algebras) that are not of that form; such homomorphisms
are by adjointness equivalent to continuous maps X --> Spec(A), where
Spec(A) would map further to R^n if n were a chosen parameterizer for
generators of A in a presentation.

Best wishes to all.

Bill

************************************************************
F. William Lawvere
Mathematics Department, State University of New York
244 Mathematics Building, Buffalo, N.Y. 14260-2900 USA
Tel. 716-645-6284
HOMEPAGE:  http://www.acsu.buffalo.edu/~wlawvere
************************************************************

---

From: "Tom Leinster" <[email-masked]>
Date: Sat, 12 Aug 2006 00:18:24 +0100 (BST)

Thanks to Bill Lawvere for pointing out the close connection between the
questions I was asking and the recent work of Jiri Adamek, Michel Hebert
and Lurdes Sousa, presented at both CT06 and the Glasgow PSSL.  It must
have lodged itself in my mind in some subliminal way; apologies for not
mentioning it earlier.

Perhaps the following is rather basic, but I'm failing to understand one
of the points in Bill's message.  As I read it, he's saying that the
Galois connection of traditional universal algebra (connecting sets of
laws and varieties of algebras) is contained within the
structure-semantics adjunction of his thesis.  I don't see how this works.

I *do* understand the following points:

1. Traditional universal algebra - given a signature S, one has the set E
of equations between S-terms and the class V of S-algebras, and the
relation "satisfaction" gives a Galois connection between the
power-sets/classes P(E) and P(V).  A Galois connection is, of course, a
contravariant adjunction on the right between posets.

2. Categorical algebra - structure and semantics form a contravariant
adjunction on the right between the category Th of Lawvere theories and
(roughly speaking) the category K of categories over Set.  One is a
section of the other: if T is a theory then Struc(Sem(T)) = T.

3. If T is a theory, any equation between the operations in T can be
construed as a pair of parallel arrows in T, and so induces a map from T
to the quotient theory T' obtained by imposing this equation.  Such a map
T ---> T' is an epimorphism, although not every epi in the category of
theories arises in this way.

4. Given a contravariant adjunction on the right, both functors turn
colimits into limits, hence epis into monos.  In particular, any set of
equations between the operations of a theory T induces an epi T ---> T',
hence a mono Sem(T') ---> Sem(T) between the categories of models, which
may perhaps be the inclusion of a full subcategory.

This makes it look as if there's going to be a Galois connection between
the poset of quotient objects of T (i.e. epis out of T) and subobjects of
Sem(T), for every theory T.  But there seem to be two problems:

(i) the functors in an adjunction on the right don't in general turn monos
into epis, so I don't see why the structure-semantics adjunction is going
to turn subcategories of Sem(T) into quotient theories of T;

(ii) even if this did work, epis out of T are more general than equations,
and monos into Sem(T) are more general than full subcategories, so it
wouldn't exactly recover the classical Galois connection of universal
algebra.

I guess I've made a wrong turn somewhere; can someone put me right?

Thanks,
Tom

> localizations (laws given by adjoining inverses to previously given
operations, semantically corresponding to "open" algebraic
subcategories).
suitable subcategories, consider Stone's study of the relation between
spaces and real commutative algebras; for computational purposes, the
spaces of the form C(X) need to receive morphisms from algebras A (like
polynomial algebras) that are not of that form; such homomorphisms are by
adjointness equivalent to continuous maps X --> Spec(A), where
Spec(A) would map further to R^n if n were a chosen parameterizer for
generators of A in a presentation.