Finitely Presented expansions of semigroups,
algebras, and groups
Bakh Khoussainov
joint work with Denis Hirschfeldt (University of Chicago)and Alexei Miasnikov (Stevens Institute)

May 14, 2013

1 / 46
Bakh Khoussainov

Finitely Presented expansions of semigroups, algebras, and group

Plan

Finitely presented universal algebras
The Bergstra-Tucker problem
The NFP theorem
Applications of the NFP theorem

2 / 46
Bakh Khoussainov

Finitely Presented expansions of semigroups, algebras, and groupUniversal algebras

Definition
A universal algebra A is a tuple (A; f1 , . . . , fn , c1 , . . . , cm ),where
A 6= ; is the domain of A,
Each fi is a total function Aki ! A, a basic operation of A.
Each cj is a distinguished element of A.
The signature of A is the sequence f1 , . . . , fn , c1 , . . . , cm .

3 / 46
Bakh Khoussainov

Finitely Presented expansions of semigroups, algebras, and group

TermsDefinition
Each constant symbol and a variable x is a term. If t1 , . . . , tk
are terms and f is function symbol of arity k then theexpression fi (t1 , . . . , tk ) is a term.
Examples of terms are:1f (f (x, y ), z), f (x, f (y , z)), f (x, g(x)), f (f (x, a), f (a, a)), and2a, f (a, b), f (a, f (b, g(a))), f (g(a), a).

Terms in Example (2) are called ground terms.

4 / 46
Bakh Khoussainov

Finitely Presented expansions of semigroups, algebras, and group

The term algebra TG

The term algebra TG is defined as follows:1

The domain is TG , the set of all ground terms.

2

For a basic operation symbol f of arity k , its value on the
k -tuple (t1 , . . . , tk ) of ground terms is the ground termf (t1 , . . . , tk ).

5 / 46
Bakh Khoussainov

Finitely Presented expansions of semigroups, algebras, and group

The word problem
Let A be a universal algebra generated by the constants. Then
there exists a homomorphism
h : TG ! A.
Definition
The word problem for A is the set
WP(A) = {(p, q) | h(p) = h(q)}.
Definition
The universal algebra A is computably enumerable if WP(A)is a computably enumerable set.
6 / 46
Bakh Khoussainov

Finitely Presented expansions of semigroups, algebras, and group

The word problem
Let A be a universal algebra generated by the constants. Then
there exists a homomorphism
h : TG ! A.
Definition
The word problem for A is the set
WP(A) = {(p, q) | h(p) = h(q)}.
Definition
The universal algebra A is computably enumerable if WP(A)is a computably enumerable set.
7 / 46
Bakh Khoussainov

Finitely Presented expansions of semigroups, algebras, and groupEquational specifications

Definition
An equation is of the form t = t 0 , where t and t 0 are terms. An
equational specification S is a finite set of equations.
Examples:GroupAxioms, RingAxioms, BooleanAlgebraAxioms.

8 / 46
Bakh Khoussainov

Finitely Presented expansions of semigroups, algebras, and group

Finitely presented universal algebras
Let S be an equational specification. Consider:
E(S) = {(t, p) | t, p 2 TG and the equality t = p can be
deduced from the equations in S}.
Define:T (S) = TG /E(S).
Definition
A universal algebra A is finitely presented if there is an S
such that A is isomorphic to T (S).

9 / 46
Bakh Khoussainov

Finitely Presented expansions of semigroups, algebras, and group

Finitely presented universal algebras
Let S be an equational specification. Consider:
E(S) = {(t, p) | t, p 2 TG and the equality t = p can be
deduced from the equations in S}.
Define:T (S) = TG /E(S).
Definition
A universal algebra A is finitely presented if there is an S
such that A is isomorphic to T (S).

10 / 46
Bakh Khoussainov

Finitely Presented expansions of semigroups, algebras, and groupProperties of T (S)A computability-theoretic property:
T (S) is a c.e. algebra.
Algebraic and logical properties:
T (S) is finitely generated and satisfies S.

If A |= S and A is finitely generated by the constants thenA is a homomorphic image of T (S).
T (S) is unique.

11 / 46
Bakh Khoussainov

Finitely Presented expansions of semigroups, algebras, and groupC.e. does not imply f.p.

Examples:The universal algebra (!; S, 2x , 0) is not finitely presented.
(Baumslag) The restricted wreath product of any non-trivialgroup G by Z is not finitely presented. In particular, therestricted wreath product of Z2 by Z is not finitely
presented (The lamplighter group).

12 / 46
Bakh Khoussainov

Finitely Presented expansions of semigroups, algebras, and group

Making (!; S, 2x , 0) finitely presented
Consider the following expansion of (!; S, 2x , 0):(!; S, 2x , 0, +, ⇥).
This expansion is finitely presented. The presentation is this:x + 0 = x, x + S(y ) = S(x + y )x ⇥ 0 = 0, x ⇥ S(0) = x, x ⇥ S(y ) = x ⇥ y + x,
20 = S(0), 2x+S(0) = 2x ⇥ S(S(0)).

13 / 46
Bakh Khoussainov

Finitely Presented expansions of semigroups, algebras, and group

Making (!; S, 2x , 0) finitely presented
Consider the following expansion of (!; S, 2x , 0):(!; S, 2x , 0, +, ⇥).
This expansion is finitely presented. The presentation is this:x + 0 = x, x + S(y ) = S(x + y )x ⇥ 0 = 0, x ⇥ S(0) = x, x ⇥ S(y ) = x ⇥ y + x,
20 = S(0), 2x+S(0) = 2x ⇥ S(S(0)).

14 / 46
Bakh Khoussainov

Finitely Presented expansions of semigroups, algebras, and group

The theorem of Bergstra and Tucker

Definition
An expansion of A = (A; f1 , . . . , fn ) is
A0 = (A; f1 , . . . , fn , h1 , . . . , hk ), where all h are new operations.
Theorem (Bergstra-Tucker, 1980)
Every computably enumerable universal algebra with decidable
word problem has finitely presented expansion.

15 / 46
Bakh Khoussainov

Finitely Presented expansions of semigroups, algebras, and group

Bergstra and Tucker problem

In the 1980s Bergstra and Tucker, and independently
Goncharov, posed the following question:
Does every finitely generated computably
enumerable universal algebra possess a finitely
presented expansion?
Theorem (Kassymov (1987), Khoussainov (1994))
There exist finitely generated c.e. universal algebras that fail topossess finitely presented expansions.

16 / 46
Bakh Khoussainov

Finitely Presented expansions of semigroups, algebras, and group

Bergstra and Tucker problem

In the 1980s Bergstra and Tucker, and independently
Goncharov, posed the following question:
Does every finitely generated computably
enumerable universal algebra possess a finitely
presented expansion?
Theorem (Kassymov (1987), Khoussainov (1994))
There exist finitely generated c.e. universal algebras that fail topossess finitely presented expansions.

17 / 46
Bakh Khoussainov

Finitely Presented expansions of semigroups, algebras, and group

Bergstra and Tucker problem revisited

Do there exist standard finitely generated algebraic
structures that fail to posses finitely presented
expansions?
More precisely, do there exist finitely generated c.e.
semigroups, groups, and algebras without finitely
presented expansions?

18 / 46
Bakh Khoussainov

Finitely Presented expansions of semigroups, algebras, and groupEffectively infinite universal algebras

Definition
A universal algebra A is effectively infinite if there exists analgorithm that enumerates a sequence t0 , t1 , . . . of ground terms
such that they all represent pairwise distinct elements of A.

19 / 46
Bakh Khoussainov

Finitely Presented expansions of semigroups, algebras, and group

Non-effectively infinite universal algebras
If A is not effectively infinite then:12
3

Every expansion of A is not effectively infinite.

All infinite sub-algebras of A are not effectively infinite.
For every term t(x) and element a of A, the sequencea, t(a), t(t(a)), . . .
is eventually periodic. In particular if a group is noteffectively infinite then it is a periodic group.

4

All infinite homomorphic images of A are not effectively
infinite.

20 / 46
Bakh Khoussainov

Finitely Presented expansions of semigroups, algebras, and group

Non-effectively infinite semigroups
Theorem (Khoussainov, Hirschfeldt)
There exists a c.e., f.g. and non effectively infinite semigroup.
Proof. Consider A = ({x, y }? ; ·). Take Z ✓ {x, y }? , anddefine:R(Z ) = {u | u contains a subword from Z }.
The relation ⌘(Z )(u, v ) 2 ⌘(Z ) $ u = v _ (u 2 R(Z )&v 2 R(Z )).
is a congruence relation on A. Set:
A(Z ) = A/⌘(Z ).
21 / 46
Bakh Khoussainov

Finitely Presented expansions of semigroups, algebras, and group

Non-effectively infinite semigroups
Theorem (Khoussainov, Hirschfeldt)
There exists a c.e., f.g. and non effectively infinite semigroup.
Proof. Consider A = ({x, y }? ; ·). Take Z ✓ {x, y }? , anddefine:R(Z ) = {u | u contains a subword from Z }.
The relation ⌘(Z )(u, v ) 2 ⌘(Z ) $ u = v _ (u 2 R(Z )&v 2 R(Z )).
is a congruence relation on A. Set:
A(Z ) = A/⌘(Z ).
22 / 46
Bakh Khoussainov

Finitely Presented expansions of semigroups, algebras, and groupProof of the theorem

Lemma
There exists a simple subset Z ✓ {x, y }? such that1

The semigroup A(Z ) = A/⌘(Z ) is infinite.

2

For each n, rn the number of strings in Z of length n isbounded by n and r0 = r1 = . . . = r5 = 0.

The lemma is proved by a careful Post type of construction of asimple set. We use Joe Miller’s lemma.
This lemma proves the theorem.

23 / 46
Bakh Khoussainov

Finitely Presented expansions of semigroups, algebras, and groupResidually finite universal algebras

Definition
A universal algebra A from a class K is residually finite if for
any two distinct elements a and b of A, there exists a
homomorphism of A onto a finite universal algebra from theclass K such that the images of a and b under thehomomorphism are distinct.

24 / 46
Bakh Khoussainov

Finitely Presented expansions of semigroups, algebras, and groupSeparation Lemma

Lemma
Let A = TG /E be a residually finite universal algebra. For all
distinct elements x and y of A there exists a set S(x, y ) ✓ TG
such that each of the following is satisfied:
1

S(x, y ) is a computable set.

2

x 2 S(x, y ) and y 62 S(x, y ).

3

The set S(x, y ) is a union of E-equivalence classes.

25 / 46
Bakh Khoussainov

Finitely Presented expansions of semigroups, algebras, and group

Non-effective infinity and residual finiteness

Theorem (Khoussainov and Miasnikov)
Let A = TG /E be a f.g. and c.e. universal algebra.
If A is residually finite and non-effectively infinite, then all c.e.
expansions of A are residually finite.
In other words, residual finiteness is invariant under expansions
if non-effective infinity is assumed.

26 / 46
Bakh Khoussainov

Finitely Presented expansions of semigroups, algebras, and group

Ingredients of the proof I

Proof. Let A0 be a c.e. expansion of A.

Set C(a,b) be the minimal congruence relation generated by
the pair (a, b).
There exists a procedure that given (a, b) extracts analgorithm generating C(a,b) .
Select x 6= y from A0 . Want to show that we candistinguish them in a finite homomorphic image of A0 .

27 / 46
Bakh Khoussainov

Finitely Presented expansions of semigroups, algebras, and group

Ingredients of the proof II
Define E(x,y ) :(a, b) 2 E(x,y ) iff 8u 2 S(x, y ) 8v 62 S(x, y )((u, v ) 62 C(a,b) ).
Lemma
The binary relation E(x,y ) is a congruence relation of A0 .
This is based on the following two lemmas (by Malcev):
1

2(u, v ) 2 C(a,b) iff 9e0 , . . . , en 2 A and 9t0 , . . . , tn 1 such thatu = e0 , v = en , and {ei , ei+1 } = {ti (a), ti (b)} for i  n 1.
E is a congruence of A iff all algebraic terms respect E.

28 / 46
Bakh Khoussainov

Finitely Presented expansions of semigroups, algebras, and group

Ingredients of the proof II
Define E(x,y ) :(a, b) 2 E(x,y ) iff 8u 2 S(x, y ) 8v 62 S(x, y )((u, v ) 62 C(a,b) ).
Lemma
The binary relation E(x,y ) is a congruence relation of A0 .
This is based on the following two lemmas (by Malcev):
1

2(u, v ) 2 C(a,b) iff 9e0 , . . . , en 2 A and 9t0 , . . . , tn 1 such thatu = e0 , v = en , and {ei , ei+1 } = {ti (a), ti (b)} for i  n 1.
E is a congruence of A iff all algebraic terms respect E.

29 / 46
Bakh Khoussainov

Finitely Presented expansions of semigroups, algebras, and group

Ingredients of the proof III

Lemma
The relation E(x,y ) is a co-c.e.congruence relation.
The transversal of every co-c.e. equivalence relation is a c.e.
set. Hence, the transversal must be a finite set.
Thus, E(x, y ) has a finite index. Therefore A0 /E(x, y ) is thedesired homomorphic image.

30 / 46
Bakh Khoussainov

Finitely Presented expansions of semigroups, algebras, and group

Ingredients of the proof III

Lemma
The relation E(x,y ) is a co-c.e.congruence relation.
The transversal of every co-c.e. equivalence relation is a c.e.
set. Hence, the transversal must be a finite set.
Thus, E(x, y ) has a finite index. Therefore A0 /E(x, y ) is thedesired homomorphic image.

31 / 46
Bakh Khoussainov

Finitely Presented expansions of semigroups, algebras, and group

The NFP theorem
Theorem (Khoussainov and Miasnikov)
If A is an infinite, finitely generated, computably enumerable,
non-effectively infinite and residually finite universal algebrathen no expansion of A is finitely presented.
Proof.
Assume A0 is a f.p. expansion of A. Then A0 is residually finite
as we have proved. The next lemma implies the theorem:
Lemma (Malcev)
If a finitely presented algebra is residually finite then the word
problem for the algebra is decidable.

32 / 46
Bakh Khoussainov

Finitely Presented expansions of semigroups, algebras, and group

The NFP theorem
Theorem (Khoussainov and Miasnikov)
If A is an infinite, finitely generated, computably enumerable,
non-effectively infinite and residually finite universal algebrathen no expansion of A is finitely presented.
Proof.
Assume A0 is a f.p. expansion of A. Then A0 is residually finite
as we have proved. The next lemma implies the theorem:
Lemma (Malcev)
If a finitely presented algebra is residually finite then the word
problem for the algebra is decidable.

33 / 46
Bakh Khoussainov

Finitely Presented expansions of semigroups, algebras, and groupApplication of the NFP to semigroups

Corollary
There exists a finitely generated, non-effectively infinite,
residually finite and computably enumerable semigroup thatfails to possess finitely presented expansions.
Proof.
It suffices to note that the semigroup A(Z ) constructed above isresidually finite.

34 / 46
Bakh Khoussainov

Finitely Presented expansions of semigroups, algebras, and groupFree algebras

Consider the algebra of polynomials over the field k :F = k {x1 , . . . , xd }, d > 1.
Represent F as

F0

F1

F2

....

Write each polynom p in F as the sum of homogeneouspolynomials:
p = p1 + p2 + . . . + pk ,where p1 2 Fn1 , . . ., pk 2 Fnk and n1 < n1 < . . . < nk .

35 / 46
Bakh Khoussainov

Finitely Presented expansions of semigroups, algebras, and group

Homogeneous ideals
Definition
A ideal is homogeneous if it is generated by homogeneouspolynomials.
Lemma
An ideal I of F is homogenous if and only if it contains
homogeneous components of all of its members.
Lemma
If I is homogeneous then A = F/I can be represented as
A0

A1

A2

...,

where An = (Fn + I)/I for all n.
36 / 46
Bakh Khoussainov

Finitely Presented expansions of semigroups, algebras, and group

Golod-Shafarevich Theorem
Let I be an ideal generated by homogeneous polynomials:
h1 , h2 , h3 , . . . , where 2  deg(h1 )  deg(h2 )  . . .
Set: rn = #(polynomials of degree n in this sequence).
Theorem (Golod-Shafarevich Theorem)
Assume that for some ✏ such that 0 < ✏  d/2 we have thefollowing inequality:rn  ✏2 (d2✏)n 2 for all n

2.

Then the algebra A = F/I has an infinite dimension.

37 / 46
Bakh Khoussainov

Finitely Presented expansions of semigroups, algebras, and group

Golod-Shafarevich Theorem
Let I be an ideal generated by homogeneous polynomials:
h1 , h2 , h3 , . . . , where 2  deg(h1 )  deg(h2 )  . . .
Set: rn = #(polynomials of degree n in this sequence).
Theorem (Golod-Shafarevich Theorem)
Assume that for some ✏ such that 0 < ✏  d/2 we have thefollowing inequality:rn  ✏2 (d2✏)n 2 for all n

2.

Then the algebra A = F/I has an infinite dimension.

38 / 46
Bakh Khoussainov

Finitely Presented expansions of semigroups, algebras, and groupConstruction of an ideal H
Let W0 , W1 , . . . be an enumeration of all c.e. subsets of F.
Uniformly on i proceed as follows. Wait for two polynomials f
and g that appear in Wi such that:
1

Both f and g are of the form f = f1 + h1 , g = g1 + h2 , and
f1 = g1 .

2

The degrees of all homogeneous components occurring in
h1 and h2 are greater than i + 10.

Put the homogeneous components present in h1 and h2 into H.
Set I =< H > and consider the algebra
A = F/I.

39 / 46
Bakh Khoussainov

Finitely Presented expansions of semigroups, algebras, and groupConstruction of an ideal H
Let W0 , W1 , . . . be an enumeration of all c.e. subsets of F.
Uniformly on i proceed as follows. Wait for two polynomials f
and g that appear in Wi such that:
1

Both f and g are of the form f = f1 + h1 , g = g1 + h2 , and
f1 = g1 .

2

The degrees of all homogeneous components occurring in
h1 and h2 are greater than i + 10.

Put the homogeneous components present in h1 and h2 into H.
Set I =< H > and consider the algebra
A = F/I.

40 / 46
Bakh Khoussainov

Finitely Presented expansions of semigroups, algebras, and groupApplication of the NFP theorem to algebras
Theorem (Khoussainov and Miasnikov)
The algebra A = F/I is finitely generated, infinite, computably
enumerable, non-effectively infinite, residually finite, andnil-algebra.
For the proof one needs to check that the conditions of theGolod-Shafarevich theorem are satisfied. Hence,
Theorem (Khoussainov and Miasnikov)
There exists a finitely generated, non-effectively infinite,
residually finite and computably enumerable algebra that fails topossess finitely presented expansions.

41 / 46
Bakh Khoussainov

Finitely Presented expansions of semigroups, algebras, and groupApplication of the NFP theorem to algebras
Theorem (Khoussainov and Miasnikov)
The algebra A = F/I is finitely generated, infinite, computably
enumerable, non-effectively infinite, residually finite, andnil-algebra.
For the proof one needs to check that the conditions of theGolod-Shafarevich theorem are satisfied. Hence,
Theorem (Khoussainov and Miasnikov)
There exists a finitely generated, non-effectively infinite,
residually finite and computably enumerable algebra that fails topossess finitely presented expansions.

42 / 46
Bakh Khoussainov

Finitely Presented expansions of semigroups, algebras, and groupApplication of the NFP theorem to groups
Theorem (Khoussainov and Miasnikov)
For every prime number p there exists a finitely generated,
non-effectively infinite, residually finite and computably
enumerable p-group that fails to possess finitely presented
expansions.
Proof. Consider the muliplicative substructure G of A
generated by 1 + x and 1 + y . One can show the following:1

G is infinite.

2

G is a group.

3

G is residually finite.

The group G is non-effectively infinite finite. Apply the NFP
theorem.
43 / 46
Bakh Khoussainov

Finitely Presented expansions of semigroups, algebras, and groupApplication of the NFP theorem to groups
Theorem (Khoussainov and Miasnikov)
For every prime number p there exists a finitely generated,
non-effectively infinite, residually finite and computably
enumerable p-group that fails to possess finitely presented
expansions.
Proof. Consider the muliplicative substructure G of A
generated by 1 + x and 1 + y . One can show the following:1

G is infinite.

2

G is a group.

3

G is residually finite.

The group G is non-effectively infinite finite. Apply the NFP
theorem.
44 / 46
Bakh Khoussainov

Finitely Presented expansions of semigroups, algebras, and groupIs being non-effectively infinite essential?

Theorem (Khoussainov and Miasnikov)
There exists a finitely generated, residually finite, computably
enumerable and effectively infinite algebra that fails to possess
finitely presented expansions.
Let I be the homogenious ideal generated by set Z constructed
for the semigroup. The algebra A = F/I is the desired algebra.

45 / 46
Bakh Khoussainov

Finitely Presented expansions of semigroups, algebras, and group

Open questions

1

Does there exist effectively infinite groups that fail topossess finitely presented expansions?

2

Are there examples of c.e. finitely generated groups,
semigroups, and algebras that fail to possessquasi-equational presentations in all expansions?

3

Does there exist a finitely presented universal algebra
which is ML-random?

4

Does there exist an effectively infinite and ML-random
algebra?
46 / 46
Bakh Khoussainov

Finitely Presented expansions of semigroups, algebras, and group