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.
This might be a natural extension question to ask in the context of Terence Tao’s equational theories project
ReplyDeleteIt's the same commenter as above. There is now a topic for discussion on the lean zulip server in the channel being used for the equational theories project : https://leanprover.zulipchat.com/#narrow/channel/458659-Equational/topic/potentially.20related.20question.20.20about.20constructing.20finite.20s.2E.2E.2E/near/512083006.
DeleteNice argument but can't you get the Theorem simpler if you take all the x_i to be the same? This is the same as a unary DFA. I think that the problem then reduces to finding an x>a such that x^2-a is congruent to x-a mod m for some fixed a and m, which is of course trivial.
ReplyDeleteI think it's still easier: start with an arbitrary element x and consider the sequence x, x^2, x^3, ... Then there are i and j with ii holds (otherwise we "cycle" some times more). Then x^(j-i) should do the job.
DeleteI think that you are using division, which is not allowed. You can avoid it by requiring that j-i is bigger than i. Then it becomes essentially what I wrote.
DeleteSomehow my comment got truncated, yes, wanted to have j-i bigger than i, so we have the same idea.
DeleteIf you're looking for "really nontrivial" finite semigroups without idempotents that are not like an identity, you might want to read about
ReplyDeleteencyclopediaofmath dot org/wiki/Completely-simple_semi-group
> ... contains a primitive idempotent, i.e. a non-zero idempotent that is not an identity for any non-zero idempotent of S.
I believe the simpler statement is using repeated squaring.
ReplyDeleteNote that idempotence at any exponent k >= 2 is sufficient. If a^k = a for some k > 2, multiplying a^(k-2) to the both sides gives a^(2k-2) = a^(k-1), taking b = a^(k-1) gives b^2 = b.
Now, enumerate the sequence x^(2^i) for i >= 0. From the finiteness of the semigroup, one must have x^(2^i) = x^(2^j) for some i < j, giving (x^(2^i))^(2^(j-i)) = x^(2^j), while 2^(j-i) >= 2.
Lets say you find out that x^4 = x^{128}. How does this get you a y such that y*y=y?
Deletex^{248}=x^{124}
DeleteWhat a downer: (1) Ramsey theory is NOT NEEDED for the theorem, and (2) There are no applications of the theorem. Well, I suppose given (1) I don't mind (2) so much. THANKS FOR HELP!
Delete