Semigroup ($(S,\ast )$)

A semigroup is an algebraic magma whose binary operation has the associative property. Its products can be regrouped while preserving the order of their elements. An identity element and inverse elements are not required.

For example, the positive integers with addition form a semigroup, since $(a+b)+c=a+(b+c)$ and a sum of positive integers is positive. They have no identity element: it would have to be zero, which is outside that set. Nonempty words over an alphabet with concatenation give a noncommutative example without an identity element. Including the empty word instead gives a free monoid.

The usefulness of a semigroup is that an ordered list has one product regardless of its parentheses. This permits replacing a consecutive block by its already computed value. Here the empty set is also allowed as a semigroup; a monoid is necessarily nonempty because it contains an identity element.

A rectangular band is a semigroup satisfying the displayed identities; these also imply associativity. Every nonempty such algebra is a product $B\times C$ with $(b,c)\ast (b^{\prime },c^{\prime })=(b,c^{\prime })$. Fixing $e$, the factor sets are $B=\{x\ast e\}$ and $C=\{e\ast x\}$, and $x\mapsto (x\ast e,e\ast x)$ has inverse $(b,c)\mapsto b\ast c$. Homomorphisms between nonempty products are exactly pairs of maps on the two factors.

The category of rectangular bands is Cartesian closed. For nonempty products $A=B\times C$, $D=E\times F$, the exponential is $E^B\times F^C$. Also $D^0=1$ and $0^A=0$ for nonempty $A$. It has no subobject classifier: the classifier would have two elements, hence would be left-zero or right-zero, while its characteristic maps on a two-by-two product could not single out a one-point subalgebra.

An element of a semigroup is idempotent when multiplying it by itself leaves it unchanged. Every element of a left-zero or right-zero semigroup is idempotent, whereas a group has only its identity as an idempotent. The Ellis–Numakura lemma guarantees such an element in a nonempty compact one-sided topological semigroup. Additive idempotence on ultrafilters gives the idempotent ultrafilter relation $p+p=p$.

A semigroup presentation specifies generators $X$ and equalities between nonempty words. The resulting semigroup is the quotient of the free semigroup $X^{+}$ by the smallest congruence containing these equalities. Two words are equal precisely when one can be transformed into the other by finitely many replacements in contexts, using the defining equalities in either direction.

A semigroup presentation is finite when both its generator set and its list of defining equalities are finite. A finite transition table for a Turing machine can be encoded this way: state-and-tape words simulate transitions, boundary rules supply blank cells, and halting-state rules erase the configuration to one distinguished symbol.

A finite deterministic Turing machine can be represented by a finite semigroup presentation whose generators are tape symbols, state symbols, a boundary marker $h$, and an accept symbol $q$. Defining equalities replace the local scanned symbol and state according to machine instructions, with separate boundary cases for implicit blanks. Only terminal-state equalities erase tape letters and then replace $h{q}_{H}h$ by $q$. A derivation from an initial description to $q$ must encounter a terminal state before its first erasure. Simulation equalities preserve halting membership in either direction: for a deterministic transition $C\to D$, $C$ halts if and only if $D$ halts. Thus reverse use of defining equalities cannot create a false halting certificate. Boundary and erasure rules require explicit checking for every chosen encoding.

A subsemigroup is a nonempty subset of a semigroup closed under its associative operation. In a compact Hausdorff space carrying a left-topological semigroup, descending chains of nonempty compact subsemigroups have a nonempty compact subsemigroup as their intersection. This supplies the minimal object used in the Ellis–Numakura lemma.

A monoid is a semigroup with a two-sided identity element $e$: $e\ast a=a\ast e=a$ for every element $a$. Associativity handles the grouping of a nonempty sequence; the identity element also supplies the result for an empty sequence. This makes the same rules apply to combining zero, one, or many contributions. ^[ref].

The nonnegative integers $\{0,1,2,\dots \}$ with addition form a commutative monoid, with identity element zero. They do not form a group: a positive integer has no additive inverse in that set. All words over an alphabet with concatenation form a free monoid, whose identity element is the empty word. The full transformation monoid consists of all self-maps of a set, with function composition and the identity function.

These examples explain why monoids are useful: accumulation needs an operation and a starting value, but it need not be reversible. Adding counts, joining strings, and composing transformations all share the same grouping and identity laws. Requiring every element to have an inverse element gives a group, a stronger structure suitable for reversible operations.

An inverse element of $a$ in a monoid is an element $b$ satisfying $a\ast b=b\ast a=e$, where $e$ is the identity element. Its notation is $a^{-1}$. Some elements of a monoid can lack an inverse element; a group requires one for every element. Associativity makes a two-sided inverse element unique: if $b,c$ both invert $a$, then $b=b\ast (a\ast c)=(b\ast a)\ast c=c$.

For the full transformation monoid, a self-map has an inverse element exactly when it is a bijection; that element is its inverse function. On $\{0,1\}$, the swap $s(0)=1,s(1)=0$ is its own inverse element, while a constant function has none because it merges the two inputs.

A transformation monoid is a collection of self-maps of a fixed set $X$ that contains the identity function and is closed under function composition. The associative property comes from function composition. A monoid action describes transformations of a set that obey a monoid's multiplication and identity laws.

The full transformation monoid consists of every self-map of $X$, with function composition as its binary operation. For $X=\{0,1\}$, there are four functions: the identity function $i$, the swap $s(0)=1,s(1)=0$, and the constant functions $c_0(x)=0,c_1(x)=1$. Their composition order matters: $c_0\circ s=c_0$, whereas $s\circ c_0=c_1$. Thus associativity does not imply commutativity.

Only $i$ and $s$ are bijections, and their inverse elements are themselves. They form a two-element group within this monoid. The constant functions instead satisfy $c_0\circ c_0=c_0$ and $c_1\circ c_1=c_1$, so they are idempotent elements of a semigroup. Such irreversible transformations explain why the monoid setting is useful even when a group would be too restrictive.

A left monoid action assigns each $m\in M$ a map $a\mapsto m\cdot a$ with $1\cdot a=a$ and $(mn)\cdot a=m\cdot (n\cdot a)$. It need not be invertible or injective. A left M-set is equivalently a covariant functor from the one-object category determined by $M$.

A right monoid action has $x1=x$ and $(xm)n=x(mn)$. It is a contravariant functor from the one-object category of the monoid to sets. The regular right action is multiplication on $M$ itself. Products of right actions use the diagonal action.

Give $M\times X$ the diagonal right monoid action. On its equivariant maps into $Y$, define $(ek)(g,x)=e(kg,x)$. The evaluation map of an exponential object is $e(1,x)$ and currying of $h:Z\times X\to Y$ is $\hat{h}(z)(g,x)=h(zg,x)$. Both maps are equivariant, and they are inverse under evaluation. The left multiplication $kg$ in this right action is essential in a noncommutative monoid.

For a group, evaluation at the identity identifies the monoid exponential with all set functions $X\to Y$. Its inverse is $e_f(g,x)=f(x{g}^{-1})g$, and the resulting function action is the displayed formula. Fixed functions are precisely equivariant maps. The inverse on the input is necessary for equivariance of evaluation and for the right-action law.

An equivariant map $h:A\to B$ between left M-sets obeys $h(m\cdot a)=m\cdot h(a)$. These are the natural transformations of the corresponding functors from the one-object monoid category.

An M-set is a set carrying a monoid action. This terminology here uses left actions. Morphisms are equivariant maps of monoid sets, and the resulting functor category $[M,\mathbf{Set}]$ is an elementary topos.

A monoid homomorphism $h:M\to N$ preserves multiplication and identity: $h(xy)=h(x)h(y)$ and $h(1_M)=1_N$. It therefore preserves every finite ordered product, including the empty product. The monoids with these maps form the category $\mathbf{Mon}$.

A monoid automorphism is a bijective operation- and identity-preserving self-map of a monoid. Its inverse is also a monoid homomorphism. Permuting prime numbers and extending by prime factorization gives all automorphisms of the multiplicative monoid of positive natural numbers; extending by $0\mapsto 0$ gives automorphisms of the multiplicative monoid including zero.

The free monoid ${\Sigma }^{\ast }$ on an alphabet $\Sigma$ consists of all finite words over an alphabet, including the empty word $\epsilon$, with concatenation as its binary operation. Distinct strings represent distinct elements: there are no imposed equalities between different sequences of letters. The empty word is its identity element, and concatenation has the associative property.^[ref]

For $\Sigma =\{a,b\}$, the elements begin $\epsilon ,a,b,aa,ab,ba,bb,\dots$. Both $(ab)a$ and $a(ba)$ give the same word $aba$, but $ab\ne ba$, so this monoid is not commutative. The length of a word over an alphabet obeys $\ell (uv)=\ell (u)+\ell (v)$; it is a monoid homomorphism to the nonnegative integers with addition. A nonempty word has no inverse element, since joining it to any other word cannot decrease its length to zero.

The defining benefit of being free is that letters can stand for arbitrary elements of another monoid. Choose a value $h(a)$ for each letter $a\in \Sigma$; then $h(a_1\cdots a_n)=h(a_1)\ast \cdots \ast h(a_n)$, with $h(\epsilon )=e$, is the unique monoid homomorphism extending those choices. Associativity and the identity element make this evaluation consistent for every finite word. For example, interpreting the letters as self-maps evaluates a word as a composed transformation; interpreting them as nonnegative counts evaluates it by addition.

A commutative monoid is a monoid whose operation is commutative. The natural numbers with addition form a commutative monoid that is not an abelian group, because positive elements have no additive inverses.

The free commutative monoid on $d$ generators consists of the nonnegative integral sums of those generators, with unique coefficients. Its semigroup algebra over a commutative ring is the polynomial ring in $d$ variables. In a smooth toric chart, the dual-cone lattice points form such a monoid, yielding affine-space coordinates.

A commutative monoid is cancellative when $a+c=b+c$ implies $a=b$. Cancellation makes the natural map into its Grothendieck group injective.

For an integer $m\ge 2$, the positive integers congruent to one modulo $m$ form a cancellative commutative monoid under multiplication. The identity is one, and it is the only unit. Proper factors outside this congruence class do not witness reducibility inside the monoid. Hence irreducible elements of a commutative monoid need not coincide with ordinary prime numbers.

The congruence submonoid of the positive integers with modulus ten has four distinct irreducible elements of a commutative monoid $21,221,51,91$ with equal pairwise products. Their ordinary prime factors are respectively $(3,7),(13,17),(3,17),(7,13)$. None of these proper prime factors is congruent to one modulo ten. The Euclid lemma proves that a product of two distinct primes has no other proper positive divisors, so all four are irreducible in this monoid. This gives nonunique factorization without assuming the fundamental theorem of arithmetic.

A nonunit element of a commutative monoid is irreducible if each factorization has a unit factor. In a submonoid of the positive integers under multiplication, the only unit is one. Irreducibility is relative to the allowed factors: a composite integer can be irreducible in a smaller monoid even though it is not a prime number.

A cancellative commutative monoid is torsion-free in this sense when $na=nb$ implies $a=b$ for every positive integer $n$. Its Grothendieck group is then a torsion-free abelian group, because $n(a-b)=0$ forces $na=nb$. This is the condition inherited by a submonoid of a torsion-free abelian group.

This category has commutative monoids and their homomorphisms. Pointwise addition makes each hom-set a commutative monoid, and composition is additive in both variables. Finite cartesian products are also coproducts, using the coordinate injections with zero in the other coordinates and summing images. Therefore it is a semi-additive category, but it is not an additive category. The reflexive pair from the submonoid $\{(m,n):m\le n\le 2m\}$ of ${\mathbb{N}}^2$ to $\mathbb{N}$, using the two projections and section $m\mapsto (m,m)$, has an arrow from $1$ to $2$ and none from $2$ to $1$ in its represented graph. Thus a reflexive pair here need not yield a groupoid.

An additive semigroup is a semigroup whose operation is written as addition.

A face $F$ of an additive monoid $S$ is a submonoid such that $a+b\in F$ implies $a,b\in F$. If $S=C\cap M$ for a rational polyhedral cone, its faces are precisely $S\cap \nu$ for faces $\nu$ of $C$. Finite generation and clearing rational denominators identify these monoid faces with the exposed faces of the cone.

// Target: geometry-and-topology.bigb

A topological semigroup is a semigroup with a topology for which multiplication is jointly continuous.

A left-topological semigroup requires only that every right translation $x\mapsto xa$ be continuous.

Every nonempty compact Hausdorff left-topological semigroup contains an idempotent. Choose a minimal nonempty compact subsemigroup $K$. For $a\in K$, minimality gives $Ka=K$; the nonempty compact subsemigroup $\{x\in K:xa=a\}$ is therefore all of $K$, so $a^2=a$.