Talk:Special classes of semigroups

Latest comment: 12 years ago by Deltahedron in topic Aperiodic semigroup

It would be very useful if this article had anchors in the table, so we can send redirects to the right entries. Tijfo098 (talk) 01:18, 29 April 2011 (UTC)Reply

Apparently there is a template that can be used for this purpose {{Anchored list}}. However it doesn't do tables. :-( Tijfo098 (talk) 23:40, 5 May 2011 (UTC)Reply

Aperiodic semigroup

edit

This entry has four bullet points, cited to Gril p.119 (which I don't currently have access to):

  • ab = ba
  • ak is in a subgroup of S for some k.
  • Every nonempty subset of E has an infimum.
  • Every subgroup of S is trivial.

It isn't clear whether these are intended to be cumulative or alternative, but in any case they seem quite wrong. The first bullet is commutativity, which is no part of the definition. The fourth is correct. The second is incorrect. The third is not explained (what is the order on idempotents). Deltahedron (talk) 17:21, 11 October 2012 (UTC)Reply

I didn't add that entry, but I have access to the book. I think the entry was added based on this (pp. 118-119):
-- Tijfo098 (talk) 17:55, 11 October 2012 (UTC)Reply
And we have an article Aperiodic monoid, which more or less says the same. "A finite semigroup is aperiodic if and only if it contains no nontrivial subgroups. In terms of Green's relations, a finite semigroup is aperiodic if and only if its H-relation is trivial. These two characterizations extend to group-bound semigroups." (but uses different sources.) The bullets here are confusing, I agree. Tijfo098 (talk) 17:59, 11 October 2012 (UTC)Reply

By the way, this page is missing what Grillet calls "complete semigroups" (and which is used in the Corollary 6.4 above, and implicitly in the bullets). I'm quoting from p. 110, but not using the quote marks template because it doesn't work with all that math in it, heh:

BEGIN QUOTE>>

By commutativity the idempotents of a commutative semigroup S constitute a semilattice E(S). We call a commutative semigroup S complete in case
(1) every archimedean component of S contains an idempotent; equivalently, every element of S has a power in a subgroup of S; (2) the semilattice E(S) is complete (every non-empty subset A of E(S) has an infimum  ).

Semigroups with property (1) have been called  -regular, pseudo-invertible, and epigroups. For a commutative semigroup, property (1) implies that the universal semilattice Y(S) = S/  of S is isomorphic to E(S).

Finite commutative semigroups are complete (since every finite archimedean semigroup contains an idempotent, and finite semilattices are complete). Complete commutative semigroups were first considered by the author [1975c] in the finitely generated case.

<<ENDQUOTE. Tijfo098 (talk) 18:20, 11 October 2012 (UTC)Reply

So it looks to me that the definition of aperiodic semigroups in the wiki table is following Grillet correctly: the bullet conditions are to be understood as ANDed together. Tijfo098 (talk) 18:34, 11 October 2012 (UTC)Reply

So these are properties, not the definition, of a commutative aperiodic monoid/semigroup. But as I said above, commutativity is no part of the definition of being aperiodic. Among the references I have by me are

  • Straubing, Howard (1994). Finite automata, formal logic, and circuit complexity. Progress in Theoretical Computer Science. Basel: Birkhäuser. p. 59. ISBN 3-7643-3719-2. Zbl 0816.68086.
A finite monoid is said to be aperiodic if it contains no non-trivial subgroup
A finite monoid M is aperiodic if and only if there exists k such that for all  ,  
If a monoid M of order m has only trivial subgroups then for all  ,  

Nothing about commutativity. Grillet appears to be talking about a special subclass. Deltahedron (talk) 18:40, 11 October 2012 (UTC)Reply

Additional. On page 58 of Straubling is an example V.2.b of the syntactic monoid of the language of all strings over {a,b} not containing bb as a factor. The multiplication table is clearly not commutative. On page 59 the example is specifically stated to be aperiodic. Deltahedron (talk) 18:50, 11 October 2012 (UTC)Reply
  • Kilp, Mati; Knauer, Ulrich; Mikhalev, Alexander V. (2000). Monoids, Acts and Categories: With Applications to Wreath Products and Graphs. A Handbook for Students and Researchers. De Gruyter Expositions in Mathematics. Vol. 29. Walter de Gruyter. p. 29. ISBN 3110812908. Zbl 0945.20036.
An element s is aperiodic if there exists n such that  
A semigroup S is aperiodic if every s is aperiodic
No mention of being commutative or finite. Deltahedron (talk) 19:23, 11 October 2012 (UTC)Reply

Basically, you're right. The snippets from Grillet are from his chapter on commutative semigroups. He has another chapter on finite semigroups where he says (p. 145):

It looks like someone should have read the whole book... Tijfo098 (talk) 19:29, 11 October 2012 (UTC)Reply

A semigroup is called aperiodic (or combinatorial or group-free) if it possess no non-trivial subgroups
I'll try to find a reference for this being equivalent: so far I only have one for equivalence in the finite case. Deltahedron (talk) 19:33, 11 October 2012 (UTC)Reply
KKM has a characterization theorem for aperiodic monoids on p. 368. It should probably go in the sub-article though. Tijfo098 (talk) 21:06, 11 October 2012 (UTC)Reply

(edit conflict) Looking at the index of Grillet's book, those two pages (119, 145) are the only mentions of aperiodic, and they both seem to be uses of a definition that Grillet probably assumes the reader already knows. His book in general is rather hard to parse... Tijfo098 (talk) 19:35, 11 October 2012 (UTC)Reply

I checked Howie (1995) which is pretty much the standard intro text on semigroups. He does not define or mention "aperiodic", "combinatorial" or "groupfree". So I think we go with the def from KKM, which seems the most general. Tijfo098 (talk) 19:55, 11 October 2012 (UTC)Reply

Ok, I've changed it to use KKM and removed the synonyms for now. Schein here says "Definition 8. A semigroup is called aperiodic (or combinatorial', or group-free') if it possesses no notrivial subgroups." I can't preview the rest of that paper in GB, so I don't know in what context he gives that def. TBD. Tijfo098 (talk) 21:44, 11 October 2012 (UTC)Reply

Grillet's other book on semigroups (the one commutative semigroups) says [1] "A c.s. is group-free when all its subgroups are trivial; these semigroups have also been called (in the finite case) combinatorial and aperiodic. Commutative semigroups in which H is the equality [...] are also called naturally partially ordered and holoids." So it's unclear how general these names are... Tijfo098 (talk) 22:53, 11 October 2012 (UTC)Reply

I realised that the infinite case is actually different. The free semigroup on one element is clearly group-free (no idempotents) but is not aperiodic: that is, it is not true that for every element x there is an n with xn = xn+1 (indeed, this is not true for any x). Clearly aperiodic implies group-free always (the order of any element in any subgroup is 1) and in the finite case group-free implies aperiodic. Deltahedron (talk) 06:24, 12 October 2012 (UTC)Reply

By the way

edit

Someone should fix the crazy WP:OVERLINKing of "commutative", "exponential" and so forth. Tijfo098 (talk) 22:49, 11 October 2012 (UTC)Reply

Also, I don't understand why we need to duplicate entries like "Semigroup with involution (*-semigroup)" followed by "*-semigroup (Semigroup with involution)". Tijfo098 (talk) 00:05, 12 October 2012 (UTC)Reply

π-regular semigroup

edit

This book uses it to mean epigroup. And it's the first GB hit on "π-regular semigroup" I got. Tijfo098 (talk) 05:01, 12 October 2012 (UTC)Reply