Namespaces
Variants
Actions

Difference between revisions of "Semi-group"

From Encyclopedia of Mathematics
Jump to: navigation, search
m (better)
(LaTeX)
Line 3: Line 3:
 
The theory of semi-groups is one of the relatively young branches of algebra. The earliest studies of semi-groups date back to the 1920's and are associated with the name of A.K. Sushkevich, who, in particular, determined the structure of the kernel (the minimal ideal) of a finite semi-group and thus, in particular, the structure of any finite semi-group without proper ideals. This result was later generalized by D. Rees to arbitrary completely-simple semi-groups (cf. [[Completely-simple semi-group|Completely-simple semi-group]]) and refined by the introduction of the concept of matrices over a group (see [[Rees semi-group of matrix type|Rees semi-group of matrix type]]). Rees' theorem, which may be regarded as a sort of analogue of Wedderburn's theorem for simple algebras, is one of the fundamental propositions of the theory of semi-groups. Other early research on semi-groups was done by A. Clifford; one of his first significant achievements was the introduction and investigation of semi-groups which are unions of groups; these semi-groups are now known as completely regular or Clifford semi-groups (cf. [[Clifford semi-group|Clifford semi-group]]). By the end of the 1950's, the theory of semi-groups had become a self-contained branch of modern algebra with a rich store of problems, a broad range of methods and strong links with many fields of mathematics, both properly algebraic (primarily the theory of groups and rings) and others, such as functional analysis (semi-groups of operators on Banach spaces), differential geometry (semi-groups of partial transformations), and the algebraic theory of automata (semi-groups of automata).
 
The theory of semi-groups is one of the relatively young branches of algebra. The earliest studies of semi-groups date back to the 1920's and are associated with the name of A.K. Sushkevich, who, in particular, determined the structure of the kernel (the minimal ideal) of a finite semi-group and thus, in particular, the structure of any finite semi-group without proper ideals. This result was later generalized by D. Rees to arbitrary completely-simple semi-groups (cf. [[Completely-simple semi-group|Completely-simple semi-group]]) and refined by the introduction of the concept of matrices over a group (see [[Rees semi-group of matrix type|Rees semi-group of matrix type]]). Rees' theorem, which may be regarded as a sort of analogue of Wedderburn's theorem for simple algebras, is one of the fundamental propositions of the theory of semi-groups. Other early research on semi-groups was done by A. Clifford; one of his first significant achievements was the introduction and investigation of semi-groups which are unions of groups; these semi-groups are now known as completely regular or Clifford semi-groups (cf. [[Clifford semi-group|Clifford semi-group]]). By the end of the 1950's, the theory of semi-groups had become a self-contained branch of modern algebra with a rich store of problems, a broad range of methods and strong links with many fields of mathematics, both properly algebraic (primarily the theory of groups and rings) and others, such as functional analysis (semi-groups of operators on Banach spaces), differential geometry (semi-groups of partial transformations), and the algebraic theory of automata (semi-groups of automata).
  
There are an extraordinary number of examples of semi-groups. Among these are various sets of numbers which are closed under addition or multiplication; semi-groups of matrices with respect to multiplication; semi-groups of functions with respect to  "pointwise"  multiplication <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s084/s084110/s0841101.png" />, defined by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s084/s084110/s0841102.png" />; semi-groups of sets with respect to intersection or union; etc. The following example is important in the general theory and in some applications. Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s084/s084110/s0841103.png" /> be an arbitrary set, and let an operation on the set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s084/s084110/s0841104.png" /> of all finite sequences of elements of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s084/s084110/s0841105.png" /> be defined by the formula
+
There are an extraordinary number of examples of semi-groups. Among these are various sets of numbers which are closed under addition or multiplication; semi-groups of matrices with respect to multiplication; semi-groups of functions with respect to  "pointwise"  multiplication $*$, defined by $(f*g)(x) = f(x) g(x)$; semi-groups of sets with respect to intersection or union; etc. The following example is important in the general theory and in some applications. Let $X$ be an arbitrary set, and let an operation on the set $F_X$ of all finite sequences of elements of $X$ be defined by the formula
 +
$$
 +
(x_1,\ldots,x_n) * (y_1,\ldots,y_m) = (x_1,\ldots,x_n,y_1,\ldots,y_m)
 +
$$
 +
Then $F_X$ is a semi-group relative to $*$; it is known as the [[Free semi-group|free semi-group]] on $X$. Every semi-group is a homomorphic image of some free semi-group.
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s084/s084110/s0841106.png" /></td> </tr></table>
+
Any set of mappings of an arbitrary set $M$ into itself, which is closed under composition (i.e. the operation of successive application, also known as superposition), is a semi-group with respect to that operation; this is the case, in particular, for the set of all self-mappings of a set $M$, known as the symmetric semi-group on $M$. Many important sets of transformations turn out to be semi-groups, and they often fail to be groups. On the other hand, any semi-group is isomorphic to some semi-group of mappings. Thus, the concept of a semi-group proves to be most suitable for the investigation of mappings in a quite general context, and it is largely through the consideration of mappings that the links between the theory of semi-groups and other fields of mathematics have been realized. In this framework, semi-groups appear very frequently as semi-groups of endomorphisms (see [[Endomorphism semi-group|Endomorphism semi-group]]) of the system being studied: spaces, algebras, graphs, etc. Semi-groups also appear in the theory of partial transformations and binary relations with respect to multiplication.
 
 
Then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s084/s084110/s0841107.png" /> is a semi-group relative to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s084/s084110/s0841108.png" />; it is known as the [[Free semi-group|free semi-group]] on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s084/s084110/s0841109.png" />. Every semi-group is a homomorphic image of some free semi-group.
 
 
 
Any set of mappings of an arbitrary set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s084/s084110/s08411010.png" /> into itself, which is closed under composition (i.e. the operation of successive application, also known as superposition), is a semi-group with respect to that operation; this is the case, in particular, for the set of all self-mappings of a set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s084/s084110/s08411011.png" />, known as the symmetric semi-group on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s084/s084110/s08411012.png" />. Many important sets of transformations turn out to be semi-groups, and they often fail to be groups. On the other hand, any semi-group is isomorphic to some semi-group of mappings. Thus, the concept of a semi-group proves to be most suitable for the investigation of mappings in a quite general context, and it is largely through the consideration of mappings that the links between the theory of semi-groups and other fields of mathematics have been realized. In this framework, semi-groups appear very frequently as semi-groups of endomorphisms (see [[Endomorphism semi-group|Endomorphism semi-group]]) of the system being studied: spaces, algebras, graphs, etc. Semi-groups also appear in the theory of partial transformations and binary relations with respect to multiplication.
 
  
 
As in other algebraic theories, one of the main problems of the theory of semi-groups is the classification of all semi-groups and a description of their structure. This is achieved by imposing various restrictions on the semi-groups under consideration and thereby specifying various types of semi-groups. Such restrictions may be of different kinds. A semi-group may satisfy a fixed system of identities (typical examples are commutative semi-groups and semi-groups of idempotents) or other conditions, expressed by a formula of first-order predicate calculus (examples are semi-groups with a cancellation law and regular semi-groups). The cancellation law and regularity are examples of restrictions which in a sense constitute weak versions of group properties; the introduction of such conditions was particularly popular in the early days of the theory of semi-groups (among the most  "group-like"  types thus defined are right groups (cf. [[Right group|Right group]])). In many cases, however, the classes of semi-groups obtained in this way include semi-groups with properties not at all similar to those of groups (typical examples are semi-groups of idempotents).
 
As in other algebraic theories, one of the main problems of the theory of semi-groups is the classification of all semi-groups and a description of their structure. This is achieved by imposing various restrictions on the semi-groups under consideration and thereby specifying various types of semi-groups. Such restrictions may be of different kinds. A semi-group may satisfy a fixed system of identities (typical examples are commutative semi-groups and semi-groups of idempotents) or other conditions, expressed by a formula of first-order predicate calculus (examples are semi-groups with a cancellation law and regular semi-groups). The cancellation law and regularity are examples of restrictions which in a sense constitute weak versions of group properties; the introduction of such conditions was particularly popular in the early days of the theory of semi-groups (among the most  "group-like"  types thus defined are right groups (cf. [[Right group|Right group]])). In many cases, however, the classes of semi-groups obtained in this way include semi-groups with properties not at all similar to those of groups (typical examples are semi-groups of idempotents).
  
The concept of a [[Regular semi-group|regular semi-group]] arose in analogy with that of a [[Regular ring (in the sense of von Neumann)|regular ring (in the sense of von Neumann)]]. Regular semi-groups are among the most intensively investigated in the theory of semi-groups. They include the following important classes: the multiplicative semi-groups of regular rings (in particular, the semi-group of all matrices of a given order over a division ring), symmetric semi-groups, the semi-groups of all partial transformations of sets, inverse semi-groups, Clifford semi-groups, in particular, semi-groups of idempotents and completely-simple semi-groups, completely <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s084/s084110/s08411013.png" />-simple semi-groups, etc.
+
The concept of a [[Regular semi-group|regular semi-group]] arose in analogy with that of a [[Regular ring (in the sense of von Neumann)|regular ring (in the sense of von Neumann)]]. Regular semi-groups are among the most intensively investigated in the theory of semi-groups. They include the following important classes: the multiplicative semi-groups of regular rings (in particular, the semi-group of all matrices of a given order over a division ring), symmetric semi-groups, the semi-groups of all partial transformations of sets, inverse semi-groups, Clifford semi-groups, in particular, semi-groups of idempotents and completely-simple semi-groups, completely $0$-simple semi-groups, etc.
  
 
Another type of commonly imposed restriction are restrictions on the system of all or some of the sub-semi-groups, in particular the ideals, and also on certain relations on semi-groups, in particular congruences. Such restrictions give rise, for example, to various types of simple semi-groups (cf. [[Simple semi-group|Simple semi-group]]) and various finiteness conditions (see [[Semi-group with a finiteness condition|Semi-group with a finiteness condition]]; [[Periodic semi-group|Periodic semi-group]]; [[Locally finite semi-group|Locally finite semi-group]]; [[Residually-finite semi-group|Residually-finite semi-group]]; [[Minimal ideal|Minimal ideal]]), semi-groups with different types of ideal series and ideal systems (see [[Ideal series|Ideal series]]; [[Nil semi-group|Nil semi-group]]); an essential role in the investigation of many problems of the theory of semi-groups is played by the [[Green equivalence relations|Green equivalence relations]].
 
Another type of commonly imposed restriction are restrictions on the system of all or some of the sub-semi-groups, in particular the ideals, and also on certain relations on semi-groups, in particular congruences. Such restrictions give rise, for example, to various types of simple semi-groups (cf. [[Simple semi-group|Simple semi-group]]) and various finiteness conditions (see [[Semi-group with a finiteness condition|Semi-group with a finiteness condition]]; [[Periodic semi-group|Periodic semi-group]]; [[Locally finite semi-group|Locally finite semi-group]]; [[Residually-finite semi-group|Residually-finite semi-group]]; [[Minimal ideal|Minimal ideal]]), semi-groups with different types of ideal series and ideal systems (see [[Ideal series|Ideal series]]; [[Nil semi-group|Nil semi-group]]); an essential role in the investigation of many problems of the theory of semi-groups is played by the [[Green equivalence relations|Green equivalence relations]].
Line 19: Line 19:
 
The restrictions may relate to generating sets, delineating various types according to the nature of the generating elements (e.g. idempotents; any semi-group can be imbedded in an idempotently-generated semi-group), the number of such elements (finitely-generated semi-groups play an essential part in many investigations), or the interaction of the generators — semi-groups given by defining relations and, in particular, finitely-presented semi-groups (see [[Algorithmic problem|Algorithmic problem]]; [[Semi-group with a finiteness condition|Semi-group with a finiteness condition]]); finally, the types of generating sets may be specified in both of the above respects (see, e.g., [[Bicyclic semi-group|Bicyclic semi-group]]).
 
The restrictions may relate to generating sets, delineating various types according to the nature of the generating elements (e.g. idempotents; any semi-group can be imbedded in an idempotently-generated semi-group), the number of such elements (finitely-generated semi-groups play an essential part in many investigations), or the interaction of the generators — semi-groups given by defining relations and, in particular, finitely-presented semi-groups (see [[Algorithmic problem|Algorithmic problem]]; [[Semi-group with a finiteness condition|Semi-group with a finiteness condition]]); finally, the types of generating sets may be specified in both of the above respects (see, e.g., [[Bicyclic semi-group|Bicyclic semi-group]]).
  
When the structure of semi-groups is considered, much importance is attached to various constructions that reduce the description of the semi-groups in question to that of  "better"  types. Quite frequently, the latter are groups, and the principle of description  "modulo groups"  is common in semi-group-theoretical contexts; in fact, it already appeared in the above-mentioned classical theorem of Rees, according to which any completely <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s084/s084110/s08411014.png" />-simple (completely-simple) semi-group is isomorphic to a regular Rees matrix semi-group over a group with a zero (over a group). Groups take part in the constructions that describe inverse semi-groups, and in those that describe commutative Archimedean semi-groups (cf. [[Archimedean semi-group|Archimedean semi-group]]) with a cancellation law and without idempotents. The description of semi-groups with several finiteness conditions reduces to that of groups with the corresponding conditions.
+
When the structure of semi-groups is considered, much importance is attached to various constructions that reduce the description of the semi-groups in question to that of  "better"  types. Quite frequently, the latter are groups, and the principle of description  "modulo groups"  is common in semi-group-theoretical contexts; in fact, it already appeared in the above-mentioned classical theorem of Rees, according to which any completely $0$-simple (completely-simple) semi-group is isomorphic to a regular Rees matrix semi-group over a group with a zero (over a group). Groups take part in the constructions that describe inverse semi-groups, and in those that describe commutative Archimedean semi-groups (cf. [[Archimedean semi-group|Archimedean semi-group]]) with a cancellation law and without idempotents. The description of semi-groups with several finiteness conditions reduces to that of groups with the corresponding conditions.
  
 
Among the constructions figuring in the description of semi-groups one has both general algebraic ones, such as direct and subdirect products, and specific semi-group-theoretical ones. The latter include, besides the above-mentioned Rees semi-groups, various other constructions, such as that of a band — a partition into sub-semi-groups such that the corresponding equivalence relation is a congruence. Particularly important bands are the commutative bands (or semi-lattices) and matrix (rectangular) bands (see [[Band of semi-groups|Band of semi-groups]]). Many types of semi-groups can be described in terms of bands. Thus, Clifford's theorem for completely-regular semi-groups means, essentially, that these semi-groups are semi-lattices of completely-simple semi-groups; the completely-simple semi-groups are precisely the rectangular bands of groups; the Tamura–Kimura theorem states that any commutative semi-group admits a unique decomposition as a band of Archimedean semi-groups (see [[#References|[3]]]).
 
Among the constructions figuring in the description of semi-groups one has both general algebraic ones, such as direct and subdirect products, and specific semi-group-theoretical ones. The latter include, besides the above-mentioned Rees semi-groups, various other constructions, such as that of a band — a partition into sub-semi-groups such that the corresponding equivalence relation is a congruence. Particularly important bands are the commutative bands (or semi-lattices) and matrix (rectangular) bands (see [[Band of semi-groups|Band of semi-groups]]). Many types of semi-groups can be described in terms of bands. Thus, Clifford's theorem for completely-regular semi-groups means, essentially, that these semi-groups are semi-lattices of completely-simple semi-groups; the completely-simple semi-groups are precisely the rectangular bands of groups; the Tamura–Kimura theorem states that any commutative semi-group admits a unique decomposition as a band of Archimedean semi-groups (see [[#References|[3]]]).
  
As always in algebra, the concept of a homomorphism plays an essential role also in the theory of semi-groups, and hence so does the concept of a congruence. Semi-groups belong to the class of universal algebras whose congruences are not uniquely determined by any canonical coset ( "kernel" ), as is the case, say, for groups and rings. This more complicated situation has led to the development of a fairly extensive branch of the theory of semi-groups, devoted to the investigation of semi-group congruences from various points of view. The problems involved fall mainly into two categories: 1) to investigate some special type of congruence on arbitrary semi-groups; 2) to describe all congruences on some special semi-groups, belonging to some class of importance. The first category includes, in particular, the study of principal congruences (see [[#References|[3]]]), and also of ideal, or Rees, congruences, associated with the two-sided ideals of a semi-group (if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s084/s084110/s08411015.png" /> is an ideal in a semi-group <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s084/s084110/s08411016.png" />, then the corresponding Rees congruence classes are <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s084/s084110/s08411017.png" /> itself and the singletons <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s084/s084110/s08411018.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s084/s084110/s08411019.png" />). Rees congruences are frequently used in various problems and explain the importance of studying ideals; the quotient semi-group modulo a Rees congruence is known as the Rees quotient semi-group modulo the corresponding ideal. Worthy of mentioning among the solved problems in the second category are the description of the congruences on symmetric semi-groups and on completely <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s084/s084110/s08411020.png" />-simple semi-groups, and the far-reaching investigation of congruences on inverse semi-groups; the theory of radicals of semi-groups (cf. [[Radical in a class of semi-groups|Radical in a class of semi-groups]]) has been developed, not without the influence of the analogous branch of ring theory. Thanks to the investigation of homomorphisms of semi-groups into semi-groups with specified  "good"  properties, it has been possible to formulate a branch of the theory dealing with approximations (see [[Separable semi-group|Separable semi-group]]; [[Residually-finite semi-group|Residually-finite semi-group]]).
+
As always in algebra, the concept of a homomorphism plays an essential role also in the theory of semi-groups, and hence so does the concept of a congruence. Semi-groups belong to the class of universal algebras whose congruences are not uniquely determined by any canonical coset ( "kernel" ), as is the case, say, for groups and rings. This more complicated situation has led to the development of a fairly extensive branch of the theory of semi-groups, devoted to the investigation of semi-group congruences from various points of view. The problems involved fall mainly into two categories: 1) to investigate some special type of congruence on arbitrary semi-groups; 2) to describe all congruences on some special semi-groups, belonging to some class of importance. The first category includes, in particular, the study of principal congruences (see [[#References|[3]]]), and also of ideal, or Rees, congruences, associated with the two-sided ideals of a semi-group (if $I$ is an ideal in a semi-group $S$, then the corresponding Rees congruence classes are $I$ itself and the singletons $\{x\}$, $x \in S \setminus I$). Rees congruences are frequently used in various problems and explain the importance of studying ideals; the quotient semi-group modulo a Rees congruence is known as the Rees quotient semi-group modulo the corresponding ideal. Worthy of mentioning among the solved problems in the second category are the description of the congruences on symmetric semi-groups and on completely $0$-simple semi-groups, and the far-reaching investigation of congruences on inverse semi-groups; the theory of radicals of semi-groups (cf. [[Radical in a class of semi-groups|Radical in a class of semi-groups]]) has been developed, not without the influence of the analogous branch of ring theory. Thanks to the investigation of homomorphisms of semi-groups into semi-groups with specified  "good"  properties, it has been possible to formulate a branch of the theory dealing with approximations (see [[Separable semi-group|Separable semi-group]]; [[Residually-finite semi-group|Residually-finite semi-group]]).
  
 
In connection with the theory of sub-semi-groups, one finds a self-contained branch of the theory dealing with the study of lattice properties of semi-groups, i.e. the relationship between the properties of semi-groups and the properties of their semi-group lattice (see [[Lattice|Lattice]]).
 
In connection with the theory of sub-semi-groups, one finds a self-contained branch of the theory dealing with the study of lattice properties of semi-groups, i.e. the relationship between the properties of semi-groups and the properties of their semi-group lattice (see [[Lattice|Lattice]]).
Line 35: Line 35:
 
One of the specific fields in the theory of semi-groups is the study of semi-groups with an additional structure compatible with the multiplication operation. In this context one should mention, above all, the structure of a topological space (see [[Topological semi-group|Topological semi-group]]) and the structure of a partial or total order (see [[Ordered semi-group|Ordered semi-group]]).
 
One of the specific fields in the theory of semi-groups is the study of semi-groups with an additional structure compatible with the multiplication operation. In this context one should mention, above all, the structure of a topological space (see [[Topological semi-group|Topological semi-group]]) and the structure of a partial or total order (see [[Ordered semi-group|Ordered semi-group]]).
  
Theories have also been developed for certain types of generalized semi-groups. These are primarily algebras with one <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s084/s084110/s08411021.png" />-ary operation satisfying a generalized associative law (known as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s084/s084110/s08411023.png" />-associative or <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s084/s084110/s08411025.png" />-semi-group operations). Another variant is that of algebras with one partial associative binary operation (a natural situation of this type arises in the theory of categories).
+
Theories have also been developed for certain types of generalized semi-groups. These are primarily algebras with one $n$-ary operation satisfying a generalized associative law (known as $n$-associative or $n$-semi-group operations). Another variant is that of algebras with one partial associative binary operation (a natural situation of this type arises in the theory of categories).
  
 
====References====
 
====References====
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  A.K. Sushkevich,  "The theory of generalized groups" , Khar'kov-Kiev  (1937)  (In Russian)</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  E.S. Lyapin,  "Semigroups" , Amer. Math. Soc.  (1974)  (Translated from Russian)</TD></TR><TR><TD valign="top">[3]</TD> <TD valign="top">  A.H. Clifford,  G.B. Preston,  "Algebraic theory of semi-groups" , '''1–2''' , Amer. Math. Soc.  (1961–1967)</TD></TR><TR><TD valign="top">[4]</TD> <TD valign="top"> , ''The algebraic theory of automata, languages and semi-groups'' , Moscow  (1975)  (In Russian; translated from English)</TD></TR><TR><TD valign="top">[5]</TD> <TD valign="top">  L. Fuchs,  "Partially ordered algebraic systems" , Pergamon  (1963)</TD></TR><TR><TD valign="top">[6]</TD> <TD valign="top">  ''Itogi Nauk. Algebra, Topol. 1962''  (1963)  pp. 33–58</TD></TR><TR><TD valign="top">[7]</TD> <TD valign="top">  ''Itogi Nauk. Algebra 1964''  (1966)  pp. 161–202</TD></TR><TR><TD valign="top">[8]</TD> <TD valign="top">  ''Itogi Nauk. Algebra, Topol. Geom. 1966''  (1968)  pp. 9–56</TD></TR><TR><TD valign="top">[9]</TD> <TD valign="top">  K.W. Folley (ed.) , ''Semigroups'' , Acad. Press  (1969)</TD></TR><TR><TD valign="top">[10]</TD> <TD valign="top">  J.M. Howie,  "An introduction to semigroup theory" , Acad. Press  (1976)</TD></TR><TR><TD valign="top">[11]</TD> <TD valign="top">  M. Petrich,  "Introduction to semigroups" , C.E. Merrill  (1973)</TD></TR><TR><TD valign="top">[12]</TD> <TD valign="top">  M. Petrich,  "Lectures in semigroups" , Wiley  (1977)</TD></TR><TR><TD valign="top">[13]</TD> <TD valign="top">  L. Redei,  "The theory of finitely generated commutative semigroups" , Pergamon  (1965)  (Translated from German)</TD></TR><TR><TD valign="top">[14]</TD> <TD valign="top">  K.H. Hofmann,  P.S. Mostert,  "Elements of compact semigroups" , C.E. Merrill  (1966)</TD></TR><TR><TD valign="top">[15]</TD> <TD valign="top">  G. Lallement,  "Semi-groups and combinatorial applications" , Wiley  (1979)</TD></TR><TR><TD valign="top">[16]</TD> <TD valign="top">  S. Eilenberg,  "Automata, languages and machines" , '''A-B''' , Acad. Press  (1974–1976)</TD></TR></table>
+
<table>
 +
<TR><TD valign="top">[1]</TD> <TD valign="top">  A.K. Sushkevich,  "The theory of generalized groups" , Khar'kov-Kiev  (1937)  (In Russian)</TD></TR>
 +
<TR><TD valign="top">[2]</TD> <TD valign="top">  E.S. Lyapin,  "Semigroups" , Amer. Math. Soc.  (1974)  (Translated from Russian)</TD></TR>
 +
<TR><TD valign="top">[3]</TD> <TD valign="top">  A.H. Clifford,  G.B. Preston,  "Algebraic theory of semi-groups" , '''1–2''' , Amer. Math. Soc.  (1961–1967)</TD></TR>
 +
<TR><TD valign="top">[4]</TD> <TD valign="top"> , ''The algebraic theory of automata, languages and semi-groups'' , Moscow  (1975)  (In Russian; translated from English)</TD></TR>
 +
<TR><TD valign="top">[5]</TD> <TD valign="top">  L. Fuchs,  "Partially ordered algebraic systems" , Pergamon  (1963)</TD></TR>
 +
<TR><TD valign="top">[6]</TD> <TD valign="top">  ''Itogi Nauk. Algebra, Topol. 1962''  (1963)  pp. 33–58</TD></TR>
 +
<TR><TD valign="top">[7]</TD> <TD valign="top">  ''Itogi Nauk. Algebra 1964''  (1966)  pp. 161–202</TD></TR>
 +
<TR><TD valign="top">[8]</TD> <TD valign="top">  ''Itogi Nauk. Algebra, Topol. Geom. 1966''  (1968)  pp. 9–56</TD></TR>
 +
<TR><TD valign="top">[9]</TD> <TD valign="top">  K.W. Folley (ed.) , ''Semigroups'' , Acad. Press  (1969)</TD></TR>
 +
<TR><TD valign="top">[10]</TD> <TD valign="top">  J.M. Howie,  "An introduction to semigroup theory" , Acad. Press  (1976)</TD></TR>
 +
<TR><TD valign="top">[11]</TD> <TD valign="top">  M. Petrich,  "Introduction to semigroups" , C.E. Merrill  (1973)</TD></TR>
 +
<TR><TD valign="top">[12]</TD> <TD valign="top">  M. Petrich,  "Lectures in semigroups" , Wiley  (1977)</TD></TR>
 +
<TR><TD valign="top">[13]</TD> <TD valign="top">  L. Redei,  "The theory of finitely generated commutative semigroups" , Pergamon  (1965)  (Translated from German)</TD></TR>
 +
<TR><TD valign="top">[14]</TD> <TD valign="top">  K.H. Hofmann,  P.S. Mostert,  "Elements of compact semigroups" , C.E. Merrill  (1966)</TD></TR>
 +
<TR><TD valign="top">[15]</TD> <TD valign="top">  G. Lallement,  "Semi-groups and combinatorial applications" , Wiley  (1979)</TD></TR>
 +
<TR><TD valign="top">[16]</TD> <TD valign="top">  S. Eilenberg,  "Automata, languages and machines" , '''A-B''' , Acad. Press  (1974–1976)</TD></TR>
 +
</table>
  
  
Line 46: Line 63:
  
 
====References====
 
====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  J.F. Berglund,  H.D. Junghenn,  P. Milnes,  "Analysis on semigroups" , Wiley  (1989)</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  J. Hilgert,  K.H. Hofmann,  J.D. Lawson,  "Lie groups, convex cones and semigroups" , Clarendon Press  (1989)</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  K.H. Hofmann (ed.)  J.D. Lawson (ed.)  J.S. Pym (ed.) , ''The analytical and topological theory of semigroups'' , Springer  (1990)</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  W.A.F. Ruppert,  "Compact semitopological semigroups: an intrinsic theory" , ''Lect. notes in math.'' , '''1079''' , Springer  (1984)</TD></TR></table>
+
<table>
 +
<TR><TD valign="top">[a1]</TD> <TD valign="top">  J.F. Berglund,  H.D. Junghenn,  P. Milnes,  "Analysis on semigroups" , Wiley  (1989)</TD></TR>
 +
<TR><TD valign="top">[a2]</TD> <TD valign="top">  J. Hilgert,  K.H. Hofmann,  J.D. Lawson,  "Lie groups, convex cones and semigroups" , Clarendon Press  (1989)</TD></TR>
 +
<TR><TD valign="top">[a3]</TD> <TD valign="top">  K.H. Hofmann (ed.)  J.D. Lawson (ed.)  J.S. Pym (ed.) , ''The analytical and topological theory of semigroups'' , Springer  (1990)</TD></TR>
 +
<TR><TD valign="top">[a4]</TD> <TD valign="top">  W.A.F. Ruppert,  "Compact semitopological semigroups: an intrinsic theory" , ''Lect. notes in math.'' , '''1079''' , Springer  (1984)</TD></TR>
 +
</table>
 +
 
 +
{{TEX|done}}

Revision as of 17:31, 25 October 2014

A set with one binary operation satisfying the law of associativity. A semi-group is a generalization of the concept of a group: only one of the group axioms is retained — associativity; this is the explanation of the term "semi-group" . Semi-groups are called monoids if they have, in addition, an identity element.

The theory of semi-groups is one of the relatively young branches of algebra. The earliest studies of semi-groups date back to the 1920's and are associated with the name of A.K. Sushkevich, who, in particular, determined the structure of the kernel (the minimal ideal) of a finite semi-group and thus, in particular, the structure of any finite semi-group without proper ideals. This result was later generalized by D. Rees to arbitrary completely-simple semi-groups (cf. Completely-simple semi-group) and refined by the introduction of the concept of matrices over a group (see Rees semi-group of matrix type). Rees' theorem, which may be regarded as a sort of analogue of Wedderburn's theorem for simple algebras, is one of the fundamental propositions of the theory of semi-groups. Other early research on semi-groups was done by A. Clifford; one of his first significant achievements was the introduction and investigation of semi-groups which are unions of groups; these semi-groups are now known as completely regular or Clifford semi-groups (cf. Clifford semi-group). By the end of the 1950's, the theory of semi-groups had become a self-contained branch of modern algebra with a rich store of problems, a broad range of methods and strong links with many fields of mathematics, both properly algebraic (primarily the theory of groups and rings) and others, such as functional analysis (semi-groups of operators on Banach spaces), differential geometry (semi-groups of partial transformations), and the algebraic theory of automata (semi-groups of automata).

There are an extraordinary number of examples of semi-groups. Among these are various sets of numbers which are closed under addition or multiplication; semi-groups of matrices with respect to multiplication; semi-groups of functions with respect to "pointwise" multiplication $*$, defined by $(f*g)(x) = f(x) g(x)$; semi-groups of sets with respect to intersection or union; etc. The following example is important in the general theory and in some applications. Let $X$ be an arbitrary set, and let an operation on the set $F_X$ of all finite sequences of elements of $X$ be defined by the formula $$ (x_1,\ldots,x_n) * (y_1,\ldots,y_m) = (x_1,\ldots,x_n,y_1,\ldots,y_m) $$ Then $F_X$ is a semi-group relative to $*$; it is known as the free semi-group on $X$. Every semi-group is a homomorphic image of some free semi-group.

Any set of mappings of an arbitrary set $M$ into itself, which is closed under composition (i.e. the operation of successive application, also known as superposition), is a semi-group with respect to that operation; this is the case, in particular, for the set of all self-mappings of a set $M$, known as the symmetric semi-group on $M$. Many important sets of transformations turn out to be semi-groups, and they often fail to be groups. On the other hand, any semi-group is isomorphic to some semi-group of mappings. Thus, the concept of a semi-group proves to be most suitable for the investigation of mappings in a quite general context, and it is largely through the consideration of mappings that the links between the theory of semi-groups and other fields of mathematics have been realized. In this framework, semi-groups appear very frequently as semi-groups of endomorphisms (see Endomorphism semi-group) of the system being studied: spaces, algebras, graphs, etc. Semi-groups also appear in the theory of partial transformations and binary relations with respect to multiplication.

As in other algebraic theories, one of the main problems of the theory of semi-groups is the classification of all semi-groups and a description of their structure. This is achieved by imposing various restrictions on the semi-groups under consideration and thereby specifying various types of semi-groups. Such restrictions may be of different kinds. A semi-group may satisfy a fixed system of identities (typical examples are commutative semi-groups and semi-groups of idempotents) or other conditions, expressed by a formula of first-order predicate calculus (examples are semi-groups with a cancellation law and regular semi-groups). The cancellation law and regularity are examples of restrictions which in a sense constitute weak versions of group properties; the introduction of such conditions was particularly popular in the early days of the theory of semi-groups (among the most "group-like" types thus defined are right groups (cf. Right group)). In many cases, however, the classes of semi-groups obtained in this way include semi-groups with properties not at all similar to those of groups (typical examples are semi-groups of idempotents).

The concept of a regular semi-group arose in analogy with that of a regular ring (in the sense of von Neumann). Regular semi-groups are among the most intensively investigated in the theory of semi-groups. They include the following important classes: the multiplicative semi-groups of regular rings (in particular, the semi-group of all matrices of a given order over a division ring), symmetric semi-groups, the semi-groups of all partial transformations of sets, inverse semi-groups, Clifford semi-groups, in particular, semi-groups of idempotents and completely-simple semi-groups, completely $0$-simple semi-groups, etc.

Another type of commonly imposed restriction are restrictions on the system of all or some of the sub-semi-groups, in particular the ideals, and also on certain relations on semi-groups, in particular congruences. Such restrictions give rise, for example, to various types of simple semi-groups (cf. Simple semi-group) and various finiteness conditions (see Semi-group with a finiteness condition; Periodic semi-group; Locally finite semi-group; Residually-finite semi-group; Minimal ideal), semi-groups with different types of ideal series and ideal systems (see Ideal series; Nil semi-group); an essential role in the investigation of many problems of the theory of semi-groups is played by the Green equivalence relations.

The restrictions may relate to generating sets, delineating various types according to the nature of the generating elements (e.g. idempotents; any semi-group can be imbedded in an idempotently-generated semi-group), the number of such elements (finitely-generated semi-groups play an essential part in many investigations), or the interaction of the generators — semi-groups given by defining relations and, in particular, finitely-presented semi-groups (see Algorithmic problem; Semi-group with a finiteness condition); finally, the types of generating sets may be specified in both of the above respects (see, e.g., Bicyclic semi-group).

When the structure of semi-groups is considered, much importance is attached to various constructions that reduce the description of the semi-groups in question to that of "better" types. Quite frequently, the latter are groups, and the principle of description "modulo groups" is common in semi-group-theoretical contexts; in fact, it already appeared in the above-mentioned classical theorem of Rees, according to which any completely $0$-simple (completely-simple) semi-group is isomorphic to a regular Rees matrix semi-group over a group with a zero (over a group). Groups take part in the constructions that describe inverse semi-groups, and in those that describe commutative Archimedean semi-groups (cf. Archimedean semi-group) with a cancellation law and without idempotents. The description of semi-groups with several finiteness conditions reduces to that of groups with the corresponding conditions.

Among the constructions figuring in the description of semi-groups one has both general algebraic ones, such as direct and subdirect products, and specific semi-group-theoretical ones. The latter include, besides the above-mentioned Rees semi-groups, various other constructions, such as that of a band — a partition into sub-semi-groups such that the corresponding equivalence relation is a congruence. Particularly important bands are the commutative bands (or semi-lattices) and matrix (rectangular) bands (see Band of semi-groups). Many types of semi-groups can be described in terms of bands. Thus, Clifford's theorem for completely-regular semi-groups means, essentially, that these semi-groups are semi-lattices of completely-simple semi-groups; the completely-simple semi-groups are precisely the rectangular bands of groups; the Tamura–Kimura theorem states that any commutative semi-group admits a unique decomposition as a band of Archimedean semi-groups (see [3]).

As always in algebra, the concept of a homomorphism plays an essential role also in the theory of semi-groups, and hence so does the concept of a congruence. Semi-groups belong to the class of universal algebras whose congruences are not uniquely determined by any canonical coset ( "kernel" ), as is the case, say, for groups and rings. This more complicated situation has led to the development of a fairly extensive branch of the theory of semi-groups, devoted to the investigation of semi-group congruences from various points of view. The problems involved fall mainly into two categories: 1) to investigate some special type of congruence on arbitrary semi-groups; 2) to describe all congruences on some special semi-groups, belonging to some class of importance. The first category includes, in particular, the study of principal congruences (see [3]), and also of ideal, or Rees, congruences, associated with the two-sided ideals of a semi-group (if $I$ is an ideal in a semi-group $S$, then the corresponding Rees congruence classes are $I$ itself and the singletons $\{x\}$, $x \in S \setminus I$). Rees congruences are frequently used in various problems and explain the importance of studying ideals; the quotient semi-group modulo a Rees congruence is known as the Rees quotient semi-group modulo the corresponding ideal. Worthy of mentioning among the solved problems in the second category are the description of the congruences on symmetric semi-groups and on completely $0$-simple semi-groups, and the far-reaching investigation of congruences on inverse semi-groups; the theory of radicals of semi-groups (cf. Radical in a class of semi-groups) has been developed, not without the influence of the analogous branch of ring theory. Thanks to the investigation of homomorphisms of semi-groups into semi-groups with specified "good" properties, it has been possible to formulate a branch of the theory dealing with approximations (see Separable semi-group; Residually-finite semi-group).

In connection with the theory of sub-semi-groups, one finds a self-contained branch of the theory dealing with the study of lattice properties of semi-groups, i.e. the relationship between the properties of semi-groups and the properties of their semi-group lattice (see Lattice).

Another extensive branch of the theory of semi-groups is connected with various imbeddings of semi-groups. The roots of this branch go back to the classical problem of imbedding of semi-groups in groups. For some problems and results in this branch of the theory, see Extension of a semi-group.

Intensive attention has been devoted to varieties of semi-groups; concerning this field see Variety of semi-groups. First steps have been taken towards a theory of quasi-varieties of semi-groups (see Algebraic systems, quasi-variety of) and certain other classes of semi-groups similar in some sense to varieties.

The general theory of semi-groups links up with specific semi-groups in many ways. Among the problems solved are the abstract characterization of various important concrete semi-groups (such as transformation semi-groups; in particular, there are several characterizations of symmetric semi-groups), and several of their abstract properties have been described. For some fundamental results concerning transformation semi-groups see Transformation semi-group. Consideration has been given to isomorphisms and homomorphisms of abstract semi-groups into various specific semi-groups, first and foremost — transformation semi-groups and matrix semi-groups (see Representation of a semi-group). The investigation of homomorphisms of semi-groups into certain semi-groups of numbers, mainly into the multiplicative semi-group of complex numbers, forms the subject of the theory of semi-group characters (cf. Character of a semi-group).

One of the specific fields in the theory of semi-groups is the study of semi-groups with an additional structure compatible with the multiplication operation. In this context one should mention, above all, the structure of a topological space (see Topological semi-group) and the structure of a partial or total order (see Ordered semi-group).

Theories have also been developed for certain types of generalized semi-groups. These are primarily algebras with one $n$-ary operation satisfying a generalized associative law (known as $n$-associative or $n$-semi-group operations). Another variant is that of algebras with one partial associative binary operation (a natural situation of this type arises in the theory of categories).

References

[1] A.K. Sushkevich, "The theory of generalized groups" , Khar'kov-Kiev (1937) (In Russian)
[2] E.S. Lyapin, "Semigroups" , Amer. Math. Soc. (1974) (Translated from Russian)
[3] A.H. Clifford, G.B. Preston, "Algebraic theory of semi-groups" , 1–2 , Amer. Math. Soc. (1961–1967)
[4] , The algebraic theory of automata, languages and semi-groups , Moscow (1975) (In Russian; translated from English)
[5] L. Fuchs, "Partially ordered algebraic systems" , Pergamon (1963)
[6] Itogi Nauk. Algebra, Topol. 1962 (1963) pp. 33–58
[7] Itogi Nauk. Algebra 1964 (1966) pp. 161–202
[8] Itogi Nauk. Algebra, Topol. Geom. 1966 (1968) pp. 9–56
[9] K.W. Folley (ed.) , Semigroups , Acad. Press (1969)
[10] J.M. Howie, "An introduction to semigroup theory" , Acad. Press (1976)
[11] M. Petrich, "Introduction to semigroups" , C.E. Merrill (1973)
[12] M. Petrich, "Lectures in semigroups" , Wiley (1977)
[13] L. Redei, "The theory of finitely generated commutative semigroups" , Pergamon (1965) (Translated from German)
[14] K.H. Hofmann, P.S. Mostert, "Elements of compact semigroups" , C.E. Merrill (1966)
[15] G. Lallement, "Semi-groups and combinatorial applications" , Wiley (1979)
[16] S. Eilenberg, "Automata, languages and machines" , A-B , Acad. Press (1974–1976)


Comments

References

[a1] J.F. Berglund, H.D. Junghenn, P. Milnes, "Analysis on semigroups" , Wiley (1989)
[a2] J. Hilgert, K.H. Hofmann, J.D. Lawson, "Lie groups, convex cones and semigroups" , Clarendon Press (1989)
[a3] K.H. Hofmann (ed.) J.D. Lawson (ed.) J.S. Pym (ed.) , The analytical and topological theory of semigroups , Springer (1990)
[a4] W.A.F. Ruppert, "Compact semitopological semigroups: an intrinsic theory" , Lect. notes in math. , 1079 , Springer (1984)
How to Cite This Entry:
Semi-group. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Semi-group&oldid=31339
This article was adapted from an original article by L.N. Shevrin (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article