1. Is the quasivariety of monoids generated by the groups and the free monoids finitely based? That is, is there a finite set of universal Horn formulas entailing the common universal Horn theory of groups and free monoids? In other words, what do groups and free monoids have in common, besides being monoids? Apart from the (equational) axioms for monoids, the only members of that theory I can think of are xy=x -> y=1 and yx=x -> y=1. 2. How different is the abelian case? More or fewer axioms? Vaughan Pratt
Vaughan asks: Is the quasivariety of monoids generated by the groups and the free monoids finitely based? The free monoids seem to be red herrings. The question is equivalent to Is the quasivariety of monoids generated by the groups finitely based? (since every free monoid is a submonoid of a group.) If the answer is known I suspect it would be well-known as a theorem about which monoids can be embedded in groups. I note that a 46-year- old paper by S.I.Adyan is still cited. It establishes just the special case of cancelation monoids given by single defining relations. Vaughn goes on to ask How different is the abelian case? More or fewer axioms? This case is easy. Again, the free commutative monoids are free herrings. Just add to the equational theory of commutative monoids the cancelation principle: xy = xz -> y = z. (Every such monoid appears in the quasivariety since its reflector into the subcat of abelian groups is an embedding.)
Dear Vaughan A related question, originating with the problem of the quality of the truth value space in M- sets, led me to the discovery of an equational class that some years later, Peter Freyd rediscovered from an entirely different point of view. What is the Structure of the union of the "variety" groups with the variety of commutative monoids ? The motivation was the common feature of the Heyting algebra of right ideals of a monoid in either class, and the partial answer is in my "Taking categories seriously", reprinted in TAC. Not only do we have to think about the meaning of "union" and about the analogy with closed subschemes (probably the source of the term "variety") but also about the fact that the inclusion of groups in monoids is more "open" than closed and is certainly not a (sub) variety even though both categories are algebraic. Again analogously, the Structure 2-functor, adjoint to Semantics does not carry full inclusions to surjective interpretations, Thus in particular in my example like others, the algebraic theory that results has more operations, not only more equations. It may be true in your case as well. Bill Quoting Vaughan Pratt <pratt@cs.stanford.edu>
1. Is the quasivariety of monoids generated by the groups and the free monoids finitely based?
That is, is there a finite set of universal Horn formulas entailing the common universal Horn theory of groups and free monoids?
In other words, what do groups and free monoids have in common, besides being monoids?
Apart from the (equational) axioms for monoids, the only members of that theory I can think of are xy=x -> y=1 and yx=x -> y=1.
2. How different is the abelian case? More or fewer axioms?
Vaughan Pratt
The Horn formulae quoted by Vaughan can of course be generalized to the cancellation laws: xy = xz => y = z (and similarly on the other side). In fact the free monoids aren't needed: every free monoid embeds as a submonoid of a (free) group, and so satisfies all Horn formulae true in groups. Thus Vaughan is asking for the universal Horn theory of those monoids which are embeddable in groups. I'm fairly sure that the answer to this is known, but I can't find a reference for it. In the commutative case, it's easy to see that the cancellation law is all you need (the proof is essentially the same as the proof that every integral domain embeds in a field), but I vaguely remember that in the non-commutative case you need something more than the cancellation laws. Generalizing in an obvious way: can one characterize those categories which admit faithful functors to groupoids by a finite collection of Horn formulae? Peter Johnstone ---------------- On Fri, 24 Mar 2006, Vaughan Pratt wrote:
1. Is the quasivariety of monoids generated by the groups and the free monoids finitely based?
That is, is there a finite set of universal Horn formulas entailing the common universal Horn theory of groups and free monoids?
In other words, what do groups and free monoids have in common, besides being monoids?
Apart from the (equational) axioms for monoids, the only members of that theory I can think of are xy=x -> y=1 and yx=x -> y=1.
2. How different is the abelian case? More or fewer axioms?
Vaughan Pratt
Dear Vaughan, 1. Instead of universal Horn formulas I shall talk about quasiidentities, which is the same thing in your context. Recall: A quasiidentity is a first order formula of the form (P1&...&Pn)=>Q, where P1,...,Pn,Q are atomic formulas (i.e. "equations of terms"). A class of universal algebras is said to be a quasivariety if it can be axiomatized with quasiidentities. Quasivarieties can be characterized as classes of algebras closed under subalgebras, products, and filtered colimits (the only reason for filtered colimits is that we want n above to be finite; products and filtered colimits can be replaced here with filtered products). 2. Since the free monoid on a set X can be considered as a submonoid of the free group on the same X, the quasivariety of monoids generated by groups contain all free monoids. In other words, every quasiidentity that holds for all groups, will also hold for all free monoids. That is, asking your question, forget free monoids! 3. The quasivariety of monoids generated by groups obviously consists exactly of all those monoids that can be embedded into groups. Hence one should probably see Malcev, A. Über die Einbettung von assoziativen Systemen in Gruppen. (Russian) Rec. Math. [Mat. Sbornik] N.S. 6 (48), (1939). 331--336. MR0002152 (2,7d) Malcev, A. Über die Einbettung von assoziativen Systemen in Gruppen. II. (Russian) Rec. Math. [Mat. Sbornik] N.S. 8 (50) (1940). 251--264. MR0002895 (2,128b) 4. I do not have these papers here in Cape Town. But I seem to remember that Mal'tsev had an infinite list of quasi-identities which describes the quasi-variety of monoids that can be embedded into groups. Furthermore it seems (I am not sure) that he actually introduced the term "quasiidentity" exactly for this purpose. The first non-trivial one, which he called Condition Z, was (as = bt) & (cs = dt) & (au = bv) => (cu = dv); this condition obviously holds in every group and therefore in every submonoid of a group, but he constructed a semigroup with cancellation in which it does not hold. (Here the difference between monoids and semigroups is irrelevant here). I do not know much did Mal'tsev know about universal constructions; once Mac Lane told me that Zariski knew them... Knowing them, one would of course begin by looking at the universal group with a homomorphism from a given monoid into it, and taking the list of quasiidentities from the description of the congruence involved in the construction of that group. 5. Your idea of xy = x => y = 1 and yx = x => y = 1 is too bad (sorry!), because it is even weaker than the usual cancellation xy = xz => y = z and yx = zx => y = z. For, take the quotient of the free monoid on {x,y} by identifying xx = xy (and = yx = yy if you like); it satisfies your implications but not the cancellation. 6. In the abelian case (obviously) it is just one quasiidentity, namely the cancellation. That is, the quasivariety of abelian monoids that can be embedded into groups is determined by the axiom x + y = x + z => y = z. George Janelidze ----- Original Message ----- From: "Vaughan Pratt" <pratt@cs.stanford.edu> To: "categories list" <categories@mta.ca> Sent: Friday, March 24, 2006 10:08 AM Subject: categories: Progressive or linear or ... monoids?
1. Is the quasivariety of monoids generated by the groups and the free monoids finitely based?
That is, is there a finite set of universal Horn formulas entailing the common universal Horn theory of groups and free monoids?
In other words, what do groups and free monoids have in common, besides being monoids?
Apart from the (equational) axioms for monoids, the only members of that theory I can think of are xy=x -> y=1 and yx=x -> y=1.
2. How different is the abelian case? More or fewer axioms?
Vaughan Pratt
Thanks to Peter, Peter, and George for the uniformly equivalent answers to my question (in striking contrast to the decided lack of uniformity of the responses to other recent topics on this list). (Bill's response was less an answer than a pointer to related work with "commutative" in place of "free" in my question, interesting but for different reasons.) I should have noticed that free monoids were a red herring, and I have no idea why I restricted to z=1 in xy=xz->y=z. The crux of the obstacle to axiomatizing the nonabelian case is clearly brought out by Malcev's Condition Z cited by George Janelidze as
(as = bt) & (cs = dt) & (au = bv) => (cu = dv);
If you could just shuffle the terms around, Z along with the larger "quasiidentities" would all collapse under cancellation, as everyone pointed out. At first glance one might think to organize Condition Z with proof nets of some kind, something along the lines of au = bv | | as = bt .| | cs = dt ------- cu = dv and so on for longer such sorites along with (independent?) reflections of each side. (The stray dot is against mailers that delete leading spaces, apologies to those not receiving this in a fixed-width font.) However googling for relevant material led to a 194-page St. Andrew's thesis submitted last July on "Presentations for subsemigroups of groups" by Alan Cain, available at http://www-history.mcs.st-and.ac.uk/~alanc/maths/publications/c_phdthesis/c_... The preface indicates how one can do better via J.-C. Spehner's notion of a Malcev presentation. (Anyone know if this is the same J.-C. Spehner as does computational geometry at Labo MAGE?)
This thesis is largely concerned with subsemigroups of groups, and from its pages a reader may discover much of their character and a little of their history. The title is perhaps a little restrictive: the body of the thesis approaches subsemigroups of groups from three directions: `ordinary' semigroup presentations, Malcev presentations, and automatic structures.
Malcev presentations are semigroup presentations of a special type for group-embeddable semigroups, introduced by Spehner (1977). Informally, whilst an `ordinary' semigroup presentation defines a semigroup by means of generators and defining relations, a Malcev presentation defines a semigroup using generators, defining relations, and a rule of group-embeddability. This rule of group-embeddability is worth an infinite number of defining relations, in the sense that a semigroup may admit a finite Malcev presentation but no finite ordinary presentation. During the three decades since Spehner's definition, little research was carried out in the area. This thesis should convince the reader that this neglect has been unfair. In preparation for the main body of the thesis, Chapter 1 formally defines Malcev presentations and establishes their basic properties.
Spehner's basic idea, on the semantic side, is that if it is known by all parties (writers and readers) that the intended congruence on a semigroup S makes S/~ embeddable in a group, then one can uniquely determine ~ with less of it than without that knowledge. The crucial fact here is that the family of all congruences ~ on a semigroup S for which S/~ embeds in a group is closed under arbitrary (including empty) intersection (consider the product of the witnessing embedding groups). Hence any binary relation R on a semigroup S has a unique minimal extension to such a congruence, namely the intersection of all such congruences containing R. A Malcev presentation of a desired such congruence is any binary relation R that generates it in this way. So in particular if au = bv, as = bt, and cs = dt are all in R, then the conclusion cu = dv of Condition Z is in this "Malcev closure" of R. On the syntactic side, the appropriate term rewriting system incorporating this knowledge of group-embeddability augments the vocabulary with left and right inverses of generators, allowing this conclusion to be obtained equationally, without resorting to quasiidentities, as cu = csSu = dtSu = dBbtSu = dBasSu = dBau = dBbv = dv where I've written S for the right inverse of s and B for the left inverse of b for want of a third flavor of s and b in ASCII. After developing the basis for, and variants of, all this, the thesis then dives into automatic semigroups, a subject with a rich literature and some very deep results that I have so far been completely unable to motivate myself to participate in (starting with Michael Arbib's lectures on this general genre at Sydney University in the Australian winter of 1967, give or take a winter, and then more lectures in the same vein in 1969 by John Rhodes at Berkeley). Maybe some day I'll see the point of it all, though so far I've had more success eventually seeing the point of Max Kelly's 1965 lectures on category theory, that only took two decades (slow learner). I'm fine with algebraic logic (which was my route back to category theory in 1983), algebraic automata theory seems an altogether different kettle of fish -- the deployment of weapons of math destruction in an unwinnable war on the combinatorial complexity of automata and semigroups. Again, many thanks for the answers and pointers! Vaughan Pratt
participants (5)
-
George Janelidze -
Peter Freyd -
Prof. Peter Johnstone -
Vaughan Pratt -
wlawvere＠buffalo.edu