Editing Presentation of a group (section)

== Recursively presented groups ==
If ''S'' is indexed by a set ''I'' consisting of all the natural numbers '''N''' or a finite subset of them, then it is easy to set up a simple one to one coding (or [[Gödel numbering]]) {{nowrap|''f'' : ''F<sub>S</sub>'' → '''N'''}} from the free group on ''S'' to the natural numbers, such that we can find algorithms that, given ''f''(''w''), calculate ''w'', and vice versa. We can then call a subset ''U'' of ''F<sub>S</sub>'' [[recursive set|recursive]] (respectively [[recursively enumerable]]) if ''f''(''U'') is recursive (respectively recursively enumerable). If ''S'' is indexed as above and ''R'' recursively enumerable, then the presentation is a '''recursive presentation''' and the corresponding group is '''recursively presented'''. This usage may seem odd, but it is possible to prove that if a group has a presentation with ''R'' recursively enumerable then it has another one with ''R'' recursive.

Every finitely presented group is recursively presented, but there are recursively presented groups that cannot be finitely presented.  However a theorem of [[Graham Higman]] states that a finitely generated group has a recursive presentation if and only if it can be embedded in a finitely presented group.<ref>{{Cite journal |date=1961-08-08 |title=Subgroups of finitely presented groups |url=https://royalsocietypublishing.org/doi/10.1098/rspa.1961.0132 |journal=Proceedings of the Royal Society of London. Series A. Mathematical and Physical Sciences |language=en |volume=262 |issue=1311 |pages=455–475 |doi=10.1098/rspa.1961.0132 |bibcode=1961RSPSA.262..455H |s2cid=120100270 |issn=0080-4630 |last1=Higman |first1=G. }}</ref> From this we can deduce that there are (up to isomorphism) only [[countably]] many finitely generated recursively presented groups. [[Bernhard Neumann]] has shown that there are [[uncountably]] many non-isomorphic two generator groups. Therefore, there are finitely generated groups that cannot be recursively presented.