The four semigroups without a finite basis
Every semigroup of order at most six has a finite identity basis except four, all of order six: L, B₂¹, A₂ᵍ and A₂¹ (Lee, Li and Zhang 2012); every semigroup of order at most five is finitely based (Trahtman 1983). Each Lean proof exhibits infinitely many identities of the semigroup, one for every n, and a property of words that separates the two sides of the n-th identity and survives every derivation step with an identity in fewer than n variables. So no finite set of identities derives them all. None of the four, and none of their transposes, lies in any of the 681 varieties generated by the finitely based semigroups of orders one to six. Each of the four is self-dual and generates a variety of its own, V[6, 3843], V[6, 8564], V[6, 8878] and V[6, 13747]; three identities tell them apart (Names).
L = [6, 3843]
| · | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
| 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 2 | 1 | 1 | 1 | 1 | 1 | 2 |
| 3 | 1 | 1 | 1 | 1 | 1 | 3 |
| 4 | 1 | 1 | 2 | 1 | 4 | 2 |
| 5 | 1 | 1 | 3 | 1 | 5 | 3 |
| 6 | 1 | 2 | 2 | 4 | 4 | 6 |
Lee's semigroup L. For every n,
x y₁²⋯yₙ² x ≈ x yₙ²⋯y₁² x
In a word equal in L to the left side the squares stay blocks, in the forward or in the reverse order, and no derivation step with an identity in fewer variables passes from one order to the other.
W. T. Zhang and Y. F. Luo (2011). Lean: SemigroupBasis.Examples.LeeL.s6_3843_nonfinitelyBased. Its variety: V[6, 3843].
B₂¹ = [6, 8564]
| · | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
| 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 2 | 1 | 1 | 4 | 1 | 2 | 2 |
| 3 | 1 | 5 | 1 | 3 | 1 | 3 |
| 4 | 1 | 2 | 1 | 4 | 1 | 4 |
| 5 | 1 | 1 | 3 | 1 | 5 | 5 |
| 6 | 1 | 2 | 3 | 4 | 5 | 6 |
The Brandt monoid B₂¹, obtained from B₂ by adjoining an identity. For every n,
x y₁⋯yₙ x yₙ⋯y₁ ≈ x yₙ⋯y₁ x y₁⋯yₙ
A pattern in the occurrences of the letters survives every derivation step with an identity in fewer variables; the argument uses that xytyx and xtyxy are isoterms, equal in B₂¹ only to themselves.
P. Perkins (1969), in the reconstruction of M. V. Sapir (1988). Lean: SemigroupBasis.Nonfinite.B2One.s6_8564_nonfinitelyBased. Its variety: V[6, 8564].
A₂ᵍ = [6, 8878]
| · | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
| 1 | 1 | 1 | 3 | 1 | 1 | 1 |
| 2 | 1 | 1 | 3 | 1 | 2 | 4 |
| 3 | 3 | 3 | 1 | 3 | 3 | 3 |
| 4 | 1 | 2 | 3 | 4 | 2 | 4 |
| 5 | 1 | 1 | 3 | 1 | 5 | 6 |
| 6 | 1 | 5 | 3 | 6 | 5 | 6 |
The semigroup A₂ᵍ, obtained from A₂ by adjoining an element g. For every n,
(x₁²⋯xₙ²)² ≈ (x₁²⋯xₙ²)³
The identities of A₂ᵍ are read off a directed graph of the word together with a parity; the parity with which a word winds around the cycle x₁ → ⋯ → xₙ → x₁ survives every derivation step with an identity in fewer variables.
A winding-parity argument on cycle words; that A₂ᵍ has no finite basis is in Lee, Li and Zhang (2012). Lean: SemigroupBasis.Examples.AC2.s6_8878_nonfinitelyBased. Its variety: V[6, 8878].
A₂¹ = [6, 13747]
| · | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
| 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 2 | 1 | 1 | 1 | 2 | 2 | 3 |
| 3 | 1 | 2 | 3 | 2 | 3 | 3 |
| 4 | 1 | 1 | 1 | 4 | 4 | 6 |
| 5 | 1 | 2 | 3 | 4 | 5 | 6 |
| 6 | 1 | 4 | 6 | 4 | 6 | 6 |
The monoid A₂¹, obtained from A₂ by adjoining an identity. For every n,
X y X′ y X ≈ X y X′ y X y X′ y X, with X = x₁⋯xₙ and X′ its reverse
No derivation step with an identity in fewer variables changes the left side at all.
A. N. Trahtman (1987); M. V. Sapir (1988). Lean: SemigroupBasis.Examples.A2One.s6_13747_nonfinitelyBased. Its variety: V[6, 13747].