I want an application of this application of Ramsey Theory to Semigroups

 I recently read the following theorem

Def: A semigroup is a pair \((G,*)\) where \(G\) is a set and  * is a binary operation on \(G\) such that * is associative. NOTE: we do not require an identity element, we do not require inverses, we do not require commutative. We DO require  that G is closed under *.

Theorem: Let (G,*) be a finite semigroup. There exists x in G such that \(x*x=x\). 

Proof: Let \(x_1,x_2,\ldots,x_r\) be a sequence of elements of G (repetition is allowed---indeed required since we will need \( r  >|G| \).)  Let \(r\) be such that any |G|-coloring of  \(K_r\) has a mono triangle.

Such an \( r\) exists by Ramsey's Theorem \((|G| \) colors, seek mono \(K_3\)). 

Consider the following coloring: for \(i<j\), \(COL(i,j) = x_i* \cdots* x_{j-1} \). 

By the choice of \(r\) there exists  \(i<j<k\) such that 

\(x_i* \cdots * x_{j-1} = x_j *\cdots *x_{k-1} = x_i* \cdots *x_{k-1} \). We call this \(x\).

Since \(x_i  *\cdots * x_{k-1} = x_i *\cdots  *x_{j-1} * x_j \cdots *x_{k-1}\) we have \(x*x=x\).

End of  Proof 

Great! Lets find some semigroups to apply this to. 

1) If G has an identity element \(e\)  then the Theorem is trivial, take \(x=e\). So we seek a semigroup without identity. 

2) Can't we just take a group and remove its identity element? No- then it won't be closed under *.

3) Can't we just take the set of N that are \ge 1, under addition. No good- that's infinite. Note that the theorem does not hold there.

4) Can't we just google. I kept getting infinite examples or being told that I can ADD the identity to a semigroup to get an identity.

5) Can't we just ask AI. I used Claude which gave me a trivial 2-element example. I then asked for an example with more than 10 elements. It DID give me one:

\(G=\{1,\ldots,12\} \)

\(x*y=\min\{x,y,10\}\)

For this semigroup (and similar one) the theorem is trivial since \(\forall x\le 10, x*x=x\).

I asked Claude for an example with more than 10 elements that does not use MIN and it said 

 Due to capacity constraints NO CAN DO.

6) SO what I really want is the following:

Give me a FINITE semigroup G WITHOUT identity for which the statement

                                     is there an \(x\) with \(x*x=x\)  

 is not obviously true- so that the Theorem above is interesting.



 •  0 comments  •  flag
Share on Twitter
Published on April 14, 2025 05:40
No comments have been added yet.


Lance Fortnow's Blog

Lance Fortnow
Lance Fortnow isn't a Goodreads Author (yet), but they do have a blog, so here are some recent posts imported from their feed.
Follow Lance Fortnow's blog with rss.