Math 2.0

Group theory and generalizations Definition

Krohn–Rhodes theory

Builds on SemigroupTransformation semigroupWreath productSimple groupSubgroup

Definition

The basic notions of Krohn–Rhodes theory are the following. Let SS and TT be semigroups.

  1. SS divides TT if SS is the image of a homomorphism from a subsemigroup of TT onto SS.
  2. Let (X,A)(X, A) and (Y,B)(Y, B) be transformation semigroups. Their wreath product (X,A)≀(Y,B)(X, A) \wr (Y, B) is the transformation semigroup on X×YX \times Y consisting of all maps (x,y)↦(φ(y)(x), b(y))(x, y) \mapsto (\varphi(y)(x), \, b(y)), where b∈Bb \in B and φ ⁣:Y→A\varphi \colon Y \to A is any function.
  3. The flip-flop is the transformation monoid on {0,1}\set{0, 1} consisting of the identity and the two constant maps.
  4. A Krohn–Rhodes decomposition of a finite semigroup SS is a division of SS into the semigroup of an iterated wreath product (X1,A1)≀⋯≀(Xk,Ak)(X_1, A_1) \wr \cdots \wr (X_k, A_k). Each factor (Xi,Ai)(X_i, A_i) is the flip-flop or a finite simple group acting on itself by left multiplication.

Remarks

The set in clause 2 is closed under composition: applying (φ′,b′)(\varphi', b') and then (φ,b)(\varphi, b) gives the map of the same form with the function y↦φ(b′(y))∘φ′(y)y \mapsto \varphi(b'(y)) \circ \varphi'(y) and the element b∘b′b \circ b'. In the wreath product, the coordinate in YY moves on its own, and it controls how the coordinate in XX moves; this is a cascade of two machines.

The Krohn–Rhodes theorem says that every finite semigroup SS has a Krohn–Rhodes decomposition in which each simple group divides SS.

Example: a finite group GG with a composition series has a decomposition into its composition factors, with no flip-flops. For G=ℤ/4ℤG = \Z/4\Z, two copies of ℤ/2ℤ\Z/2\Z suffice, as in the carry rule of a two-digit binary counter.

Non-example: the wreath product of two copies of ℤ/2ℤ\Z/2\Z contains no flip-flop factor, and its semigroup is a finite group of bijections of X×YX \times Y. Every subsemigroup of a finite group is a group, and so is every homomorphic image of a group. So the flip-flop, which is not a group, does not divide it, and every decomposition of a finite semigroup that is not a group needs at least one flip-flop.

Reading path

To understand this page from the ground up, read these 6 pages in order. The foundations come first.

Show the path as a graph
Semigroup, concept, no evidence levelSemigroupconceptSimple group, concept, no evidence levelSimple groupconceptSubgroup, concept, no evidence levelSubgroupconceptTransformation semigroup, concept, no evidence levelTransformation semigr…conceptWreath product, concept, no evidence levelWreath productconceptKrohn–Rhodes theory, definition, no evidence levelKrohn–Rhodes theorydefinition
Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.
  • no evidence level
  1. Semigroup concept
  2. Simple group concept
  3. Subgroup concept
  4. Transformation semigroup concept
  5. Wreath product concept
  6. Krohn–Rhodes theory definition

Further reading

  1. Web https://en.wikipedia.org/wiki/Krohn–Rhodes_theory
About this page
TagGYR1XYFEZB
URIm2://GYR1XYFEZB
Kinddefinition
WritingW0 stub
MSC20M35, 68Q70
DefinesKrohn–Rhodes theory
UsesSemigroup, Transformation semigroup, Wreath product, Simple group, Subgroup
Changed2 November 2026

Markdown · JSON · Edit on GitHub

What this page needs for W1

  • an inventory row: the row of the inventory that the node accounts for (0 of 1)
  • a source with a locator (0 of 1)

The writing levels say how complete the text of a page is. They do not measure its truth.

What links here

No page links to this page yet.