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