Semigroup theory studies objects that can be combined by an associative operation: grouping a sequence of combinations differently does not change its result. It is useful when actions can be composed but cannot necessarily be undone. Strings, transformations and many mathematical models of repeated processes have this structure. The gold standard is to specify the objects and operation, check the law, and use only the rearrangements that the law actually permits.
This guide develops that idea through a three-state machine, exact composition calculations, a text-processing example and changed-context exercises. You will learn the differences between semigroups, monoids and groups; how generators produce a system; and why identity, reversibility, commutativity and idempotence are separate questions. The examples are deliberately small mathematical models, not descriptions of a particular commercial system.
Use the Gold Standard collection and How X Works hub for the wider subject map. Universal Algebra explains constructions shared by many algebraic families. Here the focus is one associative operation and the structure of its repeated use. The Education guide supplies a practical learning test: explain what remains valid after the conditions change.
Choose your semigroup theory route
Chapters 1–3: Understand the laws
Chapters 4–6: Calculate transformations
Chapters 7–9: Study repetition and structure
Chapters 10–12: Apply and test transfer
Chapter index
Understand the laws · Chapters 1–3
1. Start with the operation and its domain
Calculate transformations · Chapters 4–6
4. Build a transformation model you can calculate
Study repetition and structure · Chapters 7–9
7. Understand repeated powers without assuming a group
Apply and test transfer · Chapters 10–12
10. Connect the algebra to computation carefully
Resolve questions and practise · Chapters 13–14
Closure comes before a law
A semigroup consists of a nonempty set S and a binary operation taking every ordered pair of elements of S to an element of S. The operation must be associative: (ab)c = a(bc) for all a, b and c in S. We often omit the multiplication symbol, even when the operation is not numerical multiplication. This convention saves space but makes identifying the operation essential.
Take the positive integers with addition. Adding two positive integers stays within the positive integers, and addition is associative, so this is a semigroup. There is no additive identity in this set because zero has been excluded. With the nonnegative integers instead, zero is present and is an identity. The operation has not changed, but the available elements have.
Now take positive integers with subtraction. The result of 2 minus 5 is outside the set. This fails closure before we even discuss associativity. Enlarging the set to all integers repairs closure, but subtraction remains nonassociative: (8 − 3) − 2 = 3, while 8 − (3 − 2) = 7. Repairing one property does not repair another automatically.
A specification that someone else can check
Write three things before using the word semigroup: what counts as an element, how two elements combine, and what equality of results means. For strings, equality might mean exactly the same sequence of symbols. For functions, equality means the same output on every input in the declared domain. For approximate measurements, an informal “close enough” test may not even define an equivalence relation.
This is why a single successful calculation is evidence about that calculation, not proof of associativity. The law quantifies over every triple. In a finite system of n elements, checking all n cubed triples is one direct method. In an infinite system, a general argument is usually needed. A clear definition often makes that argument shorter than a large collection of examples.
What associativity permits
Associativity allows a sequence abc to be evaluated as (ab)c or a(bc). It does not allow changing abc to bac. That second change requires a different property, commutativity, which says ab = ba. Many important semigroups are not commutative, and their usefulness comes partly from retaining the order of actions.
String concatenation is a simple illustration. Joining “ab” to “c” and then to “de” produces “abcde”. Joining “ab” to the result of joining “c” and “de” also produces “abcde”. But swapping “ab” and “c” produces “cabde”. Parentheses have changed in the first comparison; sequence order has changed in the second.
For four strings, the five complete parenthesisations all produce the same concatenated string. This does not mean their implementation costs are equal. A program that copies characters at each join can allocate different intermediate objects for different groupings. The abstract result and the cost of obtaining it are separate questions.
A useful application boundary
The existing guide to ropes, tree concatenation and text editing explores how a tree represents a sequence. Changing a tree’s shape can preserve its sequence because concatenation is associative. Exchanging its left and right text pieces usually does not preserve the sequence. That is the algebraic reason rebalancing and reordering must not be confused.
Try a quick diagnosis. A colleague says: “We can process these records in any order because combining them is associative.” Ask whether “any order” means a different parenthesisation of the same sequence or a permutation of the records. The first may follow; the second does not. A lawful parallel reduction must preserve sequence order unless additional laws justify changing it.
Even with order preserved, the implementation must realise the stated operation. Exact integer addition and fixed-precision floating-point addition are different operations. A mathematical proof about exact arithmetic cannot silently grant permissions to a rounded computation.
Monoids include an empty combination
A monoid is a semigroup with an identity e satisfying ea = a = ae for every element a. An identity leaves every element unchanged on both sides. For strings under concatenation, the empty string is the identity. For functions under composition, the identity function is the identity. The symbol e stands for a role, not a particular numerical value.
An identity, when it exists, is unique. If e and f are both identities, ef = f because e acts as an identity, and ef = e because f acts as an identity. Therefore e = f. The proof uses both sides of the definition. Merely finding an element that works on one side does not establish the full claim.
A group is a monoid in which each element has a two-sided inverse. Positive integers under addition form a semigroup; nonnegative integers under addition form a monoid; all integers under addition form a group. In each case addition is commutative, but commutativity is not part of the general definitions of semigroup, monoid or group.
Why the empty case matters
Suppose a task combines a list of strings. For a nonempty list, repeated concatenation works in the semigroup of nonempty strings. For an empty list there is no first element from which to begin. Allowing the empty string supplies a natural result and turns the structure into a monoid. A programming interface that accepts empty collections must decide what this case means.
An absorbing element plays the opposite role. An element z with az = z = za absorbs every element. Zero is absorbing for ordinary multiplication, while one is its identity. Zero is the identity for ordinary addition instead. Saying “zero does nothing” without naming the operation is therefore unreliable.
Victoria Gould’s semigroup lecture course provides the formal starting definitions and hierarchy. Keep a separate checklist for each property rather than treating “more algebraic” as a single scale of quality.
CHAPTER 4 OF 14 · Calculate transformations
4. Build a transformation model you can calculate
Three states and two actions
Let the state set be Q = {0, 1, 2}. Think of these as three display settings. Define a rotation r by r(0) = 1, r(1) = 2 and r(2) = 0. Define a reset z by z(0) = z(1) = z(2) = 0. Both are total functions from Q to Q. Rotation remembers the input; reset discards it.
Use the convention fg = f composed with g: apply g first, then f. Under this convention rz resets first and then rotates, so it sends every state to 1. By contrast, zr rotates first and then resets, so it sends every state to 0. Thus rz and zr are different functions. Testing input 0 is already enough to distinguish them.
Write a transformation as a triple of its outputs on 0, 1 and 2. Then r = (1, 2, 0), z = (0, 0, 0), rz = (1, 1, 1), and zr = (0, 0, 0). This notation makes equality completely checkable: two triples are equal exactly when their three coordinates agree.
Why composition is associative
For any three functions f, g and h from Q to Q, both (fg)h and f(gh) send an input x to f(g(h(x))). This proves associativity without checking a table of triples. It does not prove commutativity; our reset and rotation explicitly refute that property.
Not every workflow can immediately be treated as a total function on a fixed state set. An action may be unavailable in some states, may depend on an external input, or may fail. One modelling option is to include a failure state and define every outcome. Another is to work with partial transformations. Neither choice is free: it changes what the elements mean and which equalities are justified.
Before using this example elsewhere, say whether the recorded state contains everything that affects the next action. A three-value display model does not include timing, network history or a user’s permissions. Its algebra only covers the behaviour we defined.
CHAPTER 5 OF 14 · Calculate transformations
5. Generate the whole system from a few actions
Follow closure until nothing new appears
Starting with r and z, repeatedly compose available functions and keep each distinct result. Rotation twice gives r squared = (2, 0, 1). Rotation three times gives the identity e = (0, 1, 2). The composites rz and r squared z give the constant functions c1 and c2, while z is c0. This yields six functions: e, r, r squared, c0, c1 and c2.
To show these are all the generated elements, we need more than having found six. We must show the collection is closed and contains the generators. Let r to the power i denote a rotation, with exponents reduced modulo three. Then r to the power i times r to the power j is r to the power i+j. Rotation followed in the written product by a constant gives r to the power i times cj = c(i+j modulo three). A constant on the left absorbs whatever is on its right: cj f = cj.
These rules cover every pair of the six functions. No product escapes the collection. Conversely, each listed function has been expressed using the generators. Together, those two arguments identify the generated semigroup exactly.
Read a word in the correct direction
Calculate r z r squared. The rightmost r squared acts first, then z resets to zero, then r changes zero to one. The whole function is c1. The calculation works for all three inputs, not just one initial state. It is a statement about transformations.
Compare r squared z r. The rightmost r acts first; z erases its effect; the leftmost r squared sends zero to two. The answer is c2. The two words contain similar ingredients but have different effects.
The identity appeared here as r cubed, even though we did not explicitly include an empty word. That is a property of these generators. A semigroup generated by one nonempty string under concatenation never generates the empty string. Do not infer from this finite example that every generated semigroup automatically contains an identity.
CHAPTER 6 OF 14 · Calculate transformations
6. Distinguish reversible actions from stable actions
Units and information loss
The rotations e, r and r squared have inverses within the six-element monoid. The inverse of r is r squared, and conversely. The constants do not. After c0, all three possible inputs have become zero. Any subsequent function receives the same input regardless of the original state, so it cannot recover all original states.
This is a mathematical information-loss argument. It does not depend on how clever the subsequent function is. If the model retains only the output of c0, the distinction between the original states is gone. Recovery would require extra recorded information, and that means changing the model.
An idempotent element a satisfies a squared = a. Applying a constant transformation twice has the same effect as applying it once, so each cj is idempotent. The identity is idempotent too. Rotation r is not: r squared differs from r. Idempotence concerns repeated identical actions, while invertibility concerns an action that reverses an effect.
A precise retry lesson
In this model, repeating reset-to-zero does not change the final display state after the first reset. That does not prove that a real reset request is harmless to repeat. If each request also increments a counter, emits a message or changes a timestamp, those effects belong in the state. The enriched transformation may no longer be idempotent.
For an original exercise, enlarge the state to (display, count). Define reset by Z(q, n) = (0, n+1). Then Z squared(q, n) = (0, n+2), which differs from Z(q, n). The old model projected away the counter and therefore hid the difference. Both models can be mathematically valid, but they answer different questions.
This is a practical use of semigroup thinking: identify the state on which a claim is supposed to hold. “Safe to repeat” is too vague until the relevant outcomes are explicit. A proof about the displayed value is not a proof about all effects of a request.
CHAPTER 7 OF 14 · Study repetition and structure
7. Understand repeated powers without assuming a group
Finite systems eventually repeat
For an element a of a finite semigroup, the sequence a, a squared, a cubed and so on must repeat a value. If a to the power i equals a to the power j with i less than j, multiplying by further powers preserves equality. Consequently, the powers eventually become periodic. The initial segment need not be periodic from its first term.
Our rotation has period three immediately: r, r squared, e, r, r squared, e. A constant has period one immediately. To see a transient stage, define t on {0, 1, 2} by t = (1, 2, 2). Then t squared = (2, 2, 2), and every later positive power remains that constant. One step moves toward state 2; two steps finish the collapse.
The distinction matters. A finite deterministic model can settle into a fixed behaviour or enter a longer cycle. Finiteness alone does not say which. It also does not tell us how long the initial segment or cycle will be without further analysis.
Check powers as transformations
Starting t at state 2 gives 2 forever, even after one step. Starting at state 0 gives 0, 1, 2, 2 and so on. Observing only the first starting state could tempt us to call t the identity or an idempotent. Neither is correct as a claim about the full transformation.
Compare t squared with t on input 0: the outputs are 2 and 1. That single counterexample disproves idempotence. By contrast, proving two functions equal requires checking all inputs in this finite model or giving a general argument.
For an infinite semigroup, the pigeonhole argument no longer applies. Positive integers under addition provide a simple counterexample: repeated addition of 1 gives 1, 2, 3 and so on without repetition. Any theorem you carry from the finite setting should keep its finiteness assumption attached.
CHAPTER 8 OF 14 · Study repetition and structure
8. Map behaviour while stating what gets forgotten
Homomorphisms preserve combination
A semigroup homomorphism is a map h satisfying h(ab) = h(a)h(b). It lets us calculate in a simpler system while preserving the operation. It need not preserve every distinction. For strings under concatenation, length is a homomorphism into nonnegative integers under addition: the length of uv equals the length of u plus the length of v.
The strings “ab” and “ba” both have length two. Their images are equal even though the strings are different. A length calculation can answer how many symbols a concatenation contains, but cannot reconstruct their order. A useful summary should be judged against the question it is intended to answer.
Taking length modulo three gives another example. A string of length five maps to residue 2, and one of length four maps to residue 1. Concatenation has length nine and maps to 0. Adding the residues modulo three also gives 0. This summary preserves a remainder calculation while forgetting even the exact length.
When a quotient is legitimate
Identifying strings that have the same length modulo three is compatible with concatenation. Replacing either input by another string in the same class does not change the class of the result. This compatibility is what makes the operation on classes well-defined.
By contrast, identify strings merely because they either contain “ab” or do not. The strings “a” and “b” are both in the class that does not contain “ab”. Append “b”: “ab” now contains the pattern, while “bb” does not. The original class alone does not determine the output class. This proposed two-class summary is insufficient for concatenation.
The failure suggests a repair rather than merely a rejection. A richer summary could retain boundary information relevant to creating the pattern across a join. Designing such a summary requires proving its combination rule. The Universal Algebra guide develops the broader relationship between compatible equivalences and quotients.
CHAPTER 9 OF 14 · Study repetition and structure
9. Look for subsets that composition cannot escape
A concrete ideal
In our six-element transformation monoid, the set C = {c0, c1, c2} has a special property: multiplying a member of C by any monoid element on either side stays in C. A subset with this two-sided absorption property is called a two-sided ideal. Here every constant remains constant after composition, though its constant output may change.
For example, r c0 = c1, while c0 r = c0. The individual element c0 is not an absorbing zero for the entire monoid, because left multiplication by r changes it. The set of constants absorbs composition as a set. Confusing these two statements loses useful structure.
There is a direct reason no constant can become a rotation through additional composition. A constant transformation has an image containing one state. Post-composing it still yields at most one output, and pre-composing it changes nothing about its constancy. A rotation has three distinct outputs. The operation cannot restore a distinction already collapsed in this model.
An entry point to deeper structure
Semigroup theory studies the subsets reachable through multiplication and compares elements using the ideals they generate. Green’s relations formalise several of these comparisons. They provide a route beyond merely listing elements or drawing a multiplication table. Their definitions depend on left and right multiplication, so a consistent composition convention becomes especially important.
Tero Harju’s notes on semigroups cover homomorphisms, ideals, presentations and Green’s relations. Use them after you can reproduce the six-element example independently. An unfamiliar abstract definition becomes easier to interpret when you already have a small system on which to test it.
Do not assume every ideal represents a real-world failure state. That interpretation belongs to our information-loss example. In another semigroup, an ideal may have a different mathematical or practical meaning. The algebra supplies a property; the application supplies its interpretation.
CHAPTER 10 OF 14 · Apply and test transfer
10. Connect the algebra to computation carefully
Elements can represent whole input sequences
In a deterministic finite-state machine, each input symbol can act as a transformation of the state set. A sequence of symbols induces a composite transformation. Different sequences may induce the same transformation, which allows behaviour to be studied through a finite collection of effects rather than through infinitely many words.
Our rotation and reset example illustrates this mechanism. Every nonempty word in r and z has one of six effects, despite there being infinitely many such words. A word without a reset is a rotation determined by its length modulo three. A word containing a reset has a constant effect. Under our right-to-left evaluation convention, the rotations to the left of the leftmost reset determine the final constant.
For example, z r r and z both induce c0. The equality concerns final states for every starting state. If we also cared about the intermediate display sequence, these words would no longer be interchangeable observations. Again, the chosen notion of effect controls what equality means.
Computation supports a specified model
The GAP Semigroups documentation lists standard computational constructions, including transformation semigroups and several other families. Such tools can help enumerate examples and investigate structure. Their output is meaningful only after the input generators, representation and multiplication convention have been checked.
A minimal independent checker can represent each function by its output triple. To compute fg, look up g(x) and then f(g(x)) for each x. Maintain a set of known triples; add products until a complete pass adds nothing. Termination is guaranteed here because there are only 3 cubed, or 27, total functions from a three-element set to itself.
The 27 is an upper bound on the possible transformations, not the size of our generated monoid. Our particular generators reach six. Nor does finite termination promise efficient computation for large state sets: a set of n states has n to the power n total self-maps.
CHAPTER 11 OF 14 · Apply and test transfer
11. Recognise neighbouring subjects and boundaries
Discrete composition and continuous evolution
The same associative idea appears in families of time-evolution operators satisfying T(s+t) = T(s)T(t). In analysis, additional conditions such as continuity and appropriate operator domains become essential. Associativity alone does not establish the existence, stability or differentiability of an evolution model.
The existing Operator Theory guide explains the surrounding functional-analysis setting. This article’s finite transformation calculations are a foundation for understanding composition, not a substitute for the analytical hypotheses of continuous-time operator theory.
Another boundary is between a formal operation and an implementation with side effects. Joining immutable strings has an uncomplicated mathematical meaning. A function that mutates shared memory, reads the clock or accesses an external service may require a larger model before composition expresses all relevant behaviour.
Diagnose the exact unsupported move
When a calculation goes wrong, identify the claimed law. If results differ after changing parentheses, inspect associativity or the implementation. If they differ after swapping actions, inspect commutativity. If a repeated action changes the outcome, inspect idempotence. If an undo operation cannot recover a state, inspect invertibility and retained information.
These are different repair jobs. Adding an identity does not make an operation commutative. Recording more state does not automatically make every action reversible. Restricting a domain can break closure. A useful correction should name which property is missing and show a calculation that exposes it.
For learning, keep one counterexample beside each definition. Subtraction exposes nonassociativity; rotation and reset expose noncommutativity; reset exposes noninvertibility; the counter-enriched reset exposes the danger of ignoring side effects. This small collection is more valuable than memorising a hierarchy without knowing where its boundaries lie.
CHAPTER 12 OF 14 · Apply and test transfer
12. Test transfer by changing one assumption
Replace reset with a swap
Keep Q = {0, 1, 2} and the rotation r. Replace z by the swap s = (1, 0, 2). Unlike reset, s is reversible: applying it twice gives the identity. What changes in the generated system?
All compositions of r and s are permutations because compositions of bijections are bijections. No constant transformation can appear. The six transformations e, r, r squared, s, rs and r squared s are distinct: their triples are (0,1,2), (1,2,0), (2,0,1), (1,0,2), (2,1,0) and (0,2,1). There are exactly six permutations of three states, so these exhaust the generated system.
The new system also has six elements, but it is a group. Equal size did not mean equal structure. The original system contained three irreversible constants; the new one contains only reversible transformations. A simple count would have missed the most important change.
Change the observation instead
Return to reset and rotation, but ask only what happens from starting state 0. Can two functions agreeing at 0 be treated as the same element for arbitrary composition? No. The identity e and c0 agree at 0. Yet e r sends 0 to 1, while c0 r sends 0 to 0. Agreement at one selected input is not generally compatible with multiplication.
This exercise explains why equality of transformations was defined on every state. A reduced observation can be useful, but its compatibility must be proved rather than assumed. Before compressing a model, test whether indistinguishable inputs or actions remain indistinguishable after the operations you want to retain.
As a final transfer check, change the state set to four display settings and let rotation cycle through all four. With reset to zero, the same reasoning yields four rotations and four constants, hence eight elements. The number changes; the closure proof follows the same pattern, with exponents and output indices now reduced modulo four.
CHAPTER 13 OF 14 · Resolve questions and practise
13. Answer the questions that commonly cause confusion
Does every semigroup have an identity?
No. Positive integers under addition provide an elementary counterexample. One can adjoin a new identity formally, but the resulting monoid is a new structure. If the original application has no meaningful empty action, the added identity is a mathematical extension rather than an observed operation.
Is a semigroup just an incomplete group?
No. A semigroup has its own valid specification. Irreversible transformations, concatenation and absorbing behaviour are often exactly what needs modelling. Requiring inverses would exclude important examples rather than improve them. Groups describe a more restrictive combination of properties.
Is every idempotent an identity?
No. A constant transformation is idempotent but does not leave every other transformation unchanged. The equation aa = a concerns one element combined with itself. The identity equations ea = a = ae concern every element of the system.
Can I prove associativity by testing random triples?
Random testing can reveal a counterexample, but passing a sample is not a proof for every triple. Exhaustive testing establishes the law for a completely specified finite operation table. A general symbolic argument is preferable when it exposes why the operation works, as function composition does.
Why do books compose functions in different directions?
Different conventions are useful in different settings. Some write functions acting on the right, while this guide uses fg(x) = f(g(x)). Neither convention excuses ambiguity. State yours, translate carefully, and calculate one short example before using a software package or another author’s formulas.
What should I learn before advanced structure theorems?
Be comfortable with sets, functions, equivalence relations and elementary proofs. Then practise small multiplication tables, generated subsemigroups and homomorphisms. A theorem about ideals or Green’s relations becomes much more useful when you can identify the relevant objects in an example without relying on a memorised diagram.
CHAPTER 14 OF 14 · Resolve questions and practise
14. Build a practical learning route
Four sessions with a checkable outcome
In the first session, compare addition, subtraction and concatenation. Write the domain and operation for each, test closure, and explain which laws hold. Include one empty-input case. Your output should be a short classification with reasons, not just a list of algebraic names.
In the second session, reconstruct the six-element rotation-and-reset system. Calculate every function as a triple, prove the closure rules, and evaluate three words without a computer. Then use an independent enumeration to check your results. If the answers disagree, inspect composition direction before assuming the theorem is wrong.
In the third session, investigate information loss. Identify units and idempotents, prove that constants form a two-sided ideal, and explain why a constant cannot be undone within the model. Extend reset with a counter and show precisely which earlier claim fails. This is practice in revising assumptions while preserving valid reasoning.
In the fourth session, work through the changed-context exercises before reading their answers. Replace reset by a swap, change the initial-state observation, and change the size of the display. For each, record what stays the same, what changes and the calculation that decides the matter.
Choose the next branch for a reason
For algebraic depth, continue with the university notes linked above: Gould for a systematic lecture course and Harju for a compact route through structure, quotients and presentations. For computational experiments, use the official GAP Semigroups documentation while checking its conventions. For a concrete data-structure application, return to the rope article and identify the exact associativity argument behind a tree rearrangement.
You are ready to move on when you can distinguish an operation from its representation, grouping from reordering, a stable action from a reversible one, and a useful summary from an invalid quotient. Those distinctions make semigroup theory practical: they tell you which combinations are justified, what information survives, and what must be checked again when the model changes.