Intuition of recursively presented groups

Question

I am trying to understand the intuition behind recursively presented groups, and as a corollary why they are important or useful.

Here are some questions that hopefully will aid understanding, of which the first is not specific to recursively presented groups.

1. For a group that needs to have an infinite number of relations (that is excluding superfluous relations that can be obtained by other included relations) it is necessary for it to have an infinite number of generators?

2. Informally, it seems that a recursively presented group can have countably infinite generators, and the map between the natural numbers to the generators should be a recursive set, and the same must apply to the relations. Is this correct?

3. Every finitely presented group is recursively presented, but there are recursively presented groups that cannot be finitely presented. This seems trivial since if the recursively presented group has an infinite set of generators then it cannot be finitely presented?

4. The group of integers under addition is a recursively presented group but not a finitely presented group?

5. What other good (simple / important) examples are there of recursively presented groups, with particular interest in those that will aid in understanding the concept?

6. Why are recursively presented groups important, is it because informally anything larger than them will more likely be intractable in a computability theory setting?

Answer 1

1. No. There are finitely generated groups which are not finitely presentable. For example, all of the answers to this question are finitely generated, recursively presentable groups which are not finitely presentable. [Edit: actually, one is finitely presentable.] For example, the following group is finitely generated but not finitely presentable:

$$ G=\langle a, b, t; tab^iat^{-1}=ba^ib, i\in\mathbb{Z}\rangle $$

2. I'm not sure I understand your point here... Are you trying to say that every countably-generated group is recursively presentable? This is false; there are countably many finitely generated recursively presented groups (why?), but uncountably many finitely generated groups (I believe that this is first due to B.H. Neumann (who proved that there is a continuum of two-generated groups), but I'm having a hard time tracking down the reference).

3. Yes, this is trivial. However, it is not trivial if we additionally assume that the groups are finitely generated (see 1).

4. No. The group of integers under addition is finitely presentable. For example, $\langle a\mid -\rangle$ and $\langle a, b\mid b\rangle$ are both finite presentations of this group.

5. Higman proved that a finitely generated group is recursively presentable if and only if it embeds as a subgroup of a finitely presented group. This gives a wealth of examples! This result is called "Higman's embedding theorem", and is proved at the end of Rotman's book "An Introduction to the Theory of Groups" (see also Lyndon and Schupp's book "Combinatorial group theory").

6. See 5.