Although the notation ⟨S | R⟩ used in this article for a presentation is now the most common, earlier writers used different variations on the same format. Such notations include the following:
Finitely presented groups[edit]
A presentation is said to be finitely generated if S is finite and finitely related if R is finite. If both are finite it is said to be a finite presentation. A group is finitely generated (respectively finitely related, finitely presented) if it has a presentation that is finitely generated (respectively finitely related, a finite presentation). A group which has a finite presentation with a single relation is called a one-relator group.
Recursively presented groups[edit]
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) f : FS → 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 FS 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.[2] 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.
History[edit]
One of the earliest presentations of a group by generators and relations was given by the Irish mathematician William Rowan Hamilton in 1856, in his icosian calculus – a presentation of the icosahedral group.[3] The first systematic study was given by Walther von Dyck, student of Felix Klein, in the early 1880s, laying the foundations for combinatorial group theory.[4]
Suppose G has presentation ⟨S | R⟩ and H has presentation ⟨T | Q⟩ with S and T being disjoint. Then
Deficiency[edit]
The deficiency of a finite presentation ⟨S | R⟩ is just |S| − |R| and the deficiency of a finitely presented group G, denoted def(G), is the maximum of the deficiency over all presentations of G. The deficiency of a finite group is non-positive. The Schur multiplicator of a finite group G can be generated by −def(G) generators, and G is efficient if this number is required.[7]