From mboxrd@z Thu Jan 1 00:00:00 1970 X-Msuck: nntp://news.gmane.io/gmane.science.mathematics.categories/3373 Path: news.gmane.org!not-for-mail From: "George Janelidze" Newsgroups: gmane.science.mathematics.categories Subject: Re: Laws Date: Tue, 8 Aug 2006 13:28:12 +0200 Message-ID: NNTP-Posting-Host: main.gmane.org Content-Type: text/plain; charset="iso-8859-15" Content-Transfer-Encoding: 7bit X-Trace: ger.gmane.org 1241019266 8475 80.91.229.2 (29 Apr 2009 15:34:26 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Wed, 29 Apr 2009 15:34:26 +0000 (UTC) To: Original-X-From: rrosebru@mta.ca Tue Aug 8 08:51:11 2006 -0300 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Tue, 08 Aug 2006 08:51:11 -0300 Original-Received: from Majordom by mailserv.mta.ca with local (Exim 4.61) (envelope-from ) id 1GAQ5C-0007Zz-2Z for categories-list@mta.ca; Tue, 08 Aug 2006 08:49:14 -0300 Original-Sender: cat-dist@mta.ca Precedence: bulk X-Keywords: X-UID: 6 Original-Lines: 100 Xref: news.gmane.org gmane.science.mathematics.categories:3373 Archived-At: 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 in V generated by A. By a classical theorem, due to Garrett Birkhoff, 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" To: 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 > > > > >