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.
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}
Delete