A recursive presentation of a group is a one in which there is a finite number of generators and the set of relations is recursively enumerable. I found the following quote in Lyndon-Schupp, chapter II.1:

"This usage may seem a bit strange, but we shall see that if G has a presentation with the set of relations recursively enumerable, then it has another presentation with the set of relations recursive."

It is not clear to me however how one proves it. Does it go through Higman theorem? I.e. one first proves that group with a recursive presentation embeds in a finitely presented group and then one proves that every subgroup of a finitely presented group has a presentation with a recursive set of relations?

And in any case, can one see it somehow directly that having a presentation with a recursively enumerable set of relations (i.e. being recursive) implies having a presentation with a recursive set of relations?


1 Answer 1


The answer is a simple trick. Essentially no group theory is involved.

Suppose that we are given a group presentation with a set of generators, and relations R_0, R_1, etc. that have been given by a computably enumerable procedure. Let us view each relation as a word in the generators that is to become trivial in the group.

Now, the trick. Introduce a new generator x. Also, add the relation x, which means that x will be the identity. Now, let S_i be the relation (R_i)x^(t_i), where t_i is the time it takes for the word R_i to be enumerated in the enumeration algorithm. That is, we simply pad R_i with an enormous number of x's, depending on how long it takes for R_i to be enumerated into the set of relations. Clearly, S_i and R_i are going to give the same group, once we have said that x is trivial, since the enormous number of copies of x in S_i will all cancel out. But the point is that the presentation of the group with this new presentation becomes computably decidable (rather than merely enumerable), because given a relation, we look at it to see if it has the form Sx^t for some t, then we run the enumeration algorithm for t steps, and see if S has been added. If not, then we reject; if so, then we accept.

One can get rid of the extra generator x simply by using the relation R_0 from the original presentation. This gives a computable set of relations in the same generating set that generates the same group.

The essence of this trick is that every relation is equivalent to a ridiculously long relation, and you make the length long enough so that one can check that it really should be there.

  • 1
    $\begingroup$ This is a variant of "Craig's trick" that shows that a first order theory with a r.e. set of axioms has a recursive set of axioms. $\endgroup$ Dec 16, 2009 at 20:24
  • $\begingroup$ Yes, that's right. It is exactly the same idea. $\endgroup$ Dec 16, 2009 at 20:28

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .