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:
“... we all know the wag’s definition of a philanthropist: a man whose charity increases directly as the square of the distance.”
—George Eliot [Mary Ann (or Marian)
“... if, as women, we accept a philosophy of history that asserts that women are by definition assimilated into the male universal, that we can understand our past through a male lens—if we are unaware that women even have a history—we live our lives similarly unanchored, drifting in response to a veering wind of myth and bias.”
—Adrienne Rich (b. 1929)
“Mothers often are too easily intimidated by their children’s negative reactions...When the child cries or is unhappy, the mother reads this as meaning that she is a failure. This is why it is so important for a mother to know...that the process of growing up involves by definition things that her child is not going to like. Her job is not to create a bed of roses, but to help him learn how to pick his way through the thorns.”
—Elaine Heffner (20th century)