From: Helmut.Richter@lrz-muenchen.de (Helmut Richter) Subject: free algebras Date: 6 Mar 2000 10:02:38 GMT Newsgroups: sci.math Summary: [missing] I have a somewhat vague feeling what a free algebra is, and tried to get a more well-defined picture. In Grätzer's book "Universal Algebra" three entire chapters are devoted to free algebras; their definition is not very intuitive and requires the previous reading of three other chapters (if only for the notation). In contrast to that, Birkhoff's book "Lattice Theory" considers free algebras so obvious that he does not devote space in the text proper but just makes some remarks about them in the preface. A number of other algebra books (e.g. Birkhoff/MacLane, v.d.Waerden) do not mention free algebras with a single word. Let me depict the "vague feeling" first: We start with a generating set and build all terms using the operators; then define an equivalence relation: two terms are equivalent if they can be proven equal by the axioms of the underlying theory (e.g. the group axioms if we are looking for free groups). This is then a congruence relation and the equivalence classes might form an algebra which is then a free algebra. Complications can occur when the congruence classes are not sufficient, for instance because the axioms require the existence of certain things which are not fulfilled by any of these terms. I assume that the more complicated definition of free algebras deals with these complications. The context where I would like to use it is probably fairly simple, and the construction with the terms will probably suffice. Now concrete questions to this group: - Is the above picture correct, or is it only correct under additional constraints? - What reading would you suggest for a short introduction? Thank you. Helmut Richter ============================================================================== From: magidin@bosco.berkeley.edu (Arturo Magidin) Subject: Re: free algebras Date: 6 Mar 2000 15:38:50 GMT Newsgroups: sci.math In article <89vvnu$add$1@wsc10.lrz-muenchen.de>, Helmut Richter wrote: >I have a somewhat vague feeling what a free algebra is, and tried to >get a more well-defined picture. In Grätzer's book "Universal Algebra" >three entire chapters are devoted to free algebras; their definition >is not very intuitive and requires the previous reading of three other >chapters (if only for the notation). In contrast to that, Birkhoff's >book "Lattice Theory" considers free algebras so obvious that he does >not devote space in the text proper but just makes some remarks about >them in the preface. A number of other algebra books (e.g. >Birkhoff/MacLane, v.d.Waerden) do not mention free algebras with a >single word. I assume from the above that you mean a universal algebra, or an algebra of a given type \Omega. You should be careful, since the term "algebra" is usually reserved for something else (a k-algebra is a ring with a copy of k in its center, where k is a field). >Let me depict the "vague feeling" first: > >We start with a generating set and build all terms using the >operators; then define an equivalence relation: two terms are >equivalent if they can be proven equal by the axioms of the underlying >theory (e.g. the group axioms if we are looking for free groups). >This is then a congruence relation and the equivalence classes might >form an algebra which is then a free algebra. Complications can occur >when the congruence classes are not sufficient, for instance because >the axioms require the existence of certain things which are not >fulfilled by any of these terms. Ehr, no. In a universal algebra of a given type, no axioms are of the form "existence." For example, to truly define groups as universal algebras, you do not define them as a set with one operation and the usual axioms (associtivity, existence of neutral elements, existence of inverses). Rather, you define them as a group with ->three<- operations: a zeroary operation (which is equivalent to a 'distinguished element', called 'e'; a unary operation, called 'inverse' (let me denote it by i for the purposes of this), and a binary operation, called multiplication, denoted for the purposes of this example by m. So a group is an algebra of type (0,1,2), which satisfies the following axioms: (1) Assocativity: m(m(x,y),z)=m(x,m(y,z)) for all x,y,z (2) m(e,-)=m(-,e)=id (note that m is a binary operation, e is a zeroary operation, so you can consider m(e,-) as a unary operation, so you can compare it with the identity operation, which is what we do above). (3) m(i(x),x)=m(x,i(x))=e for all x. So the axioms don't really talk about "existence", but only about identities satisfied by the operations. >I assume that the more complicated definition of free algebras deals >with these complications. > >The context where I would like to use it is probably fairly simple, >and the construction with the terms will probably suffice. Now >concrete questions to this group: > >- Is the above picture correct, or is it only correct under additional > constraints? You should be careful with your definition of "algebras". In general, distinguished elements are treated as zeroary operations rather than existence (this holds, for example, for bounded lattices, which have two zeroary operations); elements that exist depending on other elements whould be described via operations of the relevant arity. >- What reading would you suggest for a short introduction? I may be a bit partial, seeing how I learned it there and he was my advisor and all, but I like George M. Bergman's "An Invitation to General Algebra and Universal Constructions." You can find about it in his homepage at www.math.berkeley.edu/~gbergman It is really more a category theory course than a universal algebra, but what is essentially does is to construct universal algebras using the language of categories. It ignores some of the problems Universal Algebraists are interested in like congruence lattices and so on, but if what you want is to get a feel for free algebras and the like, I cannot think of a better reference. ====================================================================== "It's not denial. I'm just very selective about what I accept as reality." --- Calvin ("Calvin and Hobbes") ====================================================================== Arturo Magidin magidin@math.berkeley.edu ============================================================================== From: Helmut.Richter@lrz-muenchen.de (Helmut Richter) Subject: Re: free algebras Date: 7 Mar 2000 10:58:29 GMT Newsgroups: sci.math magidin@bosco.berkeley.edu (Arturo Magidin) writes: >In article <89vvnu$add$1@wsc10.lrz-muenchen.de>, >Helmut Richter wrote: >>I have a somewhat vague feeling what a free algebra is, and tried to >>get a more well-defined picture. [...] >I assume from the above that you mean a universal algebra, or an >algebra of a given type \Omega. You should be careful, since the term >"algebra" is usually reserved for something else (a k-algebra is a >ring with a copy of k in its center, where k is a field). You assume correctly that I do not mean an algebra in the special sense that is somewhat related to vector spaces over a field. Unfortunately, in the mathematical disciplines dealing with these things (logic, algebra, and category theory), a different lingo for the same or similar things is applied. I am most accustomed to the lingo of logics, and would define "algebra" as a structure with finitely many n-ary functions where all n are finite numbers greater or equal to zero. In order to be able to speak about things like "homomorphisms", it is necessary to have a first-order theory of which the structures are models (e.g. group theory if we speak about groups). "Type" (if I understand the term correctly) is not enough, as it defines only the language (how many n-ary functions for each n) but not the axioms that must be valid. Again unfortunately, there is, to my knowledge, no general term for a class of algebras in this sense that are models of a given theory. "Category" might come closest but the category people do not look inside the structure - they are more interested in morphisms between them. But: >Ehr, no. In a universal algebra of a given type, no axioms are of the >form "existence." >For example, to truly define groups as universal algebras, you do not >define them as a set with one operation and the usual axioms >(associtivity, existence of neutral elements, existence of >inverses). Rather, you define them as a group with ->three<- >operations: a zeroary operation (which is equivalent to a >'distinguished element', called 'e'; a unary operation, called >'inverse' (let me denote it by i for the purposes of this), and a >binary operation, called multiplication, denoted for the purposes of >this example by m. This simplifies *some* things but complicates others. For instance, for fields where m is the multiplicative inverse, the axiom reads: x=0 or x·m(x)=1 which is more than just an equation. For algebraically closed fields, you have for each n>0 an axiom If a_n ¬= 0 there is x that a_n·x^n+...+a_0·x^0=0 (where, for each single n, the ellipsis can be explicitly written as a concrete term - it is thus not part of the language) It may be that you can get rid of the existential quantifier in this special case but there are certainly algebraic (i.e. first-order) theories where you cannot. The restriction on theories where all axioms are equations is hard. Well, the existence of free algebras seems to have to do with this restriction (in a way I try to learn by posting questions here) but it seems to be an over-simplification to start with this restriction. >>- What reading would you suggest for a short introduction? >I may be a bit partial, seeing how I learned it there and he was my >advisor and all, but I like George M. Bergman's "An Invitation to >General Algebra and Universal Constructions." You can find about it in >his homepage at >www.math.berkeley.edu/~gbergman >It is really more a category theory course than a universal algebra, >but what is essentially does is to construct universal algebras using >the language of categories. It ignores some of the problems Universal >Algebraists are interested in like congruence lattices and so on, but >if what you want is to get a feel for free algebras and the like, I >cannot think of a better reference. Thanks. I'll look into it. Helmut Richter ============================================================================== From: magidin@bosco.berkeley.edu (Arturo Magidin) Subject: Re: free algebras Date: 7 Mar 2000 15:45:24 GMT Newsgroups: sci.math In article <8a2ncl$j8s$1@wsc10.lrz-muenchen.de>, Helmut Richter wrote: >magidin@bosco.berkeley.edu (Arturo Magidin) writes: > >>In article <89vvnu$add$1@wsc10.lrz-muenchen.de>, >>Helmut Richter wrote: >>>I have a somewhat vague feeling what a free algebra is, and tried to >>>get a more well-defined picture. [...] > >>I assume from the above that you mean a universal algebra, or an >>algebra of a given type \Omega. You should be careful, since the term >>"algebra" is usually reserved for something else (a k-algebra is a >>ring with a copy of k in its center, where k is a field). > >You assume correctly that I do not mean an algebra in the special >sense that is somewhat related to vector spaces over a field. > >Unfortunately, in the mathematical disciplines dealing with these >things (logic, algebra, and category theory), a different lingo for >the same or similar things is applied. I am most accustomed to the >lingo of logics, and would define "algebra" as a structure with >finitely many n-ary functions where all n are finite numbers greater >or equal to zero. In order to be able to speak about things like >"homomorphisms", it is necessary to have a first-order theory of which >the structures are models (e.g. group theory if we speak about >groups). "Type" (if I understand the term correctly) is not enough, >as it defines only the language (how many n-ary functions for each n) >but not the axioms that must be valid. You usually speak of a "variety of algebras of a given type"; the 'variety' term means that you are talking about all algebras which satisfy a set of identities. >Again unfortunately, there is, to my knowledge, no general term for a >class of algebras in this sense that are models of a given theory. >"Category" might come closest but the category people do not look >inside the structure - they are more interested in morphisms between >them. > >But: > >>Ehr, no. In a universal algebra of a given type, no axioms are of the >>form "existence." > >>For example, to truly define groups as universal algebras, you do not >>define them as a set with one operation and the usual axioms >>(associtivity, existence of neutral elements, existence of >>inverses). Rather, you define them as a group with ->three<- >>operations: a zeroary operation (which is equivalent to a >>'distinguished element', called 'e'; a unary operation, called >>'inverse' (let me denote it by i for the purposes of this), and a >>binary operation, called multiplication, denoted for the purposes of >>this example by m. > >This simplifies *some* things but complicates others. For instance, >for fields where m is the multiplicative inverse, the axiom reads: > > x=0 or x·m(x)=1 > >which is more than just an equation. Fields are not usually treated as universal algebras, precisely because of this problem. On the other hand, one can extend the definition to allow ->partial<- operations, in which case it is easy to define fields: the zero element is a distinguished element, and then one can define a partial operation i on the complement of the image of zero. However, once one introduces partial operations, things get complicated. For one, even if f:A->B is a morphism, it is no longer true that f(A) is necessarily a subalgebra of B; so one has to be very, very careful with partial operations. Nevertheless you run into some problems. For example, there is no "free field on n elements" in the sense of being an adjoint to the underlying set functor. >For algebraically closed fields, you have for each n>0 an axiom > > If a_n ¬= 0 there is x that a_n·x^n+...+a_0·x^0=0 > >(where, for each single n, the ellipsis can be explicitly written as a >concrete term - it is thus not part of the language) Algebraically closed fields is also not a class one usually treats from the standpoint of universal algebra. Again, there is no left adjoint to the underlying set functor, so you don't have a good notion of "free algebraically closed field on the set X." >It may be that you can get rid of the existential quantifier in this >special case but there are certainly algebraic (i.e. first-order) >theories where you cannot. Both fields and algebraically closed fields are not treated as theories by Universal Algebra, although they probably are by Model Theory or Logic (I am not familiar enough with those fields to say authoritatively). This may also be part of the problem you are encountering, in trying to apply notions where they weren't meant to be applied. >The restriction on theories where all axioms are equations is hard. >Well, the existence of free algebras seems to have to do with this >restriction (in a way I try to learn by posting questions here) but it >seems to be an over-simplification to start with this restriction. Given what people say about Universal Algebra, I would certainly not qualify it as an "over-simplification"! Another way to think of "free algebra on X" is as the left adjoint to the underlying set functor. To wit, if you are in theory T where all objects have underlying sets and the morphisms are set morphisms, you get the forgetful functor U:T=>Sets, which associates to every algebra in T its underlying set. The "free algebra construct" is meant to be the adjoint of this functor, in the sense that it should be a functor F:Sets=>T, with the property that for every set X and every algebra A in T, there exists a natural bijection between the morphism sets: Mor_{Sets}(X,U(A)) and Mor_{T}(F(X),A). which is functorial. So, consider for example fields. If there were a good notion of "free field" you would need to have an adjoint to the underlying set functor. The free field on the empty set would be the initial object of the category of fields, since it would need to have a unique map to each and every field. But of course, you could excise the empty set from your theory (a common practice among certain Universal Algebraists, although one in which I would agree with you that it is an over-simplification). What would the free field on one element be? Note that a morphism of fields is either the zero map or an injection. So, say F is the free field on one element x. That means that given any field A and any element a in A, there must exist a unique (field) morphism from F to A mapping x to a. Now, pick a field A of characteristic different from F, and note that any map F->A must necessarily be the zero map, so if we pick an a which is not zero there cannot exist a map from F to A mapping x to a. So there is no "good" notion of free field. Trivially, one can verify that this is also true of "algebraically closed fields." Another reason for not treating fields in Universal Algebra is that UA tends to revolve around three algebraic operations: taking subalgebras, taking direct products, and taking quotients modulo a congruence relation (as exemplified in Birkhoff's HSP Theorem). The direct product of fields is not a field; this also tells you that you cannot really use the tools of Universal Algebra to deal with, for example, integral domains, since they also do not form a variety. ====================================================================== "It's not denial. I'm just very selective about what I accept as reality." --- Calvin ("Calvin and Hobbes") ====================================================================== Arturo Magidin magidin@math.berkeley.edu ============================================================================== From: BPM Mixmaster Remailer Subject: free algebras Date: Tue, 7 Mar 2000 09:10:51 -0800 (PST) Newsgroups: sci.math In our last episode: >>We start with a generating set and build all terms using the >>operators; then define an equivalence relation: two terms are >>equivalent if they can be proven equal by the axioms of the underlying >>theory (e.g. the group axioms if we are looking for free groups). This is >>then a congruence relation and the equivalence classes might form an >>algebra which is then a free algebra. Complications can occur when the >>congruence classes are not sufficient, for instance because the axioms >>require the existence of certain things which are not fulfilled by any of >>these terms. >> >>I assume that the more complicated definition of free algebras deals with >>these complications. >>What reading would you suggest for a short introduction? > >I may be a bit partial, seeing how I learned it there >and he was my advisor and all, but I like George M. >Bergman's "An Invitation to General Algebra and >Universal Constructions." I also looked at Bergman's notes on what is sometimes known as "General Nonsense". (In a good way, of course.) For the earnest student, the pages are quite thought-provoking. But I wish to add to Dr. Magidin's commentary. The idea behind a free algebra A is that, except for the relations that are required for A to be the type of algebra under consideration (e.g. a commutative monoid, or a distributive lattice, or a bilinear algebra over a field) A satsifies no other conditions. Alternatively, let X be a subset of A such that X generates A, and bigK be a class of algebras of the same type as A. Then A is a free bigK-algebra over X iff for any algebra B in the class bigK and set map b from X into B, there is a homomorphism a:A->B which agrees with b on X. So the elements X satisfy no other relations beyond those that are expected for any n elements of any algebra in bigK. For certain classes of algebras (namely varieties), one can exhibit algebras A and sets X with A being a free algebra over X for the variety, by a process similar to what was previously described. In this case, the congruences are determined by equations that hold for all members of the class. So one can actually construct the free algebra just by reference to the equations, without actually having to know the algebras in the class itself. For more general classes which are not just defined by equations, one might prefer the above formulation of the algebra being free for a class over a set of generators. Of course, this makes proving the existence of such an algebra more difficult. One approach is to find an algebra which is free for a larger class, then it will be free for the desired class as well. For more information in the case the class of algebras is a variety, or close to a variety, one can consult McKenzie, McNulty, and Taylor's "Algebras, Lattices, Varieties, Vol I. There is also Burris and Sankappanavar's "A First Course in Universal Algebra" or something similarly titled. It took me several sources before I was comfortable with the concept of free algebra. I recommend studying the concept of universal mapping property, which is implicit in the first paragraph above. If you are interested in special classes of algebras, you might also look at quasi-varieties and psuedo-varieties. My memory fails me at this point, but I suspect one class is definable by Horn sentences in a theory, and the other refers to finite models and is definable by a set of pseudo-identities which are formalizable in an infinitary language, or as satisfying all but a finite number of equations. Check the literature for the actual details. G. Paseman, 2000.03.07 ============================================================================== From: Arturo Magidin Subject: Re: free algebras Date: Wed, 08 Mar 2000 18:20:29 GMT Newsgroups: sci.math In article <200003071710.JAA23160@acid.bpm.ai>, BPM Mixmaster Remailer wrote: > [.snip.] > If you are interested in special classes of algebras, > you might also look at quasi-varieties and > psuedo-varieties. My memory fails me at this point, > but I suspect one class is definable by Horn sentences > in a theory, and the other refers to finite models and > is definable by a set of pseudo-identities which are > formalizable in an infinitary language, or as satisfying > all but a finite number of equations. Check the literature > for the actual details. In terms of algebraic operations, a variety is a class closed under homomorphic images, subalgebras, and arbitrary direct products. A pseudovariety is a class closed under homomorphic images, subalgebras, and ->finite<- direct products. For example, the class of all solvable groups is a pseudovariety, but it is not a variety. A quasivariety is a class closed under arbitrary direct products, subalgebras, and ->isomorphic<- images. ================================================ "It's not denial. I'm just very selective about what I accept as reality" -- Calvin ("Calvin and Hobbes") ================================================ Arturo Magidin magidin@math.berkeley.edu magidin@matem.unam.mx Sent via Deja.com http://www.deja.com/ Before you buy.