Subject: categories: Re: Laws

From: F W Lawvere <[email-masked]>
Date: Sat, 12 Aug 2006 11:37:26 -0400 (EDT)

The thoughts being developed by Tom Leinster give renewed hope that
results of 40 years ago are being further developed, beyond mere icons,
into tools for actual analysis of algebraic problems *.

I should perhaps have mentioned Lourdes Sousa's very interesting talk at
White Point. She and Michel Hebert had divided the presentation of the
work into existential (or injective) logic, and uniquely existential
logic, and the latter is more directly relevant to the present discussion.

The fact that a contravariant adjoint pair gives rise to Galois
connections at each object is important in many different situations, for
example in the classical study of rings of continuous functions on
topological spaces. The information inherent in this remark is less
visible if one arbitrarily restricts consideration to general epis and
general monos (it was here that Tom made a "wrong turn" in his items
4.(i) and 4.(ii) ). To recover the classical Galois connection of
universal algebra one must apply adjointness, and then take surjective (or
regular epimorphic) images. The above general remark depends on the
availability of operations like image in the categories that are being
confronted in the adjointness.

Again, I emphasize that in the classical case of continuous functions, it
is important to consider algebras A which are not of the form C(Y). A
possibly useful remark is that, under suitable restrictions on the
category of spaces, the Stone-Weierstrass theorem can be interpreted as
the statement that A --> C(X) is an epimorphism of rings iff its mate
X --> Spec(A) is a monomorphism. But then by restricting the kind of
epimorphisms and monomorphisms considered one obtains Galois connections
which were originally considered by Stone in the 1930s before the more
general functorial formulation which many of us learned from
J.L. Kelley's General Topology.

If one considers a tractable functor X --> Sem(T) from a very general
category X into a very special kind of category of the classical universal
algebra type, (i.e. where T is from the special doctrine of categories
with finite products, etc.) then the structure functor Str assigns to the
composite functor X --> Sets a definite algebraic theory Str(X) with a
morphism of theories T -->Str(X). The surjective image of the latter
morphism, of course, is the embodiment of the classical construction in
the special case where the original tractable functor was a full
inclusion. However, there are many full inclusions for which one has
X = Sem(Str(X)), i.e. X is an algebraic category even though it is not a
variety in Sem(T).

Remark: The difference between an object (in this case an algebraic
category) and an inclusion map (in this discussion a full inclusion
functor) is of course not eliminated by restricting to the case where T is
a free theory. It seems reasonable to use the classical term "variety" to
refer to those inclusion functors fixed under Birkhoff's Galois
correspondence, i.e. to those for which not only is X equal to the
semantics of its structure, but for which moreover the morphism of
theories T --> Str(X) is already surjective (which of course it is not in
the example mentioned of groups in monoids).

There are several local studies possible within the context of a given
global adjoint. It seems to be an open problem to describe those full
inclusions X --> Sem(T) for which T --> Str(X) is a localization (in which
case the inclusion, if fixed, might be called "open" in contrast to the
Birkhoff subvarieties which are clearly analogous to "closed" subspaces).
A further problem: "locally closed" is a kind of inclusion of interest in
geometry, so why should it not be also here?

* see also the paper "Some Algebraic Problems..." following the Thesis in
the TAC Reprints.

On Sat, 12 Aug 2006, Tom Leinster wrote:

> 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
>
>
> > 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
> > ************************************************************
> >
> >
> >
> >
> >
> >
>
>
>
>
>
>
>
>
>
>