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.
Lance Fortnow's Blog
- Lance Fortnow's profile
- 4 followers

