## semigroup

American Heritage Dictionary: ## sem·i·group

(sĕm'ē-grūp', sĕm'ī-)

n.Mathematics

A set for which there is a binary operation that is closed and associative.Search unanswered questions...Top

Wikipedia on Answers.com: ## Semigroup

Home > Library > Miscellaneous > WikipediaThis article is about the algebraic structure. For applications to differential equations, see C0-semigroup.A

semigroupis an algebraic structure consisting of a setStogether with an associative binary operation. 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 might not exist an inverse; further, there might not exist an identity element.The binary operation of a semigroup is most often denoted multiplicatively: , 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. Semigroups are important in many areas of mathematics because they are the abstract algebraic underpinning of "memoryless" systems: time-dependent systems that start from scratch at each iteration. In applied mathematics, semigroups are fundamental models for linear time-invariant systems. In partial differential equations, a semigroup is associated to any equation whose spatial evolution is independent of time. The theory of finite semigroups has been of particular importance in theoretical computer science since the 1950s because of the natural link between finite semigroups and finite automata. In probability theory, semigroups are associated with Markov processes (Feller 1971).

Contents [hide]## Definition

A semigroup is a set,

S, together with a binary operation "" that satisfies:

- Closure
- For all
a,binS, the result of the operationa·bis also inS.- Associativity
- For all
a,bandcinS, the equation (a·b) ·c=a· (b·c) holds.And in mathematical notation we have:

- and
- .
More compactly, a semigroup is an associative magma.

## Examples of semigroups

- Empty semigroup: the empty set forms a semigroup with the empty function as the binary operation.
- Semigroup with one element: there is essentially just one, the singleton {
a} with operationa·a=a.- Semigroup with two elements: there are five which are essentially different.
- The set of positive integers with addition.
- Square nonnegative matrices with matrix multiplication.
- Any ideal of a ring with the multiplication of the ring.
- The set of all finite strings over a fixed alphabet Σ with concatenation of strings as the semigroup operation — the so-called "free semigroup over Σ". With the empty string included, this semigroup becomes the free monoid over Σ.
- A probability distribution F together with all convolution powers of F, with convolution as operation. This is called a convolution semigroup.
- A monoid is a semigroup with an identity element.
- A group is a monoid in which every element has an inverse element.
## Basic concepts

## Identity and zero

Every semigroup, in fact every magma, has at most one identity element. A semigroup with identity is called a monoid. A semigroup without identity may be embedded into a monoid simply by adjoining an element to and defining for all . The notation S

^{1}denotes a monoid obtained from S by adjoining an identityif necessary(S^{1}= S for a monoid). Thus, every commutative semigroup can be embedded in a group via the Grothendieck group construction.Similary, every magma has at most one absorbing element, which in semigroup theory is called a

zero. Analogous to the above construction, for every semigroup S, one defines S^{0}, a semigroup with 0 that embeds S.## Subsemigroups and ideals

The semigroup operation induces an operation on the collection of its subsets: given subsets

AandBof a semigroup,A*B, written commonly asAB, is the set {ab|ainAandbinB}. In terms of this operations, a subsetAis called

- a
subsemigroupifAAis a subset ofA,- a
right idealifASis a subset ofA, and- a
left idealifSAis a subset ofA.If

Ais both a left ideal and a right ideal then it is called anideal(or atwo-sided ideal).If

Sis a semigroup, then the intersection of any collection of subsemigroups ofSis also a subsemigroup ofS. So the subsemigroups ofSform a complete lattice.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, a set of five equivalence relations that characterise the elements in terms of the principal ideals they generate, are important tools for analysing the ideals of a semigroup and related notions of structure.

## Homomorphisms and congruences

A

semigroup homomorphismis a function that preserves semigroup structure. A functionf:S→Tbetween two semigroups is a homomorphism if the equation

f(ab) =f(a)f(b).holds for all elements

a,binS, i.e. the result is the same when performing the semigroup operation after or before applying the mapf. A semigroup homomorphism is not necessarily a monoid homomorphism.Two semigroups

SandTare said to be isomorphic if there is a bijectionf:S↔Twith the property that, for any elementsa,binS,f(ab) =f(a)f(b). Isomorphic semigroups have the same structure.A

semigroup congruence˜ is an equivalence relation that is compatible with the semigroup operation. That is, a subset that is an equivalence relation and and implies for everyx,y,u,vinS. Like any equivalence relation, a semigroup congruence ˜ induces congruence classes

and the semigroup operation induces a binary operation on the congruence classes:

Because ˜ is a congruence, the set of all congruence classes of ˜ forms a semigroup with , called the

quotient semigrouporfactor semigroup, and denotedS/ ˜. The mapping is a semigroup homomorphism, called thequotient map,canonical surjectionorprojection; if S is a monoid then quotient semigroup is a monoid with identity [1]_{˜}. Conversely, the kernel of any semigroup homomorphism is a semigroup congruence. These results are nothing more than a particularization of the first isomorphism theorem in universal algebra.Every ideal

Iof a semigroup induces a subsemigroup, the Rees factor semigroup via the congruencexρy⇔ eitherx=yor bothxandyare inI.## Structure of semigroups

For any subset

AofSthere is a smallest subsemigroupTofSwhich containsA, and we say thatAgeneratesT. A single elementxofSgenerates the subsemigroup {x^{n}|nis a positive integer }. If this is finite, thenxis said to be offinite order, otherwise it is ofinfinite order. A semigroup is said to beperiodicif 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 idempotenteof the semigroup there is a unique maximal subgroup containinge. Each maximal subgroup arises in this way, so there is a one-to-one correspondence between idempotents and maximal subgroups. Here the termmaximal subgroupdiffers 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.

## Special classes of semigroups

Main article: Special classes of semigroups

- A monoid is a semigroup with identity.
- A subsemigroup is a subset of a semigroup that is closed under the semigroup operation.
- A band is a semigroup the operation of which is idempotent.
- A cancellative semigroup is one having the cancellation property:
^{[1]}a·b=a·cimpliesb=cand similarly forb·a=c·a.- Semilattices: A semigroup whose operation is idempotent and commutative is a semilattice.
- 0-simple semigroups.
- Transformation semigroups: any finite semigroup
Scan be represented by transformations of a (state-) setQof at most |S|+1 states. Each elementxofSthen mapsQinto itselfx:Q→Qand sequencexyis defined byq(xy) = (qx)yfor eachqinQ. Sequencing clearly is an associative operation, here equivalent to function composition. This representation is basic for any automaton or finite state machine (FSM).- The bicyclic semigroup is in fact a monoid, which can be described as the free semigroup on two generators
pandq, under the relationpq= 1.- C
_{0}-semigroups.- Regular semigroups. Every element
xhas at least one inverseysatisfyingxyx=xandyxy=y; the elementsxandyare sometimes called "mutually inverse".- Inverse semigroups are regular semigroups where every element has exactly one inverse. Alternatively, a regular semigroup is inverse if and only if any two idempotents commute.
- Affine semigroup: a semigroup that is isomorphic to a finitely-generated subsemigroup of Z
^{d}. These semigroups have applications to commutative algebra.## Group of fractions

The

group of fractionsof a semigroupSis the groupG=G(S)generated by the elements ofSas generators and all equationsxy=zwhich hold true inSas relations.^{[2]}This has a universal property for morphisms fromSto a group.^{[3]}There is an obvious map fromStoG(S)by sending each element ofSto the corresponding generator.An important question is to characterize those semigroups for which this map is an embedding. This need not always be the case: for example, take

Sto be the semigroup of subsets of some setXwith set-theoretic intersection as the binary operation (this is an example of a semilattice). SinceA.A=Aholds for all elements ofS, this must be true for all generators ofG(S)as well: which is therefore the trivial group. It is clearly necessary for embeddability thatShave the cancellation property. WhenSis commutative this condition is also sufficient^{[4]}and the Grothendieck group of the semigroup provides a construction of the group of fractions. The problem for non-commutative semigroups can be traced to the first substantial paper on semigroups, (Suschkewitsch 1928).^{[5]}Anatoly Maltsev gave necessary and conditions for embeddability in 1937.^{[6]}## Semigroup methods in partial differential equations

Further information: C0-semigroupSemigroup 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) ⊂

Rand timest≥ 0:

Let

Xbe theL^{p}spaceL^{2}((0, 1);R) and letAbe the second-derivative operator with domain

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

X:

On an heuristic level, the solution to this problem "ought" to be

u(t) = exp(tA)u_{0}. However, for a rigorous treatment, a meaning must be given to the exponential oftA. As a function oft, exp(tA) is a semigroup of operators fromXto itself, taking the initial stateu_{0}at timet= 0 to the stateu(t) = exp(tA)u_{0}at timet. The operatorAis said to be the infinitesimal generator of the semigroup.## History

The study of semigroups trailed behind than that of other algebraic structures with more complex axioms such as groups or rings. A number of sources

^{[7]}^{[8]}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'sTheory of Groups of Finite Order.Anton Suschkewitsch obtained 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.^{[8]}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 two-volume monograph on semigroup theory in 1961 and 1967 respectively. In 1970, a new periodical calledSemigroup Forum(currently edited by Springer Verlag) became one of the few mathematical journals devoted entirely to semigroup theory.In recent years researchers in the field have became more specialized with dedicated monographs appearing on important classes of semigroups, like inverse semigroups, as well as monographs focusing on applications in algebraic automata theory, particularly for finite automata, and also in functional analysis.

## Generalizations

Group-like structuresTotality Associativity Identity Inverses Group Yes Yes Yes Yes Monoid Yes Yes Yes No SemigroupYes Yes No No Loop Yes No Yes Yes Quasigroup Yes No No No Magma Yes No No No Groupoid No Yes Yes Yes Category No Yes Yes No If the associativity axiom of a semigroup is dropped, the result is a magma, which is nothing more than a set

Mequipped with a binary operationM×M→M.Generalizing in a different direction, an

(alson-ary semigroup,n-semigrouppolyadic semigroupormultiary semigroup) is a generalization of a semigroup to a setGwith an-ary operation instead of a binary operation.^{[9]}The associative law is generalized as follows: ternary associativity is (abc)de=a(bcd)e=ab(cde), i.e. the stringabcdewith any three adjacent elements bracketed.N-ary associativity is a string of lengthn+ (n−1) with anynadjacent elements bracketed. A 2-ary semigroup is just a semigroup. Further axioms lead to an n-ary group.## See also

- Absorbing element
- Biordered set
- Empty semigroup
- Identity element
- Light's associativity test
- Weak inverse
## Notes

^(Clifford & Preston 1967, p. 3)^B. Farb,Problems on mapping class groups and related topics(Amer. Math. Soc., 2006) page 357. ISBN 0821838385^M. Auslander and D.A. Buchsbaum,Groups, rings, modules(Harper&Row, 1974) page 50. ISBN 006040378X^(Clifford & Preston 1961, p. 34)^G. B. Preston (1990). "Personal reminiscences of the early history of semigroups". http://www.gap-system.org/~history/Extras/Preston_semigroups.html. Retrieved 2009-05-12.^Maltsev, A. (1937), "On the immersion of an algebraic ring into a field",Math. Annalen113: 686–691, doi:10.1007/BF01571659.^Earliest Known Uses of Some of the Words of Mathematics- ^
^{a}^{b}An account of Suschkewitsch's paper by Christopher Hollings^Dudek, W.A. (2001), "On some old problems in n-ary groups",Quasigroups and Related Systems8: 15–36, http://www.quasigroups.eu/contents/contents8.php?m=trzeci## References

- General references

- Howie, John M. (1995),
Fundamentals of Semigroup Theory, Clarendon Press, ISBN 0-19-851194-9 .- Clifford, A. H.; Preston, G. B. (1961),
The algebraic theory of semigroups, volume 1, American Mathematical Society .- Clifford, A. H.; Preston, G. B. (1967),
The algebraic theory of semigroups, volume 2, American Mathematical Society .- Grillet, Pierre Antoine (1995),
Semigroups: an introduction to the structure theory, Marcel Dekker, Inc.

- Specific references

- Feller, William (1971),
An introduction to probability theory and its applications. Vol. II., Second edition, New York: John Wiley & Sons, MR0270403 .- Hille, Einar; Phillips, Ralph S. (1974),
Functional analysis and semi-groups, Providence, R.I.: American Mathematical Society, MR0423094 .- Suschkewitsch, Anton (1928), "Über die endlichen Gruppen ohne das Gesetz der eindeutigen Umkehrbarkeit",
Mathematische Annalen99(1): 30–50, doi:10.1007/BF01459084, MR1512437, ISSN 0025-5831 .- Kantorovitz, Shmuel (2010),
Topics in Operator Semigroups., Boston, MA: Birkhauser.

This entry is from Wikipedia, the leading user-contributed encyclopedia. It may not have been reviewed by professional editors (see full disclaimer)

Related topics:

monoid (mathematics) one-parameter semigroup (mathematics) infinitesimal generator (mathematics)

Help us answer these:

What coextensions of semigroups? What do you mean by structure of a semigroup?

Read more: http://www.answers.com/topic/semigroup#ixzz1Bwwak9Ni

# Semigroup (Answers.com)

by anonymous