wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> putnam exam (pure math) >> Semigroup
        
(Message started by: THUDandBLUNDER on Jan 1^st, 2005, 12:20pm)

Title: Semigroup
Post by THUDandBLUNDER on Jan 1^st, 2005, 12:20pm

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.

Title: Re: Semigroup
Post by Barukh on Jan 4^th, 2005, 4:45am

A clarification question: is it assumed that the existence is unique?

In other words, there is only one solution for every x [in] S?

Title: Re: Semigroup
Post by THUDandBLUNDER on Jan 4^th, 2005, 9:40am

on 01/04/05 at 04:45:15, 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...".)

Title: Re: Semigroup
Post by Barukh on Jan 5^th, 2005, 9:22am

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 y₁, y₂ [in] S s.t.

gy₁ = x and
gy₂ = x

But I will assume it's possible...

Title: Re: Semigroup
Post by THUDandBLUNDER on Jan 5^th, 2005, 10:31am

on 01/05/05 at 09:22:17, Barukh wrote:

is it possible that for a given x [in] S there are two disitinct y₁, y₂ [in] S s.t.

gy₁ = x and
gy₂ = 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.] :P

Title: Re: Semigroup
Post by Obob on Jan 5^th, 2005, 12:50pm

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.

Title: Re: Semigroup
Post by Icarus on Jan 5^th, 2005, 12:50pm

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.

Title: Re: Semigroup
Post by Icarus on Jan 7^th, 2005, 6:00pm

on 01/05/05 at 12:50:06, Obob wrote:

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).

Title: Re: Semigroup
Post by Icarus on Jan 7^th, 2005, 7:35pm

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"(g²) = g. But then g"g = g"ge = g"g²g' = 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.

Title: Re: Semigroup
Post by Barukh on Jan 8^th, 2005, 12:25am

I like that, Icarus! Very nice :D! 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” ;D)?

Title: Re: Semigroup
Post by THUDandBLUNDER on Jan 8^th, 2005, 8:46am

Quote:

T&B, is it possible to know the source of the problem (please, do not answer “yes, it is” ;D)?

I don't know about the original source, but I found it here (http://www.siam.org/journals/problems/downloadfiles/04-002.pdf).

Title: Re: Semigroup
Post by Icarus on Jan 8^th, 2005, 4:38pm

on 01/08/05 at 00:25:06, 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!