Re: Progressive or linear or ... monoids?

Re: Progressive or linear or ... monoids?

[Peter Freyd]

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

Re: Progressive or linear or ... monoids?

[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_phdthesisonesided.ps

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

Re: Progressive or linear or ... monoids?

[George Janelidze]

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

Re: Progressive or linear or ... monoids?

[Prof. Peter Johnstone]

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

Re: Progressive or linear or ... monoids?

[wlawvere]

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

Progressive or linear or ... monoids?

[Vaughan Pratt]

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