The four semigroups without a finite basis
Every semigroup of order six has a finite identity basis except four: L, B₂¹, A₂ᵍ and A₂¹ (Lee, Li and Zhang 2012). 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 lies in any of the 505 varieties generated by the finitely based semigroups of order six.
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
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₂¹. 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
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
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