Semigroup

From Academic Kids

In mathematics, a semigroup is a set with an associative binary operation on it.

There is some disagreement on whether the empty set should be admitted as a semigroup. Many authors insist that a semigroup should be non-empty, and some even require an identity element. In this article, we shall assume that a semigroup may be empty and need not have an identity.

Examples of semigroups

A semigroup with an identity element is called a monoid. Any semigroup S may be turned into a monoid simply by adjoining an element e not in S and defining es = s = se for all sS ∪ {e}.

Some examples of semigroups:

  • The positive integers with addition.
  • Any monoid, and therefore any group.
  • Any ideal of a ring, with the operation of multiplication. (Thus, any ring, including the integers, rational, real, complex or quaternionic numbers, functions with values in a ring (including sequences), polynomials and matrices.)
  • Any subset of a semigroup which is closed under the semigroup operation.
  • The set of all finite strings over some fixed alphabet Σ, with string concatenation as operation. If the empty string is included, then this is actually a monoid, called the "free monoid over Σ"; if it is excluded, then we have a semigroup, called the "free semigroup over Σ".
  • The bicyclic semigroup.
  • C0-semigroups.
  • Matrix units form a 0-simple semigroup.
  • A semigroup that has a commutative idempotent operation is a semilattice.
  • A transformation semigroup : any finite semigroup S can be represented by transformations of a (state-) set Q of at most |S|+1 states. Each element x of S then maps Q into itself x: QQ and sequence xy is defined by q(xy) = (qx)y for each q in Q. Sequencing clearly is an associative operation, here equivalent to function composition. This representation is basic for any automaton or finite state machine (FSM).

Two semigroups S and T are said to be isomorphic if there is a bijection f : ST with the property that, for any elements a, b in S, f(ab) = f(a)f(b). In this case, T and S are also isomorphic, and for the purposes of semigroup theory, the two semigroups are identical.

Structure of semigroups

A number of concepts are useful for understanding the structure of semigroups, some of which will be described below. For brevity, the semigroup operation will be shown simply by juxtaposition, that is, xy denotes the result of applying the semigroup operation to the ordered pair (xy). If A and B are subsets of some semigroup, then AB denotes the set { ab | a in A and b in B }.

A subset A of a semigroup S is called a subsemigroup if it is closed under the semigroup operation, that is, AA is a subset of A. If A is nonempty then A is called a right ideal if AS is a subset of A, and a left ideal if SA is a subset of A. If A is both a left ideal and a right ideal then it is called an ideal (or a two-sided ideal). The intersection of two ideals is also an ideal, so a semigroup can have at most one minimal ideal. An example of semigroup with no minimal ideal is the set of positive integers under addition. The minimal ideal of a commutative semigroup, when it exists, is a group.

Green's relations are important tools for analysing the ideals of a semigroup, and related notions of structure.

If S is a semigroup, then the intersection of any collection of subsemigroups of S is also a subsemigroup of S. So the subsemigroups of S form a complete lattice. For any subset A of S there is a smallest subsemigroup T of S which contains A, and we say that A generates T. A single element x of S generates the subsemigroup { xn | n is a positive integer }. If this is finite, then x is said to be of finite order, otherwise it is of infinite order. A semigroup is said to be periodic if all of its elements are of finite order. A semigroup generated by a single element is said to be monogenic (or cyclic). If a monogenic semigroup is infinite then it is isomorphic to the semigroup of positive integers with the operation of addition. If it is finite and non-empty, then it must contain at least one idempotent. It follows that every nonempty periodic semigroup has at least one idempotent.

A subsemigroup which is also a group is called a subgroup. There is a close relationship between the subgroups of a semigroup and its idempotents. Each subgroup contains exactly one idempotent, namely the identity element of the subgroup. For each idempotent e of the semigroup there is a unique maximal subgroup containing e. Each maximal subgroup arises in this way, so there is a one-to-one correspondence between idempotents and maximal subgroups. (It should be noted that the use of the term maximal subgroup is different here than it is in group theory. In group theory, a so-called "maximal subgroup" is really a maximal proper subgroup. When considered as a semigroup, a group has only one maximal subgroup, namely itself.)

In the finite case, one can often say rather more. For example, every non-empty finite semigroup is periodic, and has a minimal ideal and at least one idempotent. For more on the structure of finite semigroups, see Krohn-Rhodes theory.

de:Halbgruppe fr:Semigroupe it:semigruppo ja:半群 nl:Algebrasche structuur pl:Półgrupa sl:polgrupa sv:semigrupp zh:半群

Navigation

Academic Kids Menu

  • Art and Cultures
    • Art (http://www.academickids.com/encyclopedia/index.php/Art)
    • Architecture (http://www.academickids.com/encyclopedia/index.php/Architecture)
    • Cultures (http://www.academickids.com/encyclopedia/index.php/Cultures)
    • Music (http://www.academickids.com/encyclopedia/index.php/Music)
    • Musical Instruments (http://academickids.com/encyclopedia/index.php/List_of_musical_instruments)
  • Biographies (http://www.academickids.com/encyclopedia/index.php/Biographies)
  • Clipart (http://www.academickids.com/encyclopedia/index.php/Clipart)
  • Geography (http://www.academickids.com/encyclopedia/index.php/Geography)
    • Countries of the World (http://www.academickids.com/encyclopedia/index.php/Countries)
    • Maps (http://www.academickids.com/encyclopedia/index.php/Maps)
    • Flags (http://www.academickids.com/encyclopedia/index.php/Flags)
    • Continents (http://www.academickids.com/encyclopedia/index.php/Continents)
  • History (http://www.academickids.com/encyclopedia/index.php/History)
    • Ancient Civilizations (http://www.academickids.com/encyclopedia/index.php/Ancient_Civilizations)
    • Industrial Revolution (http://www.academickids.com/encyclopedia/index.php/Industrial_Revolution)
    • Middle Ages (http://www.academickids.com/encyclopedia/index.php/Middle_Ages)
    • Prehistory (http://www.academickids.com/encyclopedia/index.php/Prehistory)
    • Renaissance (http://www.academickids.com/encyclopedia/index.php/Renaissance)
    • Timelines (http://www.academickids.com/encyclopedia/index.php/Timelines)
    • United States (http://www.academickids.com/encyclopedia/index.php/United_States)
    • Wars (http://www.academickids.com/encyclopedia/index.php/Wars)
    • World History (http://www.academickids.com/encyclopedia/index.php/History_of_the_world)
  • Human Body (http://www.academickids.com/encyclopedia/index.php/Human_Body)
  • Mathematics (http://www.academickids.com/encyclopedia/index.php/Mathematics)
  • Reference (http://www.academickids.com/encyclopedia/index.php/Reference)
  • Science (http://www.academickids.com/encyclopedia/index.php/Science)
    • Animals (http://www.academickids.com/encyclopedia/index.php/Animals)
    • Aviation (http://www.academickids.com/encyclopedia/index.php/Aviation)
    • Dinosaurs (http://www.academickids.com/encyclopedia/index.php/Dinosaurs)
    • Earth (http://www.academickids.com/encyclopedia/index.php/Earth)
    • Inventions (http://www.academickids.com/encyclopedia/index.php/Inventions)
    • Physical Science (http://www.academickids.com/encyclopedia/index.php/Physical_Science)
    • Plants (http://www.academickids.com/encyclopedia/index.php/Plants)
    • Scientists (http://www.academickids.com/encyclopedia/index.php/Scientists)
  • Social Studies (http://www.academickids.com/encyclopedia/index.php/Social_Studies)
    • Anthropology (http://www.academickids.com/encyclopedia/index.php/Anthropology)
    • Economics (http://www.academickids.com/encyclopedia/index.php/Economics)
    • Government (http://www.academickids.com/encyclopedia/index.php/Government)
    • Religion (http://www.academickids.com/encyclopedia/index.php/Religion)
    • Holidays (http://www.academickids.com/encyclopedia/index.php/Holidays)
  • Space and Astronomy
    • Solar System (http://www.academickids.com/encyclopedia/index.php/Solar_System)
    • Planets (http://www.academickids.com/encyclopedia/index.php/Planets)
  • Sports (http://www.academickids.com/encyclopedia/index.php/Sports)
  • Timelines (http://www.academickids.com/encyclopedia/index.php/Timelines)
  • Weather (http://www.academickids.com/encyclopedia/index.php/Weather)
  • US States (http://www.academickids.com/encyclopedia/index.php/US_States)

Information

  • Home Page (http://academickids.com/encyclopedia/index.php)
  • Contact Us (http://www.academickids.com/encyclopedia/index.php/Contactus)

  • Clip Art (http://classroomclipart.com)
Toolbox
Personal tools