Re: Laws

Re: Laws

[Peter Selinger]

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,
product").

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)].

Moreover, since a subalgebra of a quotient is a quotient of a
subalgebra, and a cartesian product of quotients [subalgebras] is a
quotient [subalgebra] of a cartesian product, the three HSP operations
can be taken in this particular order: Thus, a group satisfies all the
equations that G satisfies, if and only if it is isomorphic to a
quotient of a subalgebra of some (possibly infinite) product G x ... x G.

There are generalizations to properties other than equational ones,
but I don't remember them as well. A "Horn clause" is an implication
between equations, or more precisely a property of the form (forall
x1...xn)(P1 and ... and Pn => Q), where P1,...,Pn,Q are equations.  Of
course, every equation is trivially a Horn clause (for n=0), but not
the other way around. A typical example of a Horn clause is cancellability,
the property xz=yz => x=y. (This holds in groups, but not in monoids,
and cannot be expressed equationally in monoids, because it is not
preserved under quotients).

If you want to consider the class of algebras (in general smaller than
V(Th(G))) that satisfy all the Horn clauses that G satisfies, then you
have to drop the homomorphic images. I believe that the algebras in
question will be precisely the subalgebras of products of G, but
someone might correct me if I remember this wrongly.

-- Peter

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
>     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?
>
> Thanks,
> Tom
>
>
>
>

Re: Laws

[Jiri Adamek]

Back from holidays I am slowly working through the various interesting
e-mails of Tom Leinster. The examples he presents in his e-mail on August
9 seem to lead to the following question: given on object A characterize
the full subcategory L_A  of all objects satisfying all "laws" that A
satisfies. The algebraic case ("law" meaning equation) has two obvious
generalizations: orthogonality and injectivity. For both of them the
answer to the above question is nice and easy.

INJECTIVITY: let H be the class of morphisms generated by {A} in the
Galois connection "to be injective to". (That is, H consists of all
morphisms to which A is injective.) The opposite class
	L_A = Inj H
of all objects injective w.r.t. H consists of precisely all split
subobjects of powers of A.
This holds in every category with powers.

Proof: injectivity classes are clearly closed under product and split
subobject. Conversely, if B lies in Inj H, then it is a split subobject
of the power of A to hom(B,A). In fact, the canonical morphism
m from B to the power of A to hom(B,A) lies in H: given a morphism
f: B -> A, then f factorizes through m via the projection
of A^hom(B,A) corresponding to f. Consequently, B is injective w.r.t. m,
and since B is the domain of m, this implies trivially that m is a split
mono.

ORTHOGONALITY: let K be the class of morphisms generated by {A} in the
Galois connection "to be orthogonal to". The opposite class
	L_A = Ort K
of all objects orthogonal to K is the closure of {A} under limits.
This holds in every complete and cowellpowered category.

Proof: orthogonality classes are clearly closed under limit, thus,
Ort K contains the limit closure L of {A}. To prove the opposite inclusion
observe that L is a reflective subcategory due to Freyd's SAFT: A is
easily seen to be a cogenerator of L. For every object B in Ort K
a reflection r: B -> B' in L lies in K (since A lies in L). Thus,
B is orthogonal to r. This implies that r is a split mono. Now L
contains B' and is closed under split subobjects, thus B lies in L.

FINITARY LAWS
The algebraic case has another feature: every equation, when translated
as injectivity or orthogonality w.r.t. a morphism e:A-> B, has the
property that both A and B are finitely presentable. We can thus decide
to restrict our attention to finitary morphisms, i.e., morhisms with
finitely presentable domains and codomains, as our "laws".

If H is the class of all finitary morphisms to which A is injective,
then the injectivity class Inj H is the closure of {A} under product,
filtered colimit and pure subobject. This was proved by J. Rosicky,
F. Borceux and myself in TAC 10 (2002), 148-161.

If K is the class of all finitary morphisms to which A is orthogonal,
then the orthogonality class Ort K is the closure of {A} under product,
filtered colimit and A-pure subobject as proved by L. Sousa and myself in
JPAA 276 (2004), 685-705. (The concept of A-pure subobject is a bit
artificial, but unfortunately the above result is false if one substitutes
it with pure morphism. Surprisingly, when generalizing finitary morphisms
to k-ary morphisms for uncountable cardinals k, the corresponding result
does hold with pure subobjects: see M. Hebert and J. Rosicky, Bull. London
Math. Soc 33 (2001) 685-688.)


xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
alternative e-mail address (in case reply key does not work):
J.Adamek@tu-bs.de
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx

Re: Laws

[F W Lawvere]

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

Re: Laws

[Tom Leinster]

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

Re: Laws

[George Janelidze]

Dear All,

What Tom says now, and what Bill calls a simple answer referring to Michel
Hebert, also suggests to mention

[H. Andréka and I. Németi, Los lemma holds in every category, Stud. Sci.
Math. Hung. 13, 1978, 361-376]

(although a previous paper of the same authors would be needed, I think).
And I am sure many other people also considered many other candidates for
the concept of a "law" producing a suitable Galois connection. And - no
doubt - many such constructions would produce interesting Galois closed
classes.

However, I think "the Universal Algebra of 75 years ago" gave a beautiful
and fundamental example, were the Galois closed classes are fully and
beautifully described (that Galois connection deals with subvarieties of a
fixed variety, with fixed "basic operators" and so there is no problem with
"What is a variety?" of course).

This does not mean that I am trying to argue with Bill: Of course it is true
that Bill's thesis was a great further enlightenment, and of course it is
true that TODAY seeing only those Galois connections and not seeing
adjunctions containing them and much more (also in Galois theory itself!) is
too bad!

George Janelidze

Re: Laws

[Rob Goldblatt]

One aspect of the categorisation of "equation"  is the approach of
Banaschewski and Herrlich.  This replaces an equation as a pair (s,t)
of terms that belong to some free algebra F by the least quotient
(coequaliser)

e: F -->> F/E

identifying s and t.

An algebra A satisfies equation (s,t) precisely when every
homomorphism   F --> A lifts across e to a homomorphism   F/E --> A.

Thus the notion of an equation becomes that of a regular epi e with
free domain, and an object satisfies such an e when it is injective
for e.

To obtain a notion intrinsic to a given category, the free domains
were replaced by domains that are regular-projective, i.e. projective
for all regular epis, this being a property enjoyed by free algebras
in categories of universal algebras.

The approach has been dualised in the coalgebra literature, with a
"coequation" being defined as a regular mono with regular-injective
codomain, and a "covariety" as the class of coalgebras that are
projective for some given class of coequations.

Some (not all) relevant references are below.

cheers,
Rob


            @Article{
bana:subc76,
            author = 	"B. Banaschewski and H. Herrlich",
            title = 	"Subcategories Defined by Implications",
            journal = 	"Houston Journal of Mathematics",
            year = 	"1976",
            volume = 	"2",
            number =	"2",
            pages = 	"149--171"
            }


            @Article{
adam:vari03,
            author = {Ji{\v{r}}{\'\i} Ad{\'a}mek and Hans-E. Porst},
            title = "On Varieties and Covarieties in a Category",
            journal = 	"Mathematical Structures in Computer Science",
            year = 	"2003",
            volume = {13},
            pages = "201-232"
            }

            @Techreport{
awod:coal00,
            author =	"Steve Awodey and Jesse Hughes",
            title =	"The Coalgebraic Dual of {B}irkhoff's Variety
Theorem",
            institution = "Department of Philosophy, Carnegie Mellon
University",
            year =	"2000",
            number =	"CMU-PHIL-109",
            note =  "\url{http://phiwumbda.org/~jesse/papers/
index.html}"
            }


On 8/08/2006, at 1:36 AM, 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
>     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?
>
> Thanks,
> Tom
>
>
>
>

Re: Laws

[Jon Cohen]

Hi,

> If you want to consider the class of algebras (in general smaller than
> V(Th(G))) that satisfy all the Horn clauses that G satisfies, then you
> have to drop the homomorphic images. I believe that the algebras in
> question will be precisely the subalgebras of products of G, but
> someone might correct me if I remember this wrongly.

Isomorphic images of subalgebras of products and ultraproducts, I believe
- the standard notation for this seems to be $ISP_U$.

Further, there is the interesting result that TH(G) = Th(H) for any free
nonabelian groups G and H. The following paper gives a summary of this
result and a discussion of equations in free groups:

http://www.math.mcgill.ca/olga/V00228H7.pdf

best,
Jon

--
http://rsise.anu.edu.au/~jon

Laws

[F W Lawvere]

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

Re: Laws

[George Janelidze]

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) --->
A).

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
morphisms in T - and the story above can be easily modified accordingly. And
in the new story T(A) is in fact not set-based anymore:

Indeed, if C is a category with finite products, A an internal T-algebra in
C, and (t,t') a pair of parallel morphisms in T, then A |= (t,t') should be
understood as A(t) = A(t') (elegant indeed!). And then T(A) can be defined
as "the largest quotient theory" of T obtained by making t = t' whenever A
|= (t,t'). The only thing to have in mind is that not every C is "good
enough" to get the "C-completeness" theorem.

Moving further from Lawvere theories to other kinds of theories, we will
only need to know if "the largest quotient theory" does exist. On the other
hand, moving back to, say, classical (non-categorical) first order logic, we
are in the well known situation again: if T is a first order theory and A a
model of T, everybody knows what is the elementary theory of A. What I do
not know is if anyone ever considered any kind of logic (categorical or not)
where one cannot do this. I think Michael Makkai is the right person to be
asked.

Best regards,
George

----- Original Message -----
From: "Tom Leinster" <t.leinster@maths.gla.ac.uk>
To: <categories@mta.ca>
Sent: Monday, August 07, 2006 3:36 PM
Subject: categories: Laws


> 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?
>
> Thanks,
> Tom
>
>
>
>
>

Re: Laws

[Prof. Peter Johnstone]

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
>     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?
>
> Thanks,
> Tom
>
>
>
>
>

Re: Laws

[flinton]

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
generators."

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
algebras: no harm in considering pairs in free
algebras of any variety. Thus, for example,
(xy, yx) is still a reasonable equation for groups.
But (x(yz), (xy)z) doesn't do what you think:
the RHS and LHS are ALREADY equal in every group,
and the pair is simply the diagonal entry (xyz, xyz)
(the INTENDED associativity is already a FACT for
groups, not, like commutativity, a condition that,
capable of failing, may meaningfully be imposed).

If these comments don't fully address the concerns raised,
please let me know. In any event, the laws most UAers
speak of refer to equations in absolutely free algebras
coming from the "lawless" variety whose algebras use the
same operations as another variety one is more interested
in, but are subject to the imposition of no equations
at all.

-- Fred

Tom Leinster had written:

> 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?
>
> Thanks,
> Tom
>
>
>
>

Laws

[Tom Leinster]

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?

Thanks,
Tom