Definition
Let S be a set and let FS be the free group on S. Let R be a set of words on S, so R naturally gives a subset of FS. To form a group with presentation <S|R>, the idea is to take FS quotient by the smallest normal subgroup such that each element of R gets identified with the identity. Note that R might not be a subgroup, let alone a normal subgroup of FS, so we cannot take a quotient by R. The solution is to take the normal closure N of R in FS. The group <S|R> is then defined as the quotient group
The elements of S are called the generators of <S|R> and the elements of R are called the relators. A group G is said to have the presentation <S|R> if G is isomorphic to <S|R>.
It is a common practice to write relators in the form = where and are words on . What this means is that . This has the intuitive meaning that the images of x and y are supposed to be equal in the quotient group. Thus e.g. in the list of relators is equivalent with . Another common shorthand is to write for a commutator .
A presentation is said to be finitely generated if is finite and finitely related if 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).
If is indexed by a set consisting of all the natural numbers or a finite subset of them, then it is easy to set up a simple one to one coding (or Gödel numbering) from the free group on to the natural numbers, such that we can find algorithms that, given, calculate, and vice versa. We can then call a subset of recursive (respectively recursively enumerable) if is recursive (respectively recursively enumerable). If is indexed as above and 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 recursively enumerable then it has another one with recursive.
For a finite group, the multiplication table provides a presentation. We take to be the elements of and to be all words of the form, where is an entry in the multiplication table. A presentation can then be thought of as a generalization of a multiplication table.
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. 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.
Read more about this topic: Presentation Of A Group
Famous quotes containing the word definition:
“Perhaps the best definition of progress would be the continuing efforts of men and women to narrow the gap between the convenience of the powers that be and the unwritten charter.”
—Nadine Gordimer (b. 1923)
“The very definition of the real becomes: that of which it is possible to give an equivalent reproduction.... The real is not only what can be reproduced, but that which is always already reproduced. The hyperreal.”
—Jean Baudrillard (b. 1929)
“No man, not even a doctor, ever gives any other definition of what a nurse should be than this—”devoted and obedient.” This definition would do just as well for a porter. It might even do for a horse. It would not do for a policeman.”
—Florence Nightingale (1820–1910)