Can a Semigroup with Finitely Many Elements and the Cancellation Law be a Group?

  • Thread starter T-O7
  • Start date
In summary, the conversation discusses a question about semigroups with finitely many elements satisfying the cancellation law. Various approaches are suggested, such as using the pigeon hole principle, demonstrating a map to a general linear group, and using a semi-group action. It is mentioned that the original question is ambiguous and can be interpreted in different ways, but eventually the group is proved to also be a group.
  • #1
T-O7
55
0
Hey,
I'm having trouble on a question about semigroups which looks like it should be fairly straightforward:
If S is a semigroup with finitely many elements satisfying the Cancellation Law (i.e. ab=ac implies b=c and ba=ca implies b=c), then S is a group.

Anyone know how to go about this? :confused:
 
Physics news on Phys.org
  • #2
don't know if this will help, but...

if [tex]a b = a c[/tex] where [tex]a \neq 0[/tex]

[tex]a b - a c = 0[/tex]

[tex]a (b - c) = 0[/tex]

since [tex]a \neq 0[/tex], [tex]b - c = 0[/tex]

and then [tex]b = c[/tex]


I hope this is somewhat useful (and correct :wink:)

Best!
 
  • #3
sadly, dogma, this isn't a question about rings, and so one may not add elements like that, so strictly speaking it is not useful. nor is it correct since even if this were a question about rings it isn't specified that there are no zero divisors.

since the semi group is finite, you can show that the map [tex]f_x: a \to ax[/tex]
induces a map to some general linear group, that shows the semigroup is also a group.

MOre directly, by repeated use of the pigeon hole principle using such maps, you may demonstrate that some f_x is the identity mapping, that inverses exist and you are done.
 
  • #4
matt grime said:
sadly, dogma, this isn't a question about rings, and so one may not add elements like that, so strictly speaking it is not useful. nor is it correct since even if this were a question about rings it isn't specified that there are no zero divisors.

since the semi group is finite, you can show that the map [tex]f_x: a \to ax[/tex]
induces a map to some general linear group, that shows the semigroup is also a group.

MOre directly, by repeated use of the pigeon hole principle using such maps, you may demonstrate that some f_x is the identity mapping, that inverses exist and you are done.

The original question was ambiguous about whether the semigroup contains finitely many elements (a finite semigroup) or the semigroup has a finite subset that satisfys the cancellation law.

An alternative approach would be to use a 'semi-group action':
Let's say the semi-group is [tex]H[/tex] and [tex]|H|=n[/tex] since [tex]H[/tex] is finite. Then left multiplication by elements in [tex]H[/tex] can be considered to be a permutation of the elements of [tex]H[/tex] since semi-groups are closed over multiplication, and the cancellation rule forces the operation to be bijective. This means that [tex]H[/tex] is isomorphic (I think that's the right word) to a subset of the elements of the permutation group of [tex]n[/tex] elements - [tex]S_n[/tex], call it [tex]S[/tex]. Then [tex]H[/tex] must also be isomorphic to the subgroup generated by [tex]S[/tex] since both are generated by multiplication.
 
  • #5
Thanks NateTG, I realized that I had interpreted the ambiguous question incorrectly, and thought it meant "the semigroup has a finite subset that satisfies the cancellation law", when now I'm pretty the question is actually stating "the semigroup contains finitely many elements, ALL of which satisfy the cancellation law".

With the latter interpretation, I used your train of thought and showed that the "cosets" [tex]aS[/tex] of the semigroup [tex]S[/tex] was the semigroup itself ([tex]a\in S[/tex]), and that consequently each element (using the cancellation law too) had an inverse in [tex]S[/tex]. I assumed the semigroup [tex]S[/tex] contains the identity, something that doesn't seem to occur in the usual definition of a semigroup, but is somehow given with it in my textbook.

Thanks everyone. :smile:
 
  • #6
I read it is a semigroup with finitely many elements, and the semigroup has the cancellation property... since the most of the other interpretations are trivially false.
 

FAQ: Can a Semigroup with Finitely Many Elements and the Cancellation Law be a Group?

What is a semigroup?

A semigroup is a mathematical structure consisting of a set and an associative binary operation. This means that the operation is closed under the set and the order in which the operation is performed does not matter. In other words, given three elements a, b, and c in a semigroup, (a * b) * c = a * (b * c).

How is a semigroup different from a group?

A group is a mathematical structure that has the same properties as a semigroup, but also includes the existence of an identity element and inverses for each element. This means that for every element a in a group, there exists an element b such that a * b = b * a = identity element. Semigroups do not necessarily have these properties.

What are some real-world applications of semigroups?

Semigroups have many applications in computer science, specifically in the fields of programming languages and automata theory. They are also used in abstract algebra, particularly in the study of algebraic structures and their properties.

Are semigroups commutative?

No, semigroups are not necessarily commutative. Commutativity means that the order of elements in an operation does not matter, but in a semigroup, this is not always the case. For example, matrix multiplication is an associative operation, but it is not commutative.

Can semigroups be infinite?

Yes, semigroups can be infinite. The size of a semigroup is not limited, as long as it contains a set and an associative binary operation. For example, the set of all positive integers with the operation of addition is a semigroup that is infinite.

Back
Top