Subject: categories: Progressive or linear or ... monoids?

From: Vaughan Pratt <[email-masked]>
Date: Fri, 24 Mar 2006 00:08:15 -0800

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

---

From: "George Janelidze" <[email-masked]>
Date: Sat, 25 Mar 2006 20:50:39 +0200

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

---

From: [email-masked]
Date: Sat, 25 Mar 2006 08:46:14 -0500

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 <[email-masked]>

---

From: "Prof. Peter Johnstone" <[email-masked]>
Date: Sat, 25 Mar 2006 16:58:11 +0000 (GMT)

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