1 Semigroup basics

1.1 Definition and axioms

A semigroup is an algebraic structure consisting of a set together with an associative binary operation. Formally, a semigroup is a pair \((S,\cdot)\) where \(S\) is a set and \(\cdot : S\times S\to S\) is an operation satisfying associativity: \[ (x\cdot y)\cdot z = x\cdot (y\cdot z)\quad \text{for all }x,y,z\in S. \] Unlike groups or rings, semigroups are not required to have an identity element or inverses.

1.2 Subsemigroups and generated subsemigroups

A subsemigroup of a semigroup \((S,\cdot)\) is a subset \(T\subseteq S\) that is closed under the semigroup operation, meaning \(T\cdot T\subseteq T\), and inherits the same associativity. Given a subset \(A\subseteq S\), the subsemigroup generated by \(A\) is the smallest subsemigroup of \(S\) that contains \(A\). Equivalently, it consists of all finite products of elements of \(A\), with any parenthesization permitted by associativity.

1.3 Semigroups versus monoids

A monoid is a semigroup with an identity element. In a monoid \((M,\cdot,1)\), \(1\cdot x=x\cdot 1=x\) for all \(x\in M\). The presence of an identity affects generation: in a monoid, products can be taken to be “empty,” which can change whether certain expressions are considered generated. In semigroups without identity, every generated element must arise from a nonempty finite product.

2 Generators of semigroups

2.1 Single-generator semigroups

A semigroup \(S\) is called singly generated (or cyclic in some terminology) if there exists an element \(a\in S\) such that every element of \(S\) can be written as a power of \(a\): \[ S=\{a,a^2,a^3,\dots\}, \] where \(a^n\) denotes the product of \(n\) copies of \(a\). Because there may be no identity, the exponent \(n\) is typically taken to be positive.

2.1.1 Powers and finite products

Even when using a single generator, the general definition of generation by finite products reduces to powers. Any finite product of \(a\) with itself has the form \(a^n\), and conversely each power corresponds to one such product. Thus, the generated subsemigroup from \(\{a\}\) is precisely the set of all positive powers of \(a\).

2.2 Multi-generator semigroups

More generally, a semigroup \(S\) is generated by a set \(A\subseteq S\) if every element of \(S\) is a finite product of elements from \(A\). When \(A\) has more than one element, the order of factors can matter because semigroup multiplication need not be commutative.

2.2.1 Words over a generating set

To formalize “finite products,” one uses words. If \(A\) is a generating set, elements are represented by words \(a_{i_1}a_{i_2}\cdots a_{i_k}\) where each \(a_{i_j}\in A\). Distinct words can evaluate to the same element in the semigroup, reflecting relations not explicit in the generating set itself. The evaluation map from words to \(S\) sends a word to the corresponding product in \(S\).

2.3 Minimal generating sets

A minimal generating set is a generating set with no proper subset that still generates the whole semigroup. Minimality here is set-theoretic: removing any generator prevents reaching at least one element of the semigroup. Minimal generating sets may not be unique; different choices of generators can have the same minimal size.

2.4 Relation to generating homomorphisms

A useful perspective comes from homomorphisms. If \(f:S\to T\) is a semigroup homomorphism and \(S\) is generated by \(A\subseteq S\), then \(T\) is generated by \(f(A)\) whenever \(f\) is surjective. Conversely, understanding the images of generators can reduce questions about the entire semigroup to questions about a generating subset.

3 Constructing the generated semigroup

3.1 The subsemigroup generated by a set

Given \((S,\cdot)\) and \(A\subseteq S\), the generated subsemigroup \(\langle A\rangle\) can be constructed inductively:

  • start with \(A_1=A\),
  • define \(A_{n+1}=A_n\cdot A \,\cup\, A_n\),

and let \(\langle A\rangle=\bigcup_{n\ge 1}A_n\). Associativity guarantees that any finite product of elements from \(A\) appears at some stage.

3.2 Normal forms for products (when applicable)

In special settings, products can be rewritten into normal forms. This typically occurs when the semigroup satisfies additional algebraic constraints (for instance, commutativity, particular rewriting rules, or structures where elements admit canonical representatives). In a general semigroup, however, there is no guarantee of a unique reduced form: the same element may be represented by many different words, and finding a canonical one can be hard.

3.3 Complexity: describing elements via generators

Generation provides a form of compression: rather than listing all elements, one can specify generators and understand the semigroup as “all outputs of finite products.” The trade-off is computational and descriptive complexity. Knowing the generators does not immediately yield short expressions for arbitrary elements; elements can require long words to produce, even in finite semigroups.

3.4 Examples from transformation semigroups

A common source of examples is the transformation semigroup: a semigroup of functions from a set to itself, under composition. If a set of transformations \(A\) generates the transformation semigroup \(S\), then every transformation in \(S\) is a composition of finitely many transformations from \(A\). Here, the notion of a word becomes literal: a word corresponds to a composition order, and evaluation corresponds to applying the composed function.

4 Generated semigroup properties

4.1 Size constraints and finiteness

If \(S\) is generated by a finite set \(A\), then \(S\) is finitely generated. This does not automatically imply that \(S\) is finite. Infinite semigroups can be finitely generated; likewise, finite semigroups can be generated by small sets, depending on the structure. Finiteness typically imposes stronger constraints, including repetition among generated products.

4.2 Growth behavior under repeated generation

For a finite generating set \(A\), one can study growth by counting how many distinct elements are represented by words of bounded length. Although the full semigroup may be finite, the number of reachable elements as length increases often increases initially and then saturates. This viewpoint connects generation to combinatorial growth phenomena.

4.3 Idempotents and eventual periodicity (in finite cases)

In finite semigroups, repeatedly multiplying by a fixed element or repeatedly applying products built from generators inevitably leads to repetition. One consequence is eventual periodicity: sequences defined by iterated multiplication eventually cycle. Closely related is the existence of idempotent elements \(e\) satisfying \(e\cdot e=e\). Idempotents play a central role in understanding how generated products stabilize.

4.4 Green’s relations and their generation viewpoint

Green’s relations partition a semigroup into classes that reflect how elements generate principal ideals on the left and right. When the semigroup is described via generators, these relations can often be analyzed through how generated products build left and right ideals. This provides a structural lens: generation is not only about reachability of elements but also about how multiplication patterns organize the semigroup into interrelated components.

5 Special classes and canonical settings

5.1 Commutative semigroups and abelian generation

In a commutative semigroup, the order of factors in a product does not affect the result. As a result, words that differ only by permutation evaluate to the same element. Generation can then be reformulated in terms of multisets of generators or exponent vectors, since each product corresponds to a combination of generators with total multiplicities.

5.2 Cyclic and near-cyclic semigroups

A cyclic semigroup is generated by one element. Some semigroups are “almost” cyclic in the sense that a small set of elements, perhaps two, suffices to generate the whole structure. In such cases, normal form questions and growth behavior can sometimes be analyzed in terms of limited generating complexity, though general uniqueness of representations is still not guaranteed.

5.3 Presentations of semigroups via generators and relations

A presentation specifies a semigroup by generators together with relations that identify certain products. In this framework, one begins with the free semigroup on the generators and then factors by a congruence generated by the relations. Generation by the given generators becomes automatic in the presented structure; the relations determine which words represent the same element.

5.4 Free semigroups and universal properties

The free semigroup on a set \(A\) is the semigroup of all nonempty words over \(A\), with multiplication given by concatenation. It is characterized by a universal property: any function from \(A\) into a semigroup \(S\) extends uniquely to a homomorphism from the free semigroup to \(S\). In this setting, “generation” corresponds to the fact that every element of the free semigroup already arises from words in the generators, without additional identifications.

6 Homomorphic images and transfer of generators

6.1 Images of generated semigroups

Let \(f:S\to T\) be a homomorphism and let \(S\) be generated by \(A\subseteq S\). Then every element of \(f(S)\) is an image of some word in \(A\), hence \(f(S)\) is generated by \(f(A)\). If \(f\) is surjective, then \(T\) itself is generated by \(f(A)\).

6.2 Preimages and lifting generation through maps

Given a subset \(B\subseteq T\), one may ask whether \(B\) generates \(T\) by examining its preimage under \(f\). While images of generators behave predictably under homomorphisms, the reverse direction is more subtle: preimages of generators need not generate the whole domain, especially if \(f\) has nontrivial kernel-like behavior expressed via congruences.

6.3 Quotients and generation under congruences

Many semigroup homomorphisms can be described via quotients by congruences. If two words (or products) are identified under a congruence, then the quotient semigroup “forgets” the distinction. In such quotients, the images of a generating set for the original semigroup form a generating set for the quotient. Relations in the congruence determine how much the quotient collapses the free combinations of generators.

7 Computational aspects

7.1 Testing membership in a generated semigroup

Given a semigroup \(S\) (often finite), a generating set \(A\), and an element \(x\in S\), the membership question asks whether \(x\in\langle A\rangle\). For finite semigroups, this can be decided by systematic exploration of products up to a length that guarantees coverage. For infinite semigroups, the problem can become more complex and may require additional structure or decidability assumptions.

7.2 Enumerating generated elements for finite semigroups

When \(S\) is finite, one can enumerate \(\langle A\rangle\) by iteratively closing under multiplication. A typical approach maintains a growing set of discovered elements and repeatedly adds products of already discovered elements with generators until no new elements appear. Termination is guaranteed by finiteness.

7.3 Algorithms based on Cayley graphs

A Cayley graph viewpoint can be used: vertices represent elements of the semigroup (or a reachable subset), edges correspond to right multiplication by generators, and paths correspond to words. Reachability from the starting set (depending on conventions for nonempty products) then captures membership in the generated subsemigroup. This graph-based method can also support shortest-word searches when edges are uniform.

Finding small generators is often more difficult than verifying that a proposed set generates. Practical generator search balances:

  • the cost of computing closure under products,
  • the combinatorial explosion of word length,
  • and heuristic strategies to propose candidate generators from observed structure (such as elements that appear to increase reachability quickly).

In computational settings like transformation semigroups, it is common to use iterative refinement: propose generators, compute the closure, and adjust candidates based on how much of the target set is reached.