Skip to the Main Content

Note:These pages make extensive use of the latest XHTML and CSS Standards. They ought to look great in any standards-compliant modern browser. Unfortunately, they will probably look horrible in older browsers, like Netscape 4.x and IE 4.x. Moreover, many posts use MathML, which is, currently only supported in Mozilla. My best suggestion (and you will thank me when surfing an ever-increasing number of sites on the web which have been crafted to use the new standards) is to upgrade to the latest version of your browser. If that's not possible, consider moving to the Standards-compliant and open-source Mozilla browser.

June 9, 2015

Semigroup Puzzles

Posted by John Baez

Suppose you have a semigroup: that is, a set with an associative product. Also suppose that

xyx=x x y x = x

for all xx and all yy.

Puzzle 1. Prove that

xyz=xz x y z = x z

for all x,yx,y and zz.

Puzzle 2. Prove that

xx=x x x = x

for all xx.

The proofs I know are not ‘deep’: they involve nothing more than simple equation-pushing. But the results were surprising to me, because they feel like you’re getting something for nothing.

Regarding Puzzle 2: of course xyx=xx y x = x gives xx=xx x = x if you’re in a monoid, since you can take y=1y = 1. But in a monoid, the law xyx=xx y x = x is deadly, since you can take x=1x = 1 and conclude that y=1y = 1 for all yy. So these puzzles are only interesting for semigroups that aren’t monoids.

Posted at June 9, 2015 2:30 PM UTC

TrackBack URL for this Entry:   http://golem.ph.utexas.edu/cgi-bin/MT-3.0/dxy-tb.fcgi/2830

43 Comments & 0 Trackbacks

Re: Semigroup Puzzles

First one: xyz=xyzxz=xzxyz = xyzxz = xz. Second one: xx=xyxx=xxx = xyxx = x.

Really nothing, but what is something?

Posted by: Osman on June 9, 2015 4:27 PM | Permalink | Reply to this

Re: Semigroup Puzzles

Ooh, these are rectangular bands, right?

Well x(yz)x=x, so

xz = (xyzx)z = xy(zxz)=xyz

which takes care of 1.

It looks like 2 can be done without using 1: since the defining idenity implies x=xxx,

xx = (xxx)x = x(xx)x = x

Posted by: Yemon Choi on June 9, 2015 6:35 PM | Permalink | Reply to this

Re: Semigroup Puzzles

Nice! And your “all-x’s” proof that xx=xx x = x is different than Z-TotallyQED’s: shorter but less beautifully symmetrical.

Yes, these are rectangular bands, described on Wikipedia, and I’m the guy who added a proof that the two definitions are equivalent, because it sort of shocked me that they are.

The proof I added, taken from the talk page, is a bit less slick than some here. So, I’ll change it.

The uphill part is showing xyx=xx y x = x implies xyz=xzx y z = x z, and the proof I gave was this:

xyz=(xzx)y(zxz)=(xz)(xyz)(xz)=xz x y z = (x z x) y (z x z) = (x z) (x y z) (x z) = x z

Greg Egan gave a more efficient proof, essentially

xyz=xy(zxz)=(x(yz)x)z=xz x y z = x y (z x z) = (x (y z) x) z = x z

which is really just an annotated version of the one Osman gave:

xyz=xyzxz=xz x y z = x y z x z = x z

This must be the shortest proof.

My big question now is: what are rectangular bands good for, if anything? There’s a simple complete classification of them, shown on Wikipedia, but that’s not quite the same as them being good for something.

Posted by: John Baez on June 10, 2015 4:10 AM | Permalink | Reply to this

Re: Semigroup Puzzles

I should probably wait for Ben Steinberg to turn up and say something informed; but in my limited understanding, based on the days when I used to spend more time messing around with the convolution algebras of semigroups, is that rectangular bands can serve as basic building blocks in a structure theory for general bands. (For other readers: a band is a semigroup in which every element is idempotent.) The structure theorem is due to Petrich, and is explained in Section 4.3 of Howie’s An Introduction To Semigroup Theory.

An interesting application, or manifestation, of some of the general theory comes from the analysis of certain random processes as random walks on special kinds of bands. In these settings you want to know about eigenvalues of certain transition matrices, which is apparently helped or clarified by understanding the structure of the convolution algebra of the band; here one interesting feature is that the convolution algebra modulo its Jacobson radical is commutative. Ken Brown (of group cohomology book fame) has written about this, see

Semigroups, rings, and Markov chains. J. Theoret. Probab. 13 (2000), 871–938.

Semigroup and ring theoretical methods in probability, Representations of finite dimensional algebras and related topics in Lie theory and geometry, 3–26, Fields Inst. Commun., 40, Amer. Math. Soc., Providence, RI, 2004.

Both available from Brown’s webpage.

Posted by: Yemon Choi on June 10, 2015 10:00 AM | Permalink | Reply to this

Re: Semigroup Puzzles

My big question now is: what are rectangular bands good for, if anything?

My little question is: what is “rectangular” about rectangular bands? What is that word supposed to connote?

Posted by: RodMcGuire on June 10, 2015 1:08 PM | Permalink | Reply to this

Re: Semigroup Puzzles

Well, they are bands that come from rectangular arrays!

Take arbitrary non-empty sets II and JJ and make the Cartesian product I×JI\times J a semigroup using the multiplication

(r 1,c 1)(r 2,c 2):=(r 1,c 2) (r_1,c_1)(r_2,c_2):= (r_1,c_2)

That is, you combine two pairs by just using the first term from the first pair and the second term from the second pair. It is easy to check that this gives us a semigroup satisfying the identity described in the original post.

Conversely, once you have a semigroup BB satisfying the identities in the original post, structure theory for semigroups allows you to reconstruct sets II and JJ such that BB is isomorphic to I×JI\times J with the product I’ve defined above. (More specifically: IIRC, you look at the equivalence classes for Green’s relations L and R.)

(I guess there is probably some naturality in the “isomorphism” but I’ll leave that to others.)

Posted by: Yemon Choi on June 10, 2015 1:30 PM | Permalink | Reply to this

Re: Semigroup Puzzles

To me, rectangular bands are interesting because they are models of a kind of computation that can read a single binary digit from memory: xyxy means “read the bit, if it is 0, proceed as xx, if it is 1, proceed as yy”.

It’s a simple theory that illustrates the idea of studying computational effects through algebraic theories. (e.g. I started with this in Instances of computational effects.)

Posted by: Sam on June 10, 2015 2:07 PM | Permalink | Reply to this

Re: Semigroup Puzzles

Thanks, Yemon! This paper is really exciting to me:

• Ken Brown, Semigroups, rings, and Markov chains. J. Theoret. Probab. 13 (2000), 871–938.

Summarizing just a bit, he considers random walks on semigroups, particularly semigroups that arise from Coxeter complexes and hyperplane arrangements.

One nice thing: he takes a semigroup and defines xyx \le y if xy=yx y = y. This gives a partial ordering iff the semigroup is a left regular band, meaning that idempotence

xx=x x x = x

and the graphic identity

xyx=xy x y x = x y

hold.

He seems to be particularly interested in cases where this semigroup is a monoid, in which case idempotence follows from the graphic identity, so we have what Lawvere called a graphic monoid.

When we have a simplicial complex or more general piecewise-linear cell complex, the faces form a poset ordered by inclusion (where we may need to reverse the ordering for compatibility with what I said above), and apparently these are often associated to semigroups via the above procedure.

There seems to be quite a big interesting story here.

Posted by: John Baez on June 10, 2015 3:18 PM | Permalink | Reply to this

Re: Semigroup Puzzles

The Wikipedia page claims now that in every semigroup (not necessarily a band), xyz=xzxyz = xz implies xyx=xxyx = x. But if your only rule yields terms with at least two factors, you cannot derive a general equation with right-hand side xx. I will not edit the Wikipedia page, but this should be corrected.
Posted by: Marc Nardmann on June 11, 2015 4:24 AM | Permalink | Reply to this

Re: Semigroup Puzzles

Fixed.

Posted by: John Baez on June 11, 2015 4:36 AM | Permalink | Reply to this

Re: Semigroup Puzzles

Rectangular bands are the algebras for the monad on Set\mathbf{Set} that arises from the familiar duplicate-product adjunction between Set\mathbf{Set} and Set×Set\mathbf{Set}\times\mathbf{Set}.

In detail: F:SetSet×SetF:\mathbf{Set}\to\mathbf{Set}\times\mathbf{Set} given by F(A)=(A,A)F(A)=(A,A) is a left adjoint to G:Set×SetSetG:\mathbf{Set}\times\mathbf{Set}\to\mathbf{Set} given by G(B 1,B 2)=B 1×B 2G(B_1,B_2)=B_1\times B_2. This adjunction gives us a monad on Set\mathbf{Set}. The category of rectangular bands is the Eilenberg-Moore category for this monad.

I wonder whether the original duplicate-product adjunction is the Kleisli category for this monad.

Posted by: Gejza Jenča on June 13, 2015 9:40 AM | Permalink | Reply to this

Re: Semigroup Puzzles

This is really interesting. Maybe I’m not awake enough, but I’m having trouble seeing why an algebra for the monad you mention is a rectangular band.

Posted by: John Baez on June 14, 2015 2:39 AM | Permalink | Reply to this

Re: Semigroup Puzzles

Hmm, let me check it again:

A rectangular band is a band satisfying xyx=xx y x=x. However, this is equivalent to a band satisfying xyz=xzx y z= x z, I shall use this definition.

The unit η A:AA×A\eta_A:A\to A\times A is given by η A(a)=(a,a)\eta_A(a)=(a,a), the counit ϵ B 1,B 2:(B 1×B 2,B 1×B 2)(B 1,B 2)\epsilon_{B_1,B_2}:(B_1\times B_2,B_1\times B_2)\to(B_1,B_2) is given by ϵ B 1,B 2=(p 1,p 2)\epsilon_{B_1,B_2}=(p_1,p_2), where p 1,p 2p_1,p_2 are the canonical projections p i:B 1×B 2B ip_i:B_1\times B_2\to B_i.

This gives us the endofunctor T(A)=GF(A)=A×AT(A)=G F(A)=A\times A and the multiplication of the monad μ A:(A×A)×(A×A)A×A\mu_A:(A\times A)\times(A\times A)\to A\times A, given by μ A((a 1,a 2),(a 3,a 4))=(a 1,a 4)\mu_A((a_1,a_2),(a_3,a_4))=(a_1,a_4).

Now, let :A×AA\star :A\times A\to A be an algebra for this monad. The triangle axiom gives us the idempotence of \star and the square axiom gives us (a 1a 2)(a 3a 4)=a 1a 4(a_1\star a_2)\star (a_3\star a_4)=a_1\star a_4. Using idempotence of \star , this implies the associativity: x(yz)=(xx)(xz)=xzx\star (y\star z)=(x\star x)\star (x\star z)=x\star z, (xy)z=(xy)(zz)=xz(x\star y)\star z=(x\star y)\star (z\star z)=x\star z and this gives us also the xyz=xzx\star y\star z=x\star z axiom.

The opposite implication is easy: a 1a 4=a 1(a 2a 3)a 4=(a 1a 2)(a 3a 4)a_1\star a_4=a_1\star (a_2\star a_3)\star a_4=(a_1\star a_2)\star (a_3\star a_4).

I think it works.

Posted by: Gejza Jenča on June 14, 2015 11:17 AM | Permalink | Reply to this

Re: Semigroup Puzzles

given by μ A((a1,a2),(a3,a4))=(a1,a4)\mu_A((a1,a2),(a3,a4))=(a1,a4)

This is quite enough if correct, I think (from characterization of rectangular bands).

And yes, this is something :)

Posted by: Osman on June 14, 2015 1:15 PM | Permalink | Reply to this

Re: Semigroup Puzzles

Is the category of rectangular bands equivalent to the category Set×SetSet \times Set, where objects are pairs of sets and morphisms are pairs of functions?

If this were true, we could see why not many people say the Eilenberg–Moore category of the monad coming from the adjunction

×:Set×SetSet \times : Set \times Set \to Set Δ:SetSet×Set \Delta : Set \to Set \times Set

is the category of rectangular bands… even if this is true! They would say it’s the category Set×SetSet \times Set.

Let’s see…

As you know, given any pair of sets L,RL,R we obtain a rectangular band L×RL \times R with product given by

( 1,r 1)( 2,r 2)=( 1,r 2) (\ell_1, r_1) (\ell_2 , r_2) = (\ell_1, \r_2)

So, I believe there’s a functor

F:Set×SetRectBand F : Set \times Set \to RectBand

sending (L,R)(L,R) to the band L×RL \times R.

But there’s also a reverse procedure. Presumably this is the usual proof that every rectangular band is isomorphic to one of the above form, but I learned it from Greg Egan:

Given a rectangular band BB, define an equivalence relation L\sim_L on BB by saying x Lyx \sim_L y iff there exist a,b,cBa,b,c \in B such that

x=abx = a b

y=ac y = a c

Similarly, define an equivalence relation R\sim_R by saying x Ryx \sim_R y iff there exist a,b,cBa,b,c \in B such that

x=ba x = b a

y=ca y = c a

Let L BL_B be the set of L\sim_L-equivalence classes in BB, and let L RL_R be the set of R\sim_R-equivalence classes. Then one can prove there’s a natural isomorphism of rectangular bands

BL B×R B B \cong L_B \times R_B

sending xBx \in B to the pair of equivalence classes ([x] L,[x] R)([x]_{\sim_L}, [x]_{\sim_R}).

This implies that

F:Set×SetRectBand F : Set \times Set \to RectBand

is essentially surjective—a well-known fact. But I suspect it’s actually giving us a functor

G:RectBandSet×Set G : RectBand \to Set \times Set

which together with FF determines an equivalence of categories!

Posted by: John Baez on June 15, 2015 7:46 AM | Permalink | Reply to this

Re: Semigroup Puzzles

This equivalence of categories of rectangular bands with Set x Set is well known in the semigroup community. Notice the category of left zero semigroups (semigroups satisfying xy=x) is equivalent (isomorphic actually) to Set as is the category of right zero semigroups (defined dually). Every rectangular band is isomorphic to a product of a left zero semigroup and a right zero semigroup (unique up to iso). All morphisms are product morphisms. This is the origin of the term rectangular band.

Posted by: Benjamin Steinberg on June 15, 2015 6:04 PM | Permalink | Reply to this

Re: Semigroup Puzzles

Benjamin wrote:

This equivalence of categories of rectangular bands with Set×SetSet \times Set is well known in the semigroup community.

Can you point me to a reference? I want to add this fact to the Wikipedia article Band (mathematics), since to me it completely illuminates the structure of the category of rectangular bands. The Wikipedia article already mentions the classification of rectangular bands, so the only extra touch required is that all homomorphisms between rectangular bands have the obvious form. I don’t want to violate their ban against ‘original research’.

I feel this puts Osman’s discovery in the proper context. I’m guessing that for any category CC with finite products, the Eilenberg–Moore category of the monad

CΔC×C×C C \stackrel{\Delta}{\to} C \times C \stackrel{\times}{\to} C

is just C×CC \times C. So when C=SetC = Set the Eilenberg–Moore category is Set×SetSet \times Set, but this is equivalent to the category of rectangular bands.

A rectangular band is, in this outlook, just a nice algebraic structure you can put on a set that exhibits it as the product of two sets!

(I am not trying to annoy anyone with that word ‘just’. I’m just trying to point out a particular outlook.)

Which raises the puzzle: what’s a similar algebraic structure that we can put on a set that exhibits it as a product of three sets?

Posted by: John Baez on June 16, 2015 3:15 AM | Permalink | Reply to this

Re: Semigroup Puzzles

I don’t think C×C×CC\times C\xrightarrow \times C is usually monadic. e.g. when C=SetC=\mathbf{Set}, it doesn’t reflect isomorphisms, because (A×)(B×)(A\times \emptyset)\cong (B\times \emptyset) for all sets AA and BB.

I think the characterization of rectangular bands requires a focus on non-empty bands and non-empty sets. Correct me if I am wrong.

This is in contrast to the situation with involutive rectangular bands that I mentioned below. The monadicity of that adjunction has been analyzed by Francois Metayer here.

Posted by: Sam Staton on June 16, 2015 11:14 AM | Permalink | Reply to this

Re: Semigroup Puzzles

Sam wrote:

(A×)(B×)(A\times \emptyset)\cong (B\times \emptyset) for all sets AA and BB.

I think the characterization of rectangular bands requires a focus on non-empty bands and non-empty sets.

Oh! You’re right, A×A \times \emptyset and B×B \times \emptyset are always isomorphic as rectangular bands.

So my hoped-for equivalence of the category of rectangular bands with Set×SetSet \times Set, despite being “well known in the semigroup community”, is actually false. But the category of nonempty rectangular bands is equivalent to the category NonemptySet×NonemptySetNonemptySet \times NonemptySet.

Right?

Posted by: John Baez on June 16, 2015 11:44 AM | Permalink | Reply to this

Re: Semigroup Puzzles

You are right of course. In semigroup theory we often forget the empty semigroup. You need nonempty rectangular bands. The category of non empty rectangular bands is isomorphic to the product of two copies of non empty sets.

I’ll try to look if there is an explicit reference. The description of rectangular bands as products is in Clifford and Preston’s book. I doubt that they give the explicit description of morphisms as products restricted to rectangular bands. Rectangular bands are a special case of completely simple semigroups and all morphisms of these are described. When you restrict to rectangular bands it is just a product of maps. I am traveling now so have no references.

Posted by: Benjamin Steinberg on June 16, 2015 1:22 PM | Permalink | Reply to this

Re: Semigroup Puzzles

The equivalence between rectangular bands and the product of the category of nonempty sets with itself is given in non categorical language by Theorem 1.13 and Proposition 4.4.2 in Howie’s book Fundamentals of Semigroup Theory 1995. Note that semigroups are always non-empty in Howie’s book.

Posted by: Benjamin Steinberg on June 19, 2015 5:22 PM | Permalink | Reply to this

Re: Semigroup Puzzles

Thanks! I’ve used this information to improve the Wikipedia section on rectangular bands. A little band aid.

Posted by: John Baez on June 20, 2015 5:47 AM | Permalink | Reply to this

Re: Semigroup Puzzles

Wikipedia: Band (mathematics) currently says:

In categorical language, one can say that the category of nonempty bands is equivalent to Set ×Set \mathrm{Set}_{\ne \emptyset} \times \mathrm{Set}_{\ne \emptyset}, whereSet \mathrm{Set}_{\ne \emptyset} is the category with nonempty sets as objects and functions as morphisms. This implies that not only that every nonempty rectangular band is isomorphic to one coming from a pair of sets, but also these sets are uniquely determined up to a canonical isomorphism, and all homomorphisms between bands come from pairs of functions between sets

I thought these facts were restricted to rectangular bands, not the representation of general bands. In this thread Yemon Choi says:

rectangular bands can serve as basic building blocks in a structure theory for general bands. … The structure theorem is due to Petrich, and is explained in Section 4.3 of Howie’s An Introduction To Semigroup Theory.

A quick google turns up Andreas Distler - “Bands of order at most 10” that says:

The building blocks for bands are two types of bands with additional properties, semilattices and rectangular bands. A classic result by Clifford states that every band is a semilattice of rectangular bands.

A. H. Clifford. Bands of semigroups. Proc. Amer. Math. Soc., 5:499-504, 1954.

None of this general band stuff appears in the WIkipedia article.

Posted by: RodMcGuire on June 20, 2015 7:17 PM | Permalink | Reply to this

Re: Semigroup Puzzles

Yes, this is what I meant in my post a bit a few days ago, about reading a bit from memory.

A related example. Suppose we add to the theory of rectangular bands an involution.

(1)x **=x(xy) *=y *x *x^{**} = x\qquad (xy)^* = {y^*}{x^*}

The corresponding monad is isomorphic to the “state” monad: 2×() 22\times(-)^2.

The state monad arises from the adjunction 2×()() 2:SetSet2\times (-)\dashv(-)^2:\mathbf{Set}\to\mathbf{Set}. This is also monadic.

From the computational point of view, x *x^* is the computation that first flips the bit in memory, and then continues as xx.

Posted by: Sam on June 15, 2015 9:22 PM | Permalink | Reply to this

Re: Semigroup Puzzles

One variable solution for the second one:

x = (x)(xxx)(x) = (xx)(x)(xx) = xx.

Posted by: Z-TotallyQED on June 9, 2015 6:58 PM | Permalink | Reply to this

Re: Semigroup Puzzles

Nice!

Posted by: John Baez on June 10, 2015 1:11 AM | Permalink | Reply to this

Re: Semigroup Puzzles

If you change the universal quantifier of yy to existential and your semigroup is an actual ring, you get the definition of a von Neumann regular ring.

Posted by: Vít Tuček on June 10, 2015 12:06 AM | Permalink | Reply to this

Re: Semigroup Puzzles

I used to like those, in the dimly remembered days when I was focused on functional analysis and the foundations of quantum theory.

Posted by: John Baez on June 10, 2015 4:21 AM | Permalink | Reply to this

Re: Semigroup Puzzles

I guess I arrived too late for the fun. Yemen explained pretty well why they are called rectangular bands. They are important in semigroup theory because they are the building blocks of all bands. Every band is graded by a meet semilattice such that the homogeneous components are rectangular bands.

The most interesting class of bands is the class of left regular bands because intuitively they encode flags in a semilattice.

It turns out that the cells of many natural regular CW complexes including zonotopes, oriented matroids and finite CAT(0) cube complexes have a left regular band structure and their topology is linked to the semigroup structure. Hopefully we will get this on ArXiv soon.

Here is a new puzzle to generalize your old one. A finite semigroup S is called locally trivial if eSe=e for all idempotents e.

  1. Prove that if S is a semigroup of order n, then S is locally trivial iff S^n is a rectangular band.

  2. Prove eSf=ef in a locally trivial semigroup for any idempotents e,f

Locally trivial semigroups are important in semigroup theory because f:S->T a homomorphism of finite semigroups indices a homomorphism of complex algebras with nilpotent kernel if and only if the preimage of each idempotent of T is locally trivial.

Posted by: Benjamin Steinberg on June 10, 2015 7:33 PM | Permalink | Reply to this

Re: Semigroup Puzzles

Benjamin wrote:

It turns out that the cells of many natural regular CW complexes including zonotopes, oriented matroids and finite CAT(0) cube complexes have a left regular band structure and their topology is linked to the semigroup structure. Hopefully we will get this on arXiv soon.

Excellent! This sounds like a nice generalization of some ideas in the paper by Ken Brown that I’m enjoying now. Could you drop a line on this thread when your paper comes out?

Every left regular band gives a poset; is there some general characterization of which posets arise this way?

(Maybe they’re posets with extra structure, not just extra properties: can nonisomorphic left regular bands give isomorphic posets?)

Posted by: John Baez on June 11, 2015 5:14 AM | Permalink | Reply to this

Re: Semigroup Puzzles

Two left regular bands can have isomorphic posets without being isomorphic. The 4 element boolean algebra with meet has the same poset as the left regular band obtained by adding to a 2 element left zero semigroup an identity and a zero.

My colleague Stuart Margolis has a proof that it is NP-hard to determine if a poset comes from a left regular band.

Posted by: Benjamin Steinberg on June 11, 2015 11:07 AM | Permalink | Reply to this

Re: Semigroup Puzzles

Here is the link to the paper on left regular bands, topology and representation theory:

• Stuart Margolis, Franco Saliola and Benjamin Steinberg, Cell complexes, poset topology and the representation theory of algebras arising in algebraic combinatorics and discrete geometry, arXiv:1508.05446.

Now if somebody can explain the Lawvere Hegelian taco I would be grateful.

Posted by: Benjamin Steinberg on August 25, 2015 2:05 AM | Permalink | Reply to this

Re: Semigroup Puzzles

Thanks for the link, Benjamin!

If you email me I can give you the Hegelian taco paper, but I know that’s not the same as explaining it. The Hegelian taco is an 8-element monoid satisfying the graphic identity, but I don’t understand how it arises, and that’s the interesting part.

Posted by: John Baez on August 26, 2015 11:32 AM | Permalink | Reply to this

Re: Semigroup Puzzles

By the way here is a more high level proof of the puzzle rather than an equational proof. But it is the equational proof in disguise.

From xxx=x, it follows that each cyclic subsemigroup is a group. But the only group satisfying your identity is the trivial group so each element is idempotent.

Call your semigroup S. Then xSy=Hom(yS,xS) in the category of right S-sets. In particular Hom(xS,xS)=xSx=x by your identity.

Let C be the full subcategory of right S-sets of the form xS.

Then each endomorphism monoid of C is trivial. There is a morphism between any two objects because xy=xxy is in xSy. Thus C is a connected groupoid with trivial automorphism group. It follows each Hom set is a singleton and so xSy=xy as required.

Puzzle: prove the idempotent splitting of a finite semigroup is a groupoid iff it has a unique 2-sided ideal.

Posted by: Benjamin Steinberg on June 10, 2015 7:58 PM | Permalink | Reply to this

Re: Semigroup Puzzles

I forgot to say that S needs to be von Neumann regular for this puzzle.

Posted by: Benjamin Steinberg on June 10, 2015 8:07 PM | Permalink | Reply to this

Re: Semigroup Puzzles

sorry if this is a dumb question.

when isn’t a semigroup extendible to a monoid?

Or, are their semigroups that don’t extend in some, usually obvious way to monoids? Looking at the examples on Wikipedia Entry most either are monoids already or you can add an identity to make them one.

Posted by: Rob MacDonald on June 11, 2015 8:50 PM | Permalink | Reply to this

Re: Semigroup Puzzles

You can always take a semigroup SS and throw in an extra element 11 serving as an identity to obtain a monoid S{1}S \cup \{1\}. You can do this even when your semigroup was already a monoid, but then the original identity element will no longer be the identity.

This process is called taking the ‘free monoid on a semigroup’. It gives a functor

F:SemigroupMonoid F: Semigroup \to Monoid

which is left adjoint to the forgetful functor

U:MonoidSemigroup U: Monoid \to Semigroup

that takes a monoid and treats it as a mere semigroup.

One big difference between monoids and semigroups is that monoid homomorphisms need to preserve the identity element while semigroup homomorphisms don’t, even when they’re going between semigroups that happen to have identities!

So, not every semigroup homomorphism f:U(M)U(M)f : U(M) \to U(M') comes from a monoid homomorphism from MM to MM'. In short, the functor UU is not full.

Posted by: John Baez on June 12, 2015 3:05 AM | Permalink | Reply to this

Re: Semigroup Puzzles

However, an isomorphism of semigroups is automatically an isomorphism of monoids; i.e. the functor UU is pseudomonic. Some fancy language for that is that an identity element is “property-like structure” on a semigroup — perhaps the simplest nontrivial example of property-like structure.

Posted by: Mike Shulman on June 12, 2015 5:35 AM | Permalink | Reply to this

Re: Semigroup Puzzles

You can adjoin an element 11 to your semigroup SS, along with equations 1x=x=x11x=x=x1 for each xSx \in S, obtaining a monoid S[1]S[1]. This is true for the same reason that, given any monoid MM, you can adjoin elements m 1m^{-1} for each mMm \in M, along with relations mm 1=1=m 1mm m^{-1} = 1 = m^{-1}m to obtain a group M[M 1]M[M^{-1}]. It’s just pure algebraic fiat. And there will be canonical homomorphisms SS[1]S \to S[1], MM[M1]M \to M[M{-1}].

But I think maybe Rob MacDonald wanted to known whether these homomorphisms are injective, so that we’re really “extending” the gadget we started with. For that, we need to do a bit more work. For example, MM[M 1]M \to M[M^{-1}] will be injective only if MM is cancellative, satisfying xy=xzy=zxy = xz \implies y = z (I think this condition is also sufficient?). It isn’t injective when MM is, say, the monoid of functions on the 2-element set.

In the case of adjoining a unit, though, SS[1]S \to S[1] is always injective, because the relations 1x=x=x11x = x = x1 fully specify a multiplication on the disjoint union S⨿{1}S \amalg \{1\} (using the original multiplication on SS itself), and a case-by-case check reveals that the multiplication is associative as long as the original multiplication was (for example, check that 1(x1)=1x=x=x1=(1x)11 (x 1) = 1x = x = x1 = (1x)1 for xSx \in S and 1(xy)=xy=(1x)y1(xy) =xy = (1x)y for x,ySx,y \in S, and …).

Is there a slick way to see this that avoids a case-by-case analysis?

Posted by: Tim Campion on June 12, 2015 1:11 PM | Permalink | Reply to this

Re: Semigroup Puzzles

Is there a slick way to see this that avoids a case-by-case analysis?

I’ll interpret “this” to mean “the canonical map SS[1]S \to S[1] is injective”. I don’t have an answer, but here’s a start.

This canonical map is the SS-component η S\eta_S of the unit of the adjunction that John mentioned. By its universal property, η S\eta_S is injective if and only if the following holds: for all distinct s,tSs, t \in S, there exist a monoid MM and a semigroup homomorphism f:SMf: S \to M such that f(s)f(t)f(s) \neq f(t). (To see this, draw a triangle involving η S\eta_S, ff, and the induced monoid homomorphism S[1]MS[1] \to M.)

How would you construct such an MM and ff? Well, at present I can’t think of any easier way than taking M=S[1]M = S[1] and f=η Sf = \eta_S. But maybe someone else can.

The same argument is useful in other contexts. For example, consider the adjunction between sets and groups. Why is the unit map from a set SS to the free group on SS always injective? It’s because for any distinct s,tSs, t \in S, there exist a group GG and an injection SGS \to G. In other words, it’s because there exists a group with more than one element.

Similarly, whenever you have an algebraic theory that’s nontrivial in the sense of having at least one algebra with at least two elements, the free algebra on a set SS always contains SS as a subset.

(There are two algebraic theories that are trivial in the sense above. One is presented by no operations and the equation x=yx = y; its algebras are just the one-element set and the empty set. The other is presented by a single constant cc and the equation x=cx = c; its only algebra is the one-element set. In neither case are the components of the unit map injective.)

Posted by: Tom Leinster on June 12, 2015 1:40 PM | Permalink | Reply to this

Re: Semigroup Puzzles

Tom,

Let S act on the right of the set S U 1 by having S act on itself by multiplication and 1s=s. The associative law easily gives this is a mapping of S into the monoid of self maps on the set S U 1. This is obviously injective and so S embeds in a monoid and hence in its universal monoid

Posted by: Benjamin Steinberg on June 12, 2015 2:03 PM | Permalink | Reply to this

Re: Semigroup Puzzles

Puzzle 1. xyz = (xyz)(xz)(xyz) = (xyzx)(zxyz) = xz

  1. xxx = x. By Puzzle 1, xxx = xx. So, xx = x.
Posted by: S Burchette on June 11, 2015 2:44 AM | Permalink | Reply to this

Re: Semigroup Puzzles

I hope this is not wildly off topic, but some of the discussion seems to have veered close to the theory M(2). Recall that M(n) is the algebraic theory whose models and homomorphisms are n-th powers of sets and functions. You can easily write down a presentation in terms of n^2 n-ary operations. If you tensor M(n) with an algebraic theory A you get, of course, the theory M(n)(A) of n-powers of A-models. When A is (the algebraic theory of left modules of) a ring, we are back with nxn matrices over A.

To change subject slightly. I can remember seeing (in the Mathematical Gazette?) when I was about eleven years old an article about an algebraic theory generated by a binary operation (a,b) => ab, with the single law abcab = c. Brackets are to be taken from the left, so abc is (ab)c and so on. It went on to deduce that u = xx is independent of x and that if we define a*b = uab then u is an identity element for *, which defines a group (abelian?) structure (presuming the set of elements is nonempty). The devil is that in my dotage I forgotten the contortions necessary to show this. Maybe I am dreaming. Anyway I leave this as a frivolous conundrum for those who are fed up with the crossword or the sudoku.

Posted by: Gavin Wraith on June 17, 2015 12:18 PM | Permalink | Reply to this

Post a New Comment