# 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 {\ varvec {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

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)) 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}}$

## 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 .