Recursive presentations

Question

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?

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.

Answer 2

Checking the book of J. Rotman, An introduction to the theory of groups (4th edition), I found this issue discussed in Chapter 12, page 451. See Exercise 12.12 and Exercise 12.13. In particular, the idea used above by Joel David Hamkins is mentioned as a hint to Exercise 12.12.

However, it still is interesting to find the part in Lyndon-Schupp book in "which we shall see":

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

P.S. The term "positive word" mentioned by Rotman means that the relation shell not include negative powers of generators. See page 349.