Semigroup

Semigroup
This article is licensed under the GNU Free Documentation License. It uses material from the Wikipedia article "Semigroup".

In mathematics, a semigroup is an algebraic structure consisting of a nonempty set S together with an associative binary operation which satisfies closure and associative law. In other words, a semigroup is an associative magma. The terminology is derived from the anterior notion of a group. A semigroup differs from a group in that for each of its elements there may not exist an inverse; further, there may not exist an identity element.

The binary operation of a semigroup is most often denoted multiplicatively: $x\cdot y$ , or simply xy, denotes the result of applying the semigroup operation to the ordered pair (x, y).

The formal study of semigroups began in the early 20th century. Since the 1950s, the theory of finite semigroups has been of particular importance in theoretical computer science because of the natural link between finite semigroups and finite automata.

content

1 Formal definition
2 Semigroup homomorphisms
3 Examples of semigroups
4 Special classes of semigroups
5 Structure of semigroups
6 Semigroup methods in partial differential equations
7 History
8 See also
9 References
10 Notes

Formal definition

A semigroup consists of an ordered pair $(S,\cdot_S)$ , where S is a nonempty set and $\cdot_S$ is a function $\cdot_S: S \times S \rightarrow S$ . For convenience, the application of the function $\cdot_S$ to the pair $(x, y)$ is denoted as $x \cdot_S y$ or $x \cdot y$ . The operation is required to be associative: for any $x,y,z \in S$ we must have $(x \cdot y) \cdot z = x \cdot (y \cdot z)$ . As is common practice in abstract algebra, one usually refers to the pair $(S,\cdot_S)$ as S when the operation used is clear from the context.

Let S be a semigroup. An element $e \in S$ , if it exists, such that ex=xe=x for all $x \in S$ is called an identity element in S. A semigroup with an identity element is called a monoid.

A semigroup S is commutative if xy=yx for all $x,y \in S$ .

Some authors do not require semigroups to be non-empty. Others use the term semigroup synonymously with monoid. In the remainder of this article, the term semigroup will be used in the widest sense: it could be empty and it need not include an identity element.

Semigroup homomorphisms

A homomorphism between two semigroups (S,*) and (S′,•) is a function f : S → S′ such that

f(x*y) = f(x)•f(y) for all x, y in S.

Any semigroup S may be embedded into a monoid (generally denoted as $S 1$ ) simply by adjoining an element e (not in S) to S and defining es = s = se for all s ∈ S ∪ {e}.

A commutative semigroup can be embedded into a group if and only if it has the cancellation property.

Examples of semigroups

Any monoid, and therefore any group.
The set of positive integers with addition.
Square nonnegative matrices with matrix multiplication.
Any ideal of a ring with the given multiplication in the ring. Thus any ring including the integers, rational, real, complex or quaternionic numbers, functions with values in a ring (including sequences), polynomials and matrices.
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 Σ".

Special classes of semigroups

Monoids
Commutative semigroups
Subsemigroups: subset of a semigroup closed under the semigroup operation.
Bands: a semigroup whose operation is idempotent is a band.
Semilattices: A semigroup whose operation is idempotent and commutative is a semilattice.
0-simple semigroups.
Transformation semigroups: 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: Q → Q 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).
Bicyclic semigroups.
C₀-semigroups.
Regular semigroups.
Inverse semigroups.
Affine semigroup: a semigroup that is isomorphic to a finitely-generated subsemigroup of Z^d. These semigroups have applications to commutative algebra.

Structure of semigroups

This section sets out concepts useful for understanding the structure of semigroups. Two semigroups S and T are said to be isomorphic if there is a bijection f : S ↔ T 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.

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. Let A be nonempty. 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 { xⁿ | 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 nonempty, 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. Here the term maximal subgroup differs from its standard use in group theory.

More can often be said when the order is finite. For example, every nonempty 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.

Semigroup methods in partial differential equations

Semigroup theory can be used to study some problems in the field of partial differential equations. Roughly speaking, the semigroup approach is to regard a time-dependent partial differential equation as an ordinary differential equation on a function space. For example, consider the following initial/boundary value problem for the heat equation on the spatial interval (0, 1) ⊂ R and times t ≥ 0:

$\begin{cases} \partial_{t} u(t, x) = \partial_{x}^{2} u(t, x), & x \in (0, 1), t > 0; \\ u(t, x) = 0, & x \in \{ 0, 1 \}, t > 0; \\ u(t, x) = u_{0} (x), & x \in (0, 1), t = 0. \end{cases}$

Let X be the L^p space L²((0, 1); R) and let A be the second-derivative operator with domain

$D(A) = \big\{ u \in H^{2} ((0, 1); \mathbf{R}) \big| u(0) = u(1) = 0 \big\}.$

Then the above initial/boundary value problem can be interpreted as an initial value problem for an ordinary differential equation on the space X:

$\begin{cases} \dot{u}(t) = A u (t); \\ u(0) = u_{0}. \end{cases}$

On an heuristic level, the solution to this problem "ought" to be u(t) = exp(tA)u₀. However, for a rigorous treatment, a meaning must be given to the exponential of tA. As a function of t, exp(tA) is a semigroup of operators from X to itself, taking the initial state u₀ at time t = 0 to the state u(t) = exp(tA)u₀ at time t. The operator A is said to be the infinitesimal generator of the semigroup.

History

The formal study of semigroups came somewhat later than that of other algebraic structures such as groups or rings in the mid 19th century. A number of sources¹² attribute the first use of the term (in French) to J.-A. de Séguier in Élements de la Théorie des Groupes Abstraits (Elements of the Theory of Abstract Groups) in 1904. The term is used in English in 1908 in Harold Hinton's Theory of Groups of Finite Order. In 1970, a new periodical called Semigroup Forum (currently edited by Springer Verlag) became one of the rare mathematical journals devoted entirely to semigroup theory.

Anton Suschkewitsch is often credited with obtaining the first non-trivial results about semigroups. His 1928 paper Über die endlichen Gruppen ohne das Gesetz der eindeutigen Umkehrbarkeit (On finite groups without the rule of unique invertibility) determined the structure of finite simple semigroups and showed that the minimal ideal (or Green's relations J-class) of a finite semigroup is simple². From that point on, the foundations of semigroup theory were further laid by David Rees, James Alexander Green, Evgenii Sergeevich Lyapin, Alfred H. Clifford and Gordon Preston. The latter two published a monograph on semigroup theory in 1961.

The theory of finite semigroups is arguably more developed than its infinite counterpart. This stems particularly from the notion of syntactic semigroup and the ensuing links between pseudo-varieties of semigroups and so-called varieties of formal languages which have proved particularly fruitful in finite automata theory³.

References

John M. Howie is the author of two books, published twenty years apart, which are often cited as a basic reference in the mathematical community.
- Howie, John M. (1995). Fundamentals of Semigroup Theory. Clarendon Press. ISBN 0-19-851194-9.
- Howie, John M. (1976). Introduction to Semigroup Theory. Academic Press. ISBN 0-12-754633-2.
Two volumes of Samuel Eilenberg have also been a common reference for the applications of semigroup theory in theoretical computer science.
- Eilenberg, Samuel (1973). Automata, Languages, and Machines (Vol.A). Academic Press. ISBN 0-12-234001-9.
- Eilenberg, Samuel (1976). Automata, Languages, and Machines (Vol.B). Academic Press. ISBN 0-12-234002-7.
The algebraic theory of semigroups, A. H. Clifford and G. B. Preston. American Mathematical Society, 1961 (volume 1), 1967 (volume 2).
Semigroups: an introduction to the structure theory, Pierre Antoine Grillet. Marcel Dekker, Inc., 1995.
Semigroup Forum is the best-known periodical devoted specifically to the subject of semigroups.

Notes

^ http://members.aol.com/jeff570/s.html Earliest Known Uses of Some of the Words of Mathematics
^ ^a ^b http://uk.geocities.com/cdhollings/suschkewitsch3.pdf An account of Suschkewitsch's paper by Christopher Hollings
^ Varieties of Formal Languages, J.É. Pin, Plenum Press, 1986.

Your Ad Here

Contents