# Difference between revisions of "Generating set of a group"

(→Types of generating sets) |
|||

(7 intermediate revisions by the same user not shown) | |||

Line 9: | Line 9: | ||

A [[subset of a group]] is termed a '''generating set''' if it satisfies the following equivalent conditions: | A [[subset of a group]] is termed a '''generating set''' if it satisfies the following equivalent conditions: | ||

− | * Every element of the group can be expressed in terms of the elements of this subset by means of the group operations of multiplication and inversion. (note that if the subset is a [[symmetric subset]], i.e., it is closed under taking inverses, then every element of the group must be a product of elements in the subset. Symmetric subsets arise, for instance, when we take a union of subgroups). | + | * Every element of the group can be expressed as a [[defining ingredient::word]] in terms of the elements of this subset, i.e., it can be expressed using the elements of the subset by means of the group operations of multiplication and inversion. (note that if the subset is a [[symmetric subset]], i.e., it contains the identity and is closed under taking inverses, then every element of the group must be a product of elements in the subset. Symmetric subsets arise, for instance, when we take a union of subgroups). |

* There is no proper subgroup of the group containing this subset<section end=beginner/> | * There is no proper subgroup of the group containing this subset<section end=beginner/> | ||

* There is a surjective map from a [[free group]] on that many generators to the given group, that sends the generators of the free group to the elements of this ''generating set''. | * There is a surjective map from a [[free group]] on that many generators to the given group, that sends the generators of the free group to the elements of this ''generating set''. | ||

<section begin=beginner/> | <section begin=beginner/> | ||

− | The elements of the generating set are termed generators. | + | The elements of the generating set are termed '''generators''' (the term is best used collectively for the generating set, rather than for the elements in isolation). |

===Definition with symbols=== | ===Definition with symbols=== | ||

Line 26: | Line 26: | ||

* If <math>H</math> is a [[proper subgroup]] of <math>G</math> (i.e. <math>H</math> is a [[subgroup]] of <math>G</math> that is not equal to the whole of <math>G</math>), then <math>H</math> cannot contain <math>S</math>.<section end=beginner/> | * If <math>H</math> is a [[proper subgroup]] of <math>G</math> (i.e. <math>H</math> is a [[subgroup]] of <math>G</math> that is not equal to the whole of <math>G</math>), then <math>H</math> cannot contain <math>S</math>.<section end=beginner/> | ||

* Consider the natural map from the free group on as many generators as elements of <math>S</math>, to the group <math>G</math>, which maps the freely generating set to the elements of <math>S</math>. This gives a surjective homomorphism from the free group, to <math>G</math>. | * Consider the natural map from the free group on as many generators as elements of <math>S</math>, to the group <math>G</math>, which maps the freely generating set to the elements of <math>S</math>. This gives a surjective homomorphism from the free group, to <math>G</math>. | ||

+ | |||

+ | ===Equivalence of definitions=== | ||

+ | {{further|[[Equivalence of definitions of generating set]]}} | ||

+ | <section begin=beginner/> | ||

+ | ==Examples== | ||

+ | |||

+ | ===Extreme examples=== | ||

+ | |||

+ | * The set of ''all'' elements of a group is a generating set for the group. It is also the largest possible generating set. | ||

+ | * The set of all non-identity elements of a group is a generating set for the group. | ||

+ | * If <math>S</math> is a subset of a group <math>G</math> such that every element of <math>G</math> is a power of some element of <math>S</math>, then <math>S</math> is a generating set for <math>G</math>. | ||

+ | |||

+ | ===Some examples in abelian groups=== | ||

+ | |||

+ | * In the group of integers under addition, the singleton set <math>\{ 1 \}</math> is a generating set. This is because every integer can be written as a sum of <math>1</math>s or <math>-1</math>s. | ||

+ | * In the group of integers under addition, the two-element set <math>\{ 2,3 \}</math> is a generating set. To see this, note that every integer can expressed as a sum of <math>1</math>s or <math>-1</math>s, and both <math>1</math> and <math>-1</math> can be expressed in terms of <math>2</math> and <math>3</math>. | ||

+ | * In the group of rational numbers, the set of all unit fractions <math>1/n, n \in \mathbb{N}</math>, form a generating set. | ||

+ | <section end=beginner/> | ||

+ | |||

+ | ===Some examples in non-abelian groups=== | ||

+ | |||

+ | * In the symmetric group on a finite set, the set of all transpositions is a generating set for the group. {{proofat|[[Transpositions generate the finitary symmetric group]]}} | ||

+ | * The special linear group <math>SL(n,k)</math> over a field <math>k</math> is generated by elementary matrices. {{proofat|[[Elementary matrices generate the special linear group]]}} | ||

+ | |||

+ | For more information on generating sets of particular groups, refer: | ||

+ | |||

+ | [[:Category:Generating sets for particular groups]] | ||

==Constructs== | ==Constructs== | ||

Line 32: | Line 59: | ||

{{further|[[Cayley graph of a group]]}} | {{further|[[Cayley graph of a group]]}} | ||

+ | |||

Given a generating set of a group, we can construct the [[Cayley graph of a group|Cayley graph]] of the group with respect to that generating set. This is a graph whose vertex set is the set of elements of the group and where there is an edge between two vertices whenever one can be taken to the other by left multiplying by a generator. | Given a generating set of a group, we can construct the [[Cayley graph of a group|Cayley graph]] of the group with respect to that generating set. This is a graph whose vertex set is the set of elements of the group and where there is an edge between two vertices whenever one can be taken to the other by left multiplying by a generator. | ||

Line 37: | Line 65: | ||

The generators of a group may not in general be independent. That is, there may be words in the generators that simplify to the identity in the given group. Such a word is termed a [[relation]] between the generators. Relations can be viewed as elements of the free group on symbols corresponding to the generators. Thus relations form a [[normal subgroup]] of the free group. Specifying a set of relations whose normal closure is this normal subgroup is what we call a [[presentation of a group]]. | The generators of a group may not in general be independent. That is, there may be words in the generators that simplify to the identity in the given group. Such a word is termed a [[relation]] between the generators. Relations can be viewed as elements of the free group on symbols corresponding to the generators. Thus relations form a [[normal subgroup]] of the free group. Specifying a set of relations whose normal closure is this normal subgroup is what we call a [[presentation of a group]]. | ||

+ | |||

+ | ==Types of generating sets== | ||

+ | |||

+ | {| class="sortable" border="1" | ||

+ | ! Type of generating set !! Meaning !! Property of being a group that has such a generating set | ||

+ | |- | ||

+ | | finite generating set || The generating set is finite as a set || [[finitely generated group]] | ||

+ | |- | ||

+ | | [[minimal generating set]] (also known as irredundant generating set) || The generating set has no proper subset that is also a generating set || [[minimally generated group]] | ||

+ | |- | ||

+ | | generating set of minimum size || A generating set such that there is no generating set of smaller size. If finite, then this must also be a minimal generating set || | ||

+ | |} | ||

+ | |||

+ | It is not in general true that any two minimal generating sets of a group have the same size (see [[. However, two important related facts are true: | ||

+ | |||

+ | * If a group has a finite generating set, then every generating set has a finite subset that is a generating set, and in particular, every minimal generating set is finite. For more, see [[equivalence of definitions of finitely generated group]]. | ||

+ | * We can consider the property of being a [[group in which all minimal generating sets have the same size]]. Any [[group of prime power order]] has this property. This follows from [[Burnside's basis theorem]]. | ||

+ | |||

+ | == Associated arithmetic functions == | ||

+ | |||

+ | * [[Minimum size of generating set]]: This is the smallest possible cardinality of a generating set for the group. It is finite if and only if the group is a [[finitely generated group]]. | ||

+ | * [[Maximum size of minimal generating set]]: This is the largest possible cardinality of a minimal generating set for the group. It is defined for a [[fintie group]], but not necessarily for an infinite finitely generated group. | ||

==Study of this notion== | ==Study of this notion== |

## Latest revision as of 04:47, 11 April 2017

This article defines a property of subsets of groups

View other properties of subsets of groups|View properties of subsets of abelian groups|View subgroup properties

This term is related to: combinatorial group theory

View other terms related to combinatorial group theory | View facts related to combinatorial group theory

## Contents

## Definition

### Symbol-free definition

A subset of a group is termed a **generating set** if it satisfies the following equivalent conditions:

- Every element of the group can be expressed as a word in terms of the elements of this subset, i.e., it can be expressed using the elements of the subset by means of the group operations of multiplication and inversion. (note that if the subset is a symmetric subset, i.e., it contains the identity and is closed under taking inverses, then every element of the group must be a product of elements in the subset. Symmetric subsets arise, for instance, when we take a union of subgroups).
- There is no proper subgroup of the group containing this subset
- There is a surjective map from a free group on that many generators to the given group, that sends the generators of the free group to the elements of this
*generating set*.

The elements of the generating set are termed **generators** (the term is best used collectively for the generating set, rather than for the elements in isolation).

### Definition with symbols

A subset of a group is termed a **generating set** if it satisfies the following equivalent conditions:

- For any element , we can write:

where for each , either or (here, the s are not necessarily distinct). In the situation where is a symmetric subset (i.e. ) we do not need to throw in inverses. This happens, for instance, when is a union of subgroups of .

- If is a proper subgroup of (i.e. is a subgroup of that is not equal to the whole of ), then cannot contain .
- Consider the natural map from the free group on as many generators as elements of , to the group , which maps the freely generating set to the elements of . This gives a surjective homomorphism from the free group, to .

### Equivalence of definitions

`Further information: Equivalence of definitions of generating set`

## Examples

### Extreme examples

- The set of
*all*elements of a group is a generating set for the group. It is also the largest possible generating set. - The set of all non-identity elements of a group is a generating set for the group.
- If is a subset of a group such that every element of is a power of some element of , then is a generating set for .

### Some examples in abelian groups

- In the group of integers under addition, the singleton set is a generating set. This is because every integer can be written as a sum of s or s.
- In the group of integers under addition, the two-element set is a generating set. To see this, note that every integer can expressed as a sum of s or s, and both and can be expressed in terms of and .
- In the group of rational numbers, the set of all unit fractions , form a generating set.

### Some examples in non-abelian groups

- In the symmetric group on a finite set, the set of all transpositions is a generating set for the group.
`For full proof, refer: Transpositions generate the finitary symmetric group` - The special linear group over a field is generated by elementary matrices.
`For full proof, refer: Elementary matrices generate the special linear group`

For more information on generating sets of particular groups, refer:

Category:Generating sets for particular groups

## Constructs

### Cayley graph

`Further information: Cayley graph of a group`

Given a generating set of a group, we can construct the Cayley graph of the group with respect to that generating set. This is a graph whose vertex set is the set of elements of the group and where there is an edge between two vertices whenever one can be taken to the other by left multiplying by a generator.

### Presentation

The generators of a group may not in general be independent. That is, there may be words in the generators that simplify to the identity in the given group. Such a word is termed a relation between the generators. Relations can be viewed as elements of the free group on symbols corresponding to the generators. Thus relations form a normal subgroup of the free group. Specifying a set of relations whose normal closure is this normal subgroup is what we call a presentation of a group.

## Types of generating sets

Type of generating set | Meaning | Property of being a group that has such a generating set |
---|---|---|

finite generating set | The generating set is finite as a set | finitely generated group |

minimal generating set (also known as irredundant generating set) | The generating set has no proper subset that is also a generating set | minimally generated group |

generating set of minimum size | A generating set such that there is no generating set of smaller size. If finite, then this must also be a minimal generating set |

It is not in general true that any two minimal generating sets of a group have the same size (see [[. However, two important related facts are true:

- If a group has a finite generating set, then every generating set has a finite subset that is a generating set, and in particular, every minimal generating set is finite. For more, see equivalence of definitions of finitely generated group.
- We can consider the property of being a group in which all minimal generating sets have the same size. Any group of prime power order has this property. This follows from Burnside's basis theorem.

## Associated arithmetic functions

- Minimum size of generating set: This is the smallest possible cardinality of a generating set for the group. It is finite if and only if the group is a finitely generated group.
- Maximum size of minimal generating set: This is the largest possible cardinality of a minimal generating set for the group. It is defined for a fintie group, but not necessarily for an infinite finitely generated group.

## Study of this notion

### Mathematical subject classification

Under the Mathematical subject classification, the study of this notion comes under the class: 20F05