Author |
Topic: Semigroup (Read 543 times) |
|
ThudnBlunder
Uberpuzzler
The dewdrop slides into the shining Sea
Gender: 
Posts: 4489
|
Let S be a semigroup with an element g such that
(1) [smiley=forall.gif]x[in]S [smiley=exists.gif] y[in]S such that gy = x
(2) [smiley=forall.gif]x[in]S [smiley=exists.gif] y[in]S such that yx = g
Prove that S is a group.
|
| « Last Edit: Jan 4th, 2005, 8:55am by ThudnBlunder » |
 IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
 |
Re: Semigroup
« Reply #1 on: Jan 4th, 2005, 4:45am » |
 Quote  Modify
|
A clarification question: is it assumed that the existence is unique?
In other words, there is only one solution for every x [in] S?
|
|
IP Logged |
|
|
|
ThudnBlunder
Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489
|
|
Re: Semigroup
« Reply #2 on: Jan 4th, 2005, 9:40am » |
Quote Modify
|
on Jan 4th, 2005, 4:45am, Barukh wrote:A clarification question: is it assumed that the existence is unique?
In other words, there is only one solution for every x [in] S? |
|
Nope, that is not assumed. For example, you could have y = x
(The original question states "...there is some y in S...".)
|
|
IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Semigroup
« Reply #3 on: Jan 5th, 2005, 9:22am » |
Quote Modify
|
Hmm, I must admit I didn't get your example... What I asked is this: is it possible that for a given x [in] S there are two disitinct y1, y2 [in] S s.t.
gy1 = x and
gy2 = x
But I will assume it's possible...
|
|
IP Logged |
|
|
|
ThudnBlunder
Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489
|
|
Re: Semigroup
« Reply #4 on: Jan 5th, 2005, 10:31am » |
Quote Modify
|
on Jan 5th, 2005, 9:22am, Barukh wrote: is it possible that for a given x [in] S there are two disitinct y1, y2 [in] S s.t.
gy1 = x and
gy2 = x
But I will assume it's possible... |
|
I see what you mean.
I believe the wording is unambiguous.
[I wonder how an invigilator (proctor) would respond to such a query.] 
|
| « Last Edit: Jan 5th, 2005, 10:36am by ThudnBlunder » |
IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
Obob
Senior Riddler
Gender:
Posts: 489
|
|
Re: Semigroup
« Reply #5 on: Jan 5th, 2005, 12:50pm » |
Quote Modify
|
Under the wording of the problem, yes it is possible that there would be two such elements. However, the conditions of the problem will actually make this impossible since the semigroup is in fact a group.
|
|
IP Logged |
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Semigroup
« Reply #6 on: Jan 5th, 2005, 12:50pm » |
Quote Modify
|
In standard mathematical english, "There is some" only specifies existance, not uniqueness. Just like with "or", by convention, we discard the second, colloquial, meaning. So the original statement (I assume the symbology was added by T&B to clarify) did not require y to be unique.
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Semigroup
« Reply #7 on: Jan 7th, 2005, 6:00pm » |
Quote Modify
|
on Jan 5th, 2005, 12:50pm, Obob wrote:| Under the wording of the problem, yes it is possible that there would be two such elements. However, the conditions of the problem will actually make this impossible since the semigroup is in fact a group. |
|
The point of Barukh's question was whether this uniqueness was part of the "givens" that result in the semigroup being a group. If you could assume uniqueness, then showing that the semigroup was a group would be much easier to accomplish.
Since no-one has posted a solution, and I can't seem to gain any more traction right now, I thought I would try to get things moving by proving that semigroup has a left-identity:
Lemma: [exists]e [in] S such that [forall]x [in] S, ex = x.
Proof: By (2) [exists]e such that eg = g. for each x [in] S, by (1), [exists]y such that gy = x. Therefore ex = egy = gy = x. QED.
Alas, I haven't even been able to show the existance of a right identity yet (if it exists, it is trivial to show that it must be e, and e is the only right or left identity).
|
| « Last Edit: Jan 7th, 2005, 6:08pm by Icarus » |
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Semigroup
« Reply #8 on: Jan 7th, 2005, 7:35pm » |
Quote Modify
|
Okay, here we go:
Lemma: ge = g
Proof: [exists] a such that ae = g by (2). But ge = (ae)e= a(ee) = ae =g.
Lemma: [exists] g' such that gg' = e and [exists] g" such that g"g = e.
Proof: by (1), [exists] g' such that gg' = e. By (2), [exists] g" such that g"(g2) = g. But then g"g = g"ge = g"g2g' = gg' = e.
Lemma: [forall] x, [exists] x" such that x"x = e.
Proof: By (2) [exists] y such that yx = g. Let x" = g"y. Then x"x = g"yx = g"g = e.
From this it follows that a semigroup has such an element g if and only if it possesses a left identity and left inverses. Still not all the way there yet, but a lot closer.
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Semigroup
« Reply #9 on: Jan 8th, 2005, 12:25am » |
Quote Modify
|
I like that, Icarus! Very nice  ! I was missing first 2 lemmas from your last post to proceed. But with what you did, we are actually done: the one-sided identity and inverses are sufficient to define the group. Here we go:
1. [Right Inverse]. [forall]x [in] S, [exists]x’ [in] S s.t. xx’ = e.
Proof: By the existence of left inverses, [exists] x’, x’’ [in] S s.t. x’x = x’’x’ = e. Then x = ex = (x’’x’)x = x’’e, and
xx’ = x’’ex’ = x’’x’ = e
2. [Right Identity]. [forall]x [in] S, xe = x.
Proof: xe = x(ee) = x(x’x’’)e = (xx’)(x’’e) = ex = x.
This was shown for the first time by L.E. Dickson exactly 100 years ago. I am always amazed about such problems. They have the property of using the minimum of algebraic techniques but in order to solve them one often needs an unreachable level of virtuosity.
T&B, is it possible to know the source of the problem (please, do not answer “yes, it is”  )?
|
| « Last Edit: Jan 8th, 2005, 12:27am by Barukh » |
IP Logged |
|
|
|
ThudnBlunder
Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489
|
|
Re: Semigroup
« Reply #10 on: Jan 8th, 2005, 8:46am » |
Quote Modify
|
Quote:| T&B, is it possible to know the source of the problem (please, do not answer “yes, it is” )? |
|
I don't know about the original source, but I found it here.
|
|
IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Semigroup
« Reply #11 on: Jan 8th, 2005, 4:38pm » |
Quote Modify
|
on Jan 8th, 2005, 12:25am, Barukh wrote:| I was missing first 2 lemmas from your last post to proceed. |
|
I was missing them for quite a while too, then I realized the first shortly after posting the left-identity lemma. From there, the right inverse for g was not hard to find, and the left-inverse for everything followed quickly from that. But from left-indentity & left-inverses to finish still required some insight, so "done" is definitely a stretch!
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print