Half group

In mathematics , a semigroup is an algebraic structure consisting of a set with an inner two-digit link that complies with the associative law (i.e. an associative magma ). It is a generalization of a group .

Definitions

Half group

A semigroup consists of a set and an inner two-digit link ${\displaystyle {\boldsymbol {S}}=(S,*)}$ ${\displaystyle S}$

${\displaystyle *\colon \,S\times S\to S,\,(a,b)\mapsto a*b,}$

which is associative, d. H. for all true ${\displaystyle a,b,c\in S}$

${\displaystyle a*(b*c)=(a*b)*c}$.

A semigroup therefore differs from a group in that the two-digit link does not have to be invertible and a neutral element does not necessarily exist.

It is not assumed that it is not empty. The empty set also forms a semigroup with respect to the empty link ${\displaystyle S}$ ${\displaystyle \emptyset }$

${\displaystyle \emptyset \colon \,\emptyset \times \emptyset \rightarrow \emptyset }$,

called the empty or trivial semigroup . ${\displaystyle (\emptyset ,\emptyset )}$

Notes on the notation

The symbol is often used for the link ; one then speaks of a multiplicatively written semigroup. As is common with ordinary multiplication , the painting point can be left out in many situations . ${\displaystyle *}$ ${\displaystyle \cdot }$ ${\displaystyle \cdot }$

A semigroup can also be noted additively by using the symbol for the link , which is usually only done for commutative semigroups. ${\displaystyle *}$ ${\displaystyle +}$

With the validity of the associative law, a simplified notation without brackets can be introduced, because if

${\displaystyle a_{1}*\cdots *a_{n}:=(a_{1}*\cdots *a_{n-1})*a_{n}}$for each , ${\displaystyle n\geq 3}$

then all the links of that differ only in the brackets from have the same result ( general associative law , proof: complete induction over ), so one can just write for each of these links . ${\displaystyle a_{1},\ldots ,a_{n}}$ ${\displaystyle a_{1}*\cdots *a_{n}}$ ${\displaystyle n}$ ${\displaystyle a_{1}*\cdots *a_{n}}$

Subgroup

Be a semi-group and . If a semigroup is then ( here is a simplified notation for the restriction of to ), it is called a sub-subgroup of . Then and only then is a subgroup of if is closed with respect to , i. H. it applies ${\displaystyle {\boldsymbol {S}}=(S,*)}$ ${\displaystyle U\subseteq S}$ ${\displaystyle {\boldsymbol {U}}:=(U,*)}$ ${\displaystyle *}$ ${\displaystyle *|_{U\times U}}$ ${\displaystyle *}$ ${\displaystyle U\times U}$ ${\displaystyle {\boldsymbol {U}}}$ ${\displaystyle {\boldsymbol {S}}}$ ${\displaystyle {\boldsymbol {U}}}$ ${\displaystyle {\boldsymbol {S}}}$ ${\displaystyle U}$ ${\displaystyle *}$

${\displaystyle a*b\in U}$for everyone . ${\displaystyle a,b\in U}$

${\displaystyle {\boldsymbol {S}}}$is then also called the upper half group of . ${\displaystyle {\boldsymbol {U}}}$

Factor half group

If there is a semigroup and an equivalence relation compatible with , then the factor amount forms from to together with the through ${\displaystyle {\boldsymbol {S}}=(S,*)}$ ${\displaystyle R\subseteq S\times S}$ ${\displaystyle *}$ ${\displaystyle S}$ ${\displaystyle S/R}$ ${\displaystyle S}$ ${\displaystyle R}$

${\displaystyle [a]{\;*}_{R\;}[b]:=[a*b]}$

defined link also a semi-group. This half group is called the factor half group or quotient half group from to . The link is called the link induced by the equivalence relation or the canonical link of the factor half -group. ${\displaystyle {\;*}_{R\;}}$ ${\displaystyle {\boldsymbol {S}}/R=\left(S/R,*_{R}\right)}$ ${\displaystyle {\boldsymbol {S}}}$ ${\displaystyle R}$ ${\displaystyle {\;*}_{R\;}}$

Semigroup homomorphism

A mapping between the carrier sets of two semigroups and is called semigroup homomorphism if: ${\displaystyle \varphi \colon \,S_{1}\rightarrow S_{2}}$ ${\displaystyle {\boldsymbol {S}}_{1}=(S_{1},*_{1})}$ ${\displaystyle {\boldsymbol {S}}_{2}=(S_{2},*_{2})}$

${\displaystyle \operatorname {\varphi } (a*_{1}b)=\operatorname {\varphi } (a)*_{2}\operatorname {\varphi } (b)}$

for everyone . If it is clear from the context that there is a homomorphism between semigroups, the addition of semigroups is omitted. Depending on whether it is injective or surjective or both, the homomorphism is called mono-, epi- or isomorphism. If so, the homomorphism is called endomorphism of and the isomorphism is called automorphism of . ${\displaystyle a,b\in S_{1}}$ ${\displaystyle \varphi }$ ${\displaystyle \varphi }$ ${\displaystyle S_{1}=S_{2},}$ ${\displaystyle \varphi }$ ${\displaystyle {\boldsymbol {S}}_{1}}$ ${\displaystyle {\boldsymbol {S}}_{1}}$

properties

The following is an overview of basic algebraic properties, interpreted and applied to semigroups. More detailed information can be found in the relevant main articles.

Commutativity

The semigroup is called commutative or Abelian if ${\displaystyle {\boldsymbol {S}}=(S,*)}$

${\displaystyle b*a=a*b}$

applies to all . The link itself is also referred to as commutative. ${\displaystyle a,b\in S}$ ${\displaystyle *}$

Using a construction named after Alexander Grothendieck , a group can be constructed for a given commutative semigroup, the Grothendieck group . For the commutative semigroup given by the addition of natural numbers , the Grothendieck group coincides with the usual construction of whole numbers .

Idempotence

→ Main article : Idempotence

An element of a semigroup is called idempotent if applies. ${\displaystyle a\in S}$ ${\displaystyle {\boldsymbol {S}}=(S,*)}$ ${\displaystyle a*a=a}$

If all elements of the semigroup are idempotent, one also speaks of an idempotent semigroup or a band . ${\displaystyle {\boldsymbol {S}}}$

Can be shortened

An element is called left- shortable if for all ${\displaystyle k\in S}$ ${\displaystyle {\boldsymbol {S}}=(S,*)}$ ${\displaystyle a,b\in S}$

${\displaystyle k*a=k*b\implies a=b}$

applies, or can be reduced by law if for all ${\displaystyle a,b\in S}$

${\displaystyle a*k=b*k\implies a=b}$

applies. If both left and right can be shortened, it can be shortened on both sides or just shortened. ${\displaystyle k}$

${\displaystyle {\boldsymbol {S}}}$means left- shortenable if every element from can be left- shortened , or right- shortenable if every element from can be shortened right-hand, and shortenable if all elements from can be shortened. A finite semigroup that can be shortened is a group . ${\displaystyle S}$ ${\displaystyle S}$ ${\displaystyle S}$

Note: In the following definitions, only the left-hand variant is listed as a substitute for the corresponding right-hand and bilateral variant; the right and two-sided variants are defined analogously.

Neutral element

An element of a semigroup is called left-neutral if the following applies to all : ${\displaystyle e\in S}$ ${\displaystyle {\boldsymbol {S}}=(S,*)}$ ${\displaystyle a\in S}$

${\displaystyle e*a=a}$.

A left-neutral element is obviously idempotent, but can also be left-shortened: ${\displaystyle e}$

${\displaystyle e*a=e*b\implies a=e*a=e*b=b}$

For all Conversely, every idempotent element that can be left- shortened is left-neutral in a semigroup , because the following applies to all : ${\displaystyle a,b\in S.}$ ${\displaystyle (S,*)}$ ${\displaystyle e}$ ${\displaystyle a\in S}$

${\displaystyle e*e*a=e*a,}$ so ${\displaystyle e*a=a.}$

If there is both a left-neutral and a right-neutral element in a semigroup, these are identical and therefore neutral. In a semigroup there is at most one neutral element (otherwise either only left-neutral or only right-neutral or neither nor); one then speaks of the neutral element of . A semigroup with a neutral element is also called a monoid . ${\displaystyle {\boldsymbol {S}}}$ ${\displaystyle {\boldsymbol {S}}}$

Invertibility and inverse

In a semigroup with a left-neutral element , an element can be left-inverted if one exists, so that: ${\displaystyle (S,*)}$ ${\displaystyle e\in S}$ ${\displaystyle j\in S}$ ${\displaystyle i\in S}$

${\displaystyle i*j=e}$.

One then calls a left inverse (also left inverse, f. ) Of . Left- invertible elements can always be left-shortened, because the following applies to all : ${\displaystyle i}$ ${\displaystyle j}$ ${\displaystyle j\in S}$ ${\displaystyle a,b\in S}$

${\displaystyle j*a=j*b\implies a=e*a=i*j*a=i*j*b=e*b=b.}$

If every element can be inverted to the left, then every element can also be inverted to the right, because with ${\displaystyle S}$ ${\displaystyle j\in S}$

${\displaystyle i*j=e}$and for follows ${\displaystyle h*i=e}$ ${\displaystyle i,h\in S}$

${\displaystyle j*i=e*j*i=h*i*j*i=h*e*i=h*i=e.}$

The following is also legally neutral: ${\displaystyle e}$

${\displaystyle j*e=j*i*j=e*j=j}$.

${\displaystyle (S,*)}$is in this case a group so that all inverses of an element match.

Weak inverse

Is there in a half group to a one with ${\displaystyle (S,*)}$ ${\displaystyle i\in S}$ ${\displaystyle j\in S}$

${\displaystyle j*i*j=j,}$

so this is called the weak inverse (or weak inverse ) of . Such is then also a regular member (Engl. Regular ) in ${\displaystyle j}$ ${\displaystyle i}$ ${\displaystyle j}$ ${\displaystyle S.}$

absorption

An element is called absorptive to the left in if the following applies to all : ${\displaystyle o\in S}$ ${\displaystyle (S,*)}$ ${\displaystyle a\in S}$

${\displaystyle o*a=o}$.

Every left or right absorbing element is idempotent. There is at most one absorbent element in a semigroup, because if there were two absorbent elements then it would apply . ${\displaystyle o_{1},o_{2}}$ ${\displaystyle o_{1}=o_{1}*o_{2}=o_{2}}$

Examples

The origin of the name

With the usual addition, the set of natural numbers forms a commutative and abbreviated semigroup that is not a group. Since the negative numbers are missing here, in other words " half " of the Abelian group of whole numbers, the name semigroup was obvious for this mathematical structure . In fact, in the past the term “semigroup” was used for a commutative monoid that could be shortened according to the definitions given above; later the above definition became generally accepted. ${\displaystyle \mathbb {N} _{0}=\{0,1,\ldots \}}$ ${\displaystyle (\mathbb {N} _{0},+)}$ ${\displaystyle (\mathbb {Z} ,+)}$

${\displaystyle (\mathbb {N} ,+),(\mathbb {N} _{0},\cdot )}$and form examples of commutative semigroups with different properties regarding neutral and absorbing elements as well as the shortening. ${\displaystyle (\mathbb {N} ,\cdot )}$

Transformation semigroups

For an arbitrary set, let the set of all functions of . Describes the composition of images , so then a semigroup is above the full transformation semigroup . Idempotent elements in are e.g. B. for each the constant mapping with for all , but also the identical mapping on as a neutral element. Under Half groups of hot transformation semigroups on . ${\displaystyle X}$ ${\displaystyle {\mathcal {T}}_{X}:=\{\tau \mid \tau \colon X\rightarrow X\}}$ ${\displaystyle X}$ ${\displaystyle \circ }$ ${\displaystyle \sigma ,\tau \in {\mathcal {T}}_{X}}$ ${\displaystyle \tau \circ \sigma \colon \,x\mapsto \tau (\sigma (x))}$ ${\displaystyle ({\mathcal {T}}_{X},\circ )}$ ${\displaystyle X}$ ${\displaystyle {\mathcal {T}}_{X}}$ ${\displaystyle a\in X}$ ${\displaystyle \operatorname {c} _{a}\colon X\rightarrow X}$ ${\displaystyle \operatorname {c} _{a}(x)=a}$ ${\displaystyle x\in X}$ ${\displaystyle \operatorname {id} _{X}}$ ${\displaystyle X}$ ${\displaystyle ({\mathcal {T}}_{X},\circ )}$ ${\displaystyle X}$

application

Formal languages

For an arbitrary set let ${\displaystyle X\neq \emptyset }$

${\displaystyle X^{*}:=\bigcup _{n\in \mathbb {N} _{0}}X^{n}}$

the clover's shell of . Define a multiplication for all of them ${\displaystyle X}$ ${\displaystyle (x_{1},\ldots ,x_{n}),(y_{1},\ldots ,y_{m})\in X^{*}}$

${\displaystyle (x_{1},\ldots ,x_{n})\cdot (y_{1},\ldots ,y_{m})=(x_{1},\ldots ,x_{n},y_{1},\ldots ,y_{m}),}$

then a semigroup and also a monoid , the free semigroup above . If you write the elements simply in the form , then the elements are called in words above the alphabet , the word is empty and the multiplication is called concatenation . In theoretical computer science , one generally assumes that an alphabet is finite; subsets of the Kleenian shell of an alphabet with the empty word are called formal languages . ${\displaystyle (X^{*},\cdot )}$ ${\displaystyle X}$ ${\displaystyle (x_{1},\ldots ,x_{n})\in X^{*}}$ ${\displaystyle x_{1}\ldots x_{n}}$ ${\displaystyle X^{*}}$ ${\displaystyle X}$ ${\displaystyle \varepsilon :=(\,)=\{\,\}}$ ${\displaystyle \cdot }$

Functional analysis, partial differential equations

Semigroups also play a role in the solution theory of partial differential equations . Let be a family of bounded transformations on a complete metric space , i.e. H. for each there is a with ${\displaystyle (A_{t})_{t\geq 0}:=(A_{t})_{t\in [0,\infty )}}$ ${\displaystyle A_{t}\colon \,X\rightarrow X}$ ${\displaystyle (X,d)}$ ${\displaystyle t\in [0,\infty )}$ ${\displaystyle m_{t}\in [0,\infty )}$

${\displaystyle d(A_{t}(x),A_{t}(y))\leq m_{t}\cdot d(x,y)}$for everyone . ${\displaystyle x,y\in X}$

In particular, each is continuous and forms a commutative semigroup with a neutral element if: ${\displaystyle A_{t}}$ ${\displaystyle S:=\{A_{t}\mid t\in [0,\infty )\}}$ ${\displaystyle (S,\circ )}$ ${\displaystyle \operatorname {id} _{X}}$

${\displaystyle A_{0}=\operatorname {id} _{X}}$ and

${\displaystyle A_{t+s}=A_{t}\circ A_{s}}$for everyone . ${\displaystyle t,s\geq 0}$

The function is a semigroup homomorphism from to and is called a one-parameter semigroup of operators (see also: continuous dynamic system ). One is also contractive in case ${\displaystyle (A_{t})_{t\geq 0}}$ ${\displaystyle ([0,\infty ),+)}$ ${\displaystyle (S,\circ )}$ ${\displaystyle A_{t}}$

${\displaystyle d(A_{t}(x),A_{t}(y))<d(x,y)}$is for everyone . ${\displaystyle x,y\in X,x\neq y}$

The semigroup is called uniformly continuous if there is a bounded linear operator on a Banach space for all of them and we have: ${\displaystyle (A_{t})_{t\geq 0}}$ ${\displaystyle t\geq 0}$ ${\displaystyle A_{t}}$ ${\displaystyle (X,\|.\|_{X})}$

${\displaystyle \lim _{t\downarrow 0}\|A_{t}-\operatorname {id} _{X}\|=0,}$

where denotes the operator norm . ${\displaystyle \|\cdot \|}$

The semigroup is called strongly continuous if the mapping is for all ${\displaystyle (A_{t})_{t\geq 0}}$ ${\displaystyle x\in X}$

${\displaystyle [0,\infty )\to X,\,t\mapsto A_{t}(x),}$

is continuous; then exist with so that ${\displaystyle k,m\in \mathbb {R} }$ ${\displaystyle m\geq 1}$

${\displaystyle \|A_{t}(x)\|_{X}\leq me^{kt}\|x\|_{X}}$

applies. Can be chosen, it is called a restricted one-parameter semigroup . ${\displaystyle k=0}$ ${\displaystyle (A_{t})_{t\geq 0}}$

See also : strongly continuous semigroup

See also

• Inverse semigroup

literature

• Pierre Antoine Grillet: Semigroups: An Introduction to the Structure Theory. Marcel Dekker, New York 1995, ISBN 0-8247-9662-4 .
• Udo Hebisch , Hanns Joachim Weinert: Half Rings: Algebraic Theory and Applications in Computer Science. BG Teubner, Stuttgart 1993, ISBN 3-519-02091-2 .
• John F. Berglund, Hugo D. Junghenn, Paul Milnes: Analysis on Semigroups: Function Spaces, Compactifications, Representations. John Wiley & Sons, New York et al. 1989, ISBN 0-471-61208-1 .
• John M. Howie: Fundamentals of Semigroup Theory. Oxford University Press, Oxford 1995, ISBN 0-19-851194-9 .
• Mario Petrich: Introduction to Semigroups. Bell & Howell, Columbus OH 1973, ISBN 0-675-09062-8 .

Web links

Wiktionary: Semi-group  - explanations of meanings, word origins, synonyms, translations

• Lev Shevrin : Semigroup . In: Michiel Hazewinkel (Ed.): Encyclopaedia of Mathematics . Springer-Verlag , Berlin 2002, ISBN 978-1-55608-010-4 (English, online ).
• Eric W. Weisstein : Semigroup . In: MathWorld (English).
• Tero Harju: Lecture Notes on Semigroups . (PDF; 454 kB). University of Turku, 1996 (script)

References and comments

1. ^ Mario Petrich: Introduction to Semigroups. S. 4. PA Grillet: Semigroups: An Introduction to the Structure Theory. P. 4f.
2. ^ John Fountain: Semigroups, Algorithms, Automata and Languages . Ed .: Gracinda MS Gomes. World Scientific, 2002, ISBN 978-981-277-688-4 , An introduction to covers for semigroups, pp. 167-168 ( google.com ). preprint
3. ↑ Paul Lorenzen : Abstract foundation of the multiplicative ideal theory . In: Math. Z. , 45, 1939, pp. 533-553.
4. ^ John Mackintosh Howie : Fundamentals of Semigroup Theory. S. 6. PA Grillet: Semigroups: An Introduction to the Structure Theory. P. 2.
5. ↑ Udo Hebisch , Hanns Joachim Weinert: Half Rings: Algebraic Theory and Applications in Computer Science. P. 244.
6. ↑ John E. Hopcroft , Jeffrey Ullman : Introduction to Automata Theory, Formal Languages, and Complexity Theory . 2nd Edition. Addison-Wesley , Bonn, Munich 1990, ISBN 3-89319-181-X , p. 1 (Original title: Introduction to automata theory, languages ​​and computation .).
7. ^ Einar Hille : Methods in Classical and Functional Analysis . Addison-Wesley, Reading MA et al. a. 1972. p. 165ff.