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?

  • $\begingroup$ I don't understand your second point. Are you trying to say that every countably-generated group is recursively presentable? (This is false.) $\endgroup$ – user1729 May 12 '20 at 16:06
  • 1
    $\begingroup$ It might be worth mentioning the nice result that if a group has a presentation with a recursively enumerable set of defining relators, then it has one with a recursive set of defining relators. $\endgroup$ – Derek Holt May 12 '20 at 16:55
  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 $$

  1. 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).

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

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

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

  5. See 5.

  • 1
    $\begingroup$ My guess as to the intention in point 2: Some people define "recursive" only for sets of natural numbers. So in order to speak of recursive presentations of groups, they need to represent (= code = Gödel-number) group-theoretic words by natural numbers. That representation should be (intuitively) computable. $\endgroup$ – Andreas Blass May 12 '20 at 16:16
  • 1
    $\begingroup$ I disagree with your answer to point 3. The OP says it is trivial to see that there are recursively presented groups that cannot be finitely presented, and I would say it is so. Just take a free group on an infinite set (even a free abelian group). I don't really see how the fact that every group has an infinite presentation is related. $\endgroup$ – Captain Lama May 12 '20 at 16:18
  • 1
    $\begingroup$ Re: $5$, note that the situation is even better: there is a single finite presented group into which every finitely presented (hence every finitely generated recursively presented) group embeds! $\endgroup$ – Noah Schweber May 12 '20 at 16:24
  • $\begingroup$ @CaptainLama Yes, sorry, I mistakenly read "relators" instead of "generators". $\endgroup$ – user1729 May 12 '20 at 16:26
  • $\begingroup$ @AndreasBlass yes I think you are correct here, the Wikipedia page on presentation of a group mentions Gödel numbering. $\endgroup$ – Single Malt May 13 '20 at 9:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.