SemiBase

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]

·123456
1111111
2111112
3111113
4112142
5113153
6122446

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]

·123456
1111111
2114122
3151313
4121414
5113155
6123456

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]

·123456
1113111
2113124
3331333
4123424
5113156
6153656

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]

·123456
1111111
2111223
3123233
4111446
5123456
6146466

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].