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?



Recursive presentations
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.


