Let be a vector space and be a basis of . Given any vector space and any elements , there is a linear transformation such that . One could say that this happens because the elements of a basis are not "related" to each other (formally, they are linearly independent). Indeed, if, for example, we had the relation for some scalar (and then wasn't linearly independent), then the linear transformation could not exist.
Let us consider a similar problem with groups: given a group spanned by a set and given any group and any set , does there always exist a group morphism such that ? The answer is no. For example, consider the group which is spanned by the set , the group (with the adition operation) and the set . If there exists a group morphism such that , then , which is impossible. But if instead we had choose , then such a group morphism does exist and it would be given by . Indeed, given any group and any , we have the group morphism defined by (in multiplicative notation) that verifies . In a way, we can think that this happens because the elements of the set (that spans ) don't verify relations like (like ) or . So, it seems that is a group more "free" that .
Our goal in this section will be, given a set , build a group spanned by the set such that it will be the most "free" possible, in the sense that it doesn't have to obey relations like or . To do so, we begin by constructing a "free" monoid (in the same sense). Informally, this monoid will be the monoid of the words written with the letters of the alphabet , where the identity will be the word with no letters (the "empty word"), and the binary operation of the monoid will be concatenation of words. The notation that we will use for the element of this monoid meets this idea that the elements of this monoid are the words where are letters of the alphabet . Here is the definition of this monoid.
DefinitionLet be a set.
We denote the -tuples with and by .
We denote , that is with , by .
We denote by the set .
We define in the concatenation operation by .
Next we prove that this monoid is indeed a monoid. It's an easy to prove result, we need to show associativity of and that .
Proposition is a monoid with identity .
Proof The operation is associative because, given any , we have
It's obvious that has the identity as by the definition of and .
Following the idea that the monoid is the most "free" monoid spanned by , we will call it the free monoid spanned by .
DefinitionLet be a set. We denote the free monoid spanned by by .
Now let us construct the more "free" group spanned by a set . Informally, what we will do is insert in the monoid the inverse elements that are missing in it for it to be a group. In a more precise way, we will have a set equipotent to , choose a bijection from to and in this way achieve a "association" between the elements of and the elements of . Then we face (with ) as having the inverse element (with ), where is is associated with , respectively. Let us note that the order of the elements in is "reversed" because the inverse of the product must be , and the are, respectively, . The way we do that be the inverse of is to take a congruence relation that identifies with , and pass to the quotient by this relation (defining then, in a natural way, the binary operation of the group, ). By taking the quotient, we are formalizing the intuitive idea of identifying with , because in the quotient we have the equality . Let us give the formal definition.
DefinitionLet be a set. Let us take another set equipotent to and disjoint from and let be a bijective application.
For each let us denote by , for each let us denote by and for each let us denote by .
Let be the congruence relation of spanned by , this is, is the intersection of all the congruence relations in wich have as a subset. We denote the quotient set by .
Frequently, abusing the notation, we represent an element simply by .
Because the operation that we want to define in is defined using particular represententes and of the equivalence classes and , a first precaution is to verify that the definition does not depend on the chosen representatives. It's an easy verification.
LemmaLet be a set. It is well defined in the binary operation by (where is the congruence relation of the previous definition).
Proof Let be any elements such that and , this is, and . Because is a congruence relation in , we have , this is, .
Because the definition is valid, we present it.
DefinitionLet be a set. We define in the binary operation by .
Finally, we verify that the group that we constructed is indeed a group.
PropositionLet be a set. is a group with identity and where .
is associative because
Let us see that is the identity . Let be any element. We have and, in the same way, .
Let be any element and let us see that . We have and, by definition of , , this is, , therefore and, in the same way, .
In the same way that we did with the free monoid, we will call free group spanned by the set to the more "free" group spanned by this set.
DefinitionLet be a set. We call free group spanned by to .
Example Let . Let us choose any set disjoint (and equipotent) of . Let be any (in fact, the only) bijective application of in . Then we denote by and we denote by . We regard and as inverse elements. Let be the congruence relation of spanned by . is the set of all "words" written in the alphabet . For example, .
We have and, for example, , because (therefore ) and because is a congruence relation, we can "multiply" both "members" of the relation by and obtain . We see as meaning that in We have (more precisely, ), and we think in this equality as being the result of one "cut out" with in .
Given , let us denote the exact number of times that the "letter" appears in by and let us denote the exact number of times the "letter" appears in by . Then "cutting" 's with 's it remains a reduced word word with times the letter (if , let us us consider that there aren't any letters and remains times the letter ). Let us denote by . We have
if and only if and
In this way, each element is determined by the integer number and the product of two elements correspondent to the sum of they associated integers numbers and . Therefore, it seems that the group is "similar" to . indeed is isomorph to and the application is a group isomorphism.
Informally, it seems that is obtained from the "free" group imposing the relation . Let us try formalize this idea. We start with a set that spans a group that que want to create and a set of relations (such as or ) that the elements of must verify and we obtain a group spanned by and that verify the relations of . More precisely, we write each relation in the form (for example, is written in the form ) and we see each as a "word" of . Because doesn't have to be a normal subgroup of , we can not consider the quotient , so we consider the quotient where is the normal subgroup of spanned by . In , we will have , which we see as meaning that in the elements and are the same. In this way, will verify all the relations that we want and will be spanned by (more precisely, by ). Let us formalize this idea.
DefinitionLet be a group. We call presentation of , and denote by , to a ordered pair where is a set, and , where is the normal subgroup of spanned by . Given a presentation , we call spanning set to and set of relations to .
Let us see some examples of presentations of the free group and the groups , , and . We also use the examples to present some common notation and to show that a presentation of a group does not need to be unique.
Let be a set. is a presentation of because , where is the normal subgroup of spanned by . In particular, is a presentation of , more commonly denoted by . Another presentation of is , more commonly denoted by . Informally, in the presentation we insert a new element in the spanning set, but we impose the relation , this is, , which is the same as having not introduced the element and have stayed by the presentation .
Let . (where times) is a presentation of . Indeed, the subgroup of spanned by is and , therefore. Is more common to denote by .
Let (with and distinct) and . is a presentation of . Informally, what we do is impose comutatibility in , this is, , this is, , obtaining a group isomorph to . It's more usually denote by .
Let and . is a presentation of . Informally, what we do is impose comutability in the same way as in the previous example, and we impose and to obtain instead . It's more common denote by .
, more commonly written , is a presentation of , the group of the permutations of with the composition of applications. To verify this, one can verify that any group with presentation as exactly six elements , , , , , and , and that the multiplication of this elements results in the following Cayley table that is equal to the Cayley table of . Just to give an idea how this can be achived, a group with presentation as exactly the elements , , , , , and because none of this elements are the same (the relations don't allow us to conclude that two of the elements are equal) and because "another" elements like are actually one of the previous elements (for example, from we have , and taking inverses of both members, we have , which, using , this is, , and , results in ). Then, using the relations of the presentation, one can compute the Cayley table. For example, because we have the relation . Another example: we have because we can multiply both members of the relation by and then use . One could have suspected of this presentation by taking , and and then, trying to construct the Cayley table of , found out that it was possible if one know that .
It's natural to ask if all groups have a presentation. The following theorem tell us that the answer is yes, and it give us a presentation.
TheoremLet be a group.
The application defined by (where ) is an epimorphism of groups.
is a presentation of .
is well defined because every element of as a unique representations in the form with , with the exception of appears several times in the representation, but that doesn't affect the value of Let be any elements, where . We have , therefore is a morphism of groups. Because , then is a epimorphism of groups.
Using the first isomorphism theorem (for groups), we have , therefore is a presentation of .
The previous theorem, despite giving us a presentations of the group , doesn't give us a "good" presentation, because the spanning set is usually much larger that other spanning sets, and the set of relations is also usually much larger then other sufficient sets of relations (it is even a normal subgroup of , when it would be enough that it span an appropriated normal subgroup).