Please turn on javascript in your browser to play chess.
Posers and Puzzles

Posers and Puzzles

  1. 01 May '08 15:25 / 2 edits
    A "Semigroup" is a set S under an operation * such that,
    - a*(b*c)=(a*b)*c (it is associative) &
    - a*b is contained in S (it is closed).

    NOTE: I'll usually just write a*b as ab from now on.

    Now, let S be commutative. That is, ab=ba for all a and b in S.

    Now, if for all a, b in S there exists x, y in S such that xab=y, prove that S is a group. That is, prove that there already exists an element 1 in S such that a1=1a=a for all a in S, and, further, that there exists a' in S such that a'*a=1. (S contains an identity and inverses).

    Sorry if the question seems rather confusing - just ask if you need clarification...

    EDIT: Sorry for all the "that is"-es. Can't think of anything to replace them though...
  2. Subscriber joe shmo On Vacation
    Strange Egg
    01 May '08 16:32
    Originally posted by Swlabr
    A "Semigroup" is a set S under an operation * such that,
    - a*(b*c)=(a*b)*c (it is associative) &
    - a*b is contained in S (it is closed).

    NOTE: I'll usually just write a*b as ab from now on.

    Now, let S be commutative. That is, ab=ba for all a and b in S.

    Now, if for all a, b in S there exists x, y in S such that xab=y, prove that S is a group. Tha ...[text shortened]...
    EDIT: Sorry for all the "that is"-es. Can't think of anything to replace them though...
    "in other words"
  3. 01 May '08 16:35 / 2 edits
    Originally posted by joe shmo
    "in other words"
    Thanks, although you're 7 minutes to late for an edit...ah well.

    Although I took a paragraph of unnecessary comlicated-ness out which contained a lot of "that is"-es after putting in that comment. 2 is more respectable than what it was...
  4. 02 May '08 01:00 / 1 edit
    Originally posted by Swlabr
    A "Semigroup" is a set S under an operation * such that,
    - a*(b*c)=(a*b)*c (it is associative) &
    - a*b is contained in S (it is closed).

    NOTE: I'll usually just write a*b as ab from now on.

    Now, let S be commutative. That is, ab=ba for all a and b in S.

    Now, if for all a, b in S there exists x, y in S such that xab=y, prove that S is a group. Tha
    EDIT: Sorry for all the "that is"-es. Can't think of anything to replace them though...
    I think something's missing ...

    let S = N \ {0}, that is all positive integers (without zero).

    Then S is clearly a semigroup under multiplication as is it closed and integer multiplication is associative. Also for all a,b in S there are x,y in S such that xab = y. But S is clearly not a group (actually it is a monoid) as no element (apart from 1) has an inverse...
  5. 02 May '08 07:35 / 1 edit
    Originally posted by 3v1l5w1n
    I think something's missing ...

    let S = N \ {0}, that is all positive integers (without zero).

    Then S is clearly a semigroup under multiplication as is it closed and integer multiplication is associative. Also for all a,b in S there are x,y in S such that xab = y. But S is clearly not a group (actually it is a monoid) as no element (apart from 1) has an inverse...
    No, as taking a to be 9, b to be 1 there is no x and y such that xay=b. x*9*y=1. I perhaps did not explain that line clearly, but I think (hope) that that example make it more clear. You pick a and b arbitrarily, but you must get from the a to the b by post and pre multiplying the a, not either the a or the b.
  6. Standard member adam warlock
    Baby Gauss
    02 May '08 08:23 / 2 edits
    Originally posted by Swlabr
    No, as taking a to be 9, b to be 1 there is no x and y such that xay=b. x*9*y=1. I perhaps did not explain that line clearly, but I think (hope) that that example make it more clear. You pick a and b arbitrarily, but you must get from the a to the b by post and pre multiplying the a, not either the a or the b.
    I'm confused now.. Is it supposed to be xab=y as you wrote on your first post or xay=b as you wrote now?

    Edit: Of course it is xay=b and now the problem makes much more sense. So here it goes:

    We have xay=b for every a and b.So this equality is valid in particular for a=b. So we have xay=a, axy=a since the multiplication is associative and commutative. Since the last equation is valid for all values of a (we have made no hypothesis on it) it implies that xy=1. And since x and y belong to S 1 also belongs to S.

    Now for the inverse: xay=b. We have already proven that 1 belongs to the group so we can take in the former equation b=1. We have in that case xay=1, axy=1. So the element xy is what we usually denote by a^-1 and call the inverse. This is valid by the same reasons that were used in the previous reasoning: No hypothesis was made on the nature of a so the equation is valid for all values of a and in that case xy as no choice but to be the inverse.
  7. 02 May '08 13:01
    Originally posted by adam warlock
    I'm confused now.. Is it supposed to be xab=y as you wrote on your first post or xay=b as you wrote now?

    Edit: Of course it is xay=b and now the problem makes much more sense. So here it goes:

    We have xay=b for every a and b.So this equality is valid in particular for a=b. So we have xay=a, axy=a since the multiplication is associative and comm ...[text shortened]... e equation is valid for all values of a and in that case xy as no choice but to be the inverse.
    You have to show that your choice of xy works for all a in S. It is not necessarily true that if xay=a then xby=b.

    In my first post I meant axb=y, although it doesn't actually matter as it is commutative.
  8. Standard member adam warlock
    Baby Gauss
    02 May '08 13:09
    Originally posted by Swlabr
    You have to show that your choice of xy works for all a in S. It is not necessarily true that if xay=a then xby=b.
    I have made no hypothesis on the nature of a other than it being a member of S, so the proof works for all members of S b included. Isn't it so?
  9. 02 May '08 13:22
    Originally posted by adam warlock
    I have made no hypothesis on the nature of a other than it being a member of S, so the proof works for all members of S b included. Isn't it so?
    No, as there exists an x and y fir each a and b - the x and y (could) change with every a and b.
  10. Standard member adam warlock
    Baby Gauss
    02 May '08 13:32
    Originally posted by Swlabr
    No, as there exists an x and y fir each a and b - the x and y (could) change with every a and b.
    Yes I'm aware that x and y can change for every member of S. But that's not the point. What matters is xay=b holds for every member of S, so I can pick the same element of S on both sides and see what are the x and y that holds the equality. Now x and y should change for every member of S, but xy or yx is always the same. And that's the focus of the proof: if x and y belong to S so does xy,yx and it has to be 1.
  11. 02 May '08 13:39
    Originally posted by adam warlock
    Yes I'm aware that x and y can change for every member of S. But that's not the point. What matters is xay=b holds for every member of S, so I can pick the same element of S on both sides and see what are the x and y that holds the equality. Now x and y should change for every member of S, but xy or yx is always the same. And that's the focus of the proof: if x and y belong to S so does xy,yx and it has to be 1.
    but axy=a, bx'y'=b does not imply that x'y'=xy. Are you using that if ax=bx then a=b?
  12. Standard member adam warlock
    Baby Gauss
    02 May '08 13:53
    Originally posted by Swlabr
    but axy=a, bx'y'=b does not imply that x'y'=xy. Are you using that if ax=bx then a=b?
    I think you are too caught up on the letters that we use to describe the situation.

    I will try to be as clear as possible here but if can't make my point across this time I really feel I can't do much better.

    You said that you had a set S which is a minigroup with the property that for each member a,b there is two other members x,y that gives xay=b.
    So if this equality is truely valid for all members of S a and b don't need to be distinct members. So we can take them equal and write xay=a. Now if one writes a,b,c,d,e,f,g or whatever symbol for the current set member one is investigating it doesn't matter. All we need is that a,x,y are members of S and the associative and commutative relations so we can write axy=a. Now here the point is we have made no hypothesis whatsoever on the nature of a other than it is a member of S. So if that equality always holds xy has to be the unity on that S.

    It could be that we were talking about a set of some matrices and on that set of matrices one could have axy=a for some values of a and xy wouldn't ammount to being the unity but if the equality holds for all members of the said set than xy has to be unity.

    That's why one doesn't need to write on equation for and another for b. If that was the case may I ask you why you stop at a and b. Are you saying that S only has those two members? If not why don't you prove there is a unity for every given member of the set? Obviously because one doesn't have to. But I think what you're missing in my proof is the part that I say since I've made no hypothesis on a the equality holds for all members of S (in practice this ammounts to me saying that in my proof a is just a dummy variable) and in that case xy=yx=1.

    Just out of curiosity PM your proof please. I want to see how you did it and I don't want to spoil anyone's fun.