Re: Laws

["George Janelidze" <janelg@telkomsa.net>]

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