In mathematics, a generating system is a subset of the basic set of a mathematical structure from which each element of the entire set can be represented by applying the available operations. In the case of vector spaces in particular, this means that each vector can be represented as a linear combination of vectors of the generating system. In the case of groups , this means that each group element can be represented as the product of elements of the generating system and their inverses . The concept of the generating system also applies to other algebraic structures , such as modules and rings , and also for non-algebraic structures, such as topological spaces .
Generating systems of a given mathematical structure are usually not clearly defined. The existence of a generating system, on the other hand, is usually easy to show, since the basic set itself can often be chosen as the generating system. It is therefore often tried to find a minimal generating system. However, this is not always possible and general existence proofs for minimal generating systems often make use of Zorn's lemma (see for example the existence of a basis in vector spaces).
In general, the substructure of a mathematical structure generated by any subset can also be considered. This substructure is called the product of this subset and the subset itself is then called the generating set or producer of the substructure. So every sub-vector space is the product of a generating set of vectors (namely the linear envelope of these vectors) and every subgroup is the product of a generating set of group elements.
Generating systems in linear algebra
If a vector space is over a body , then a set is called a generating system of , if every vector from can be represented as a linear combination of vectors from . Each vector therefore has a decomposition of the form
with , and . Such a decomposition is generally not clearly defined. A vector space is called finitely generated if it has a generating system made up of finitely many vectors.
A generating system of the real coordinate space consists of the so-called standard basis vectors
In fact, any vector can pass
with represent as a linear combination of these vectors. Further generating systems can be obtained by adding additional “superfluous” vectors. In particular, the set of all vectors of represents a generating system of. There are also generating systems that do not contain the vectors . For example is
a generating system of , because every vector can also pass through
An example of a vector space that is not finitely generated is the polynomial space of polynomials with real coefficients in one variable . A generating system of the is the set of monomials
This is a generating system because every polynomial of degree is
thus can be represented as a (finite) linear combination of monomials. Here, too, there are many other generating systems, for example the Legendre polynomials or the Chebyshev polynomials . But one can show that the polynomial space has no finite generating system.
Another example of a vector space that is not finitely generated is the sequence space of real number sequences with for . In this case, however, the obvious choice is
no generating system of dar, because not every sequence can be represented as a (finite) linear combination of . This is only possible for sequences in which only a finite number of sequence members are not equal to zero. A generating system of inevitably consists of an uncountable number of elements.
Zero vector space
The zero vector space , which consists only of the zero vector , has the two generating systems
- and .
The empty set forms a generating system of the zero vector space, since the empty sum of vectors gives the zero vector by definition.
A generating system is called minimal if no vector exists, so that there is still a generating system of . According to the basic selection theorem, a minimal generating system can be selected from every non-minimal generating system by omitting “superfluous” elements. This is easy to see in the case of finite-dimensional vector spaces, in the case of infinite-dimensional vector spaces one needs Zorn's lemma for the proof .
A minimal generating system always consists of linearly independent vectors. If the vectors in were not linearly independent, then there is a vector that can be represented as a linear combination of vectors in . But then every linear combination of vectors can also be written as a linear combination of vectors in and would not be minimal. Each minimal generating system thus represents a basis of the vector space, that is, each vector of the space can be uniquely represented as a linear combination of the basis vectors.
The subspace generated by can also be considered for any set . To construct there are the following two methods.
In the first method, the average of all subspaces of which contain is considered. This is itself a subspace of , since the intersection of a non-empty set of subspaces is again a subspace, and with itself has at least one subspace that contains. This sub-vector space is the smallest sub-vector space in the sense of inclusion that contains as a subset.
In the second method, the set of all possible linear combinations of elements of the set is considered. This set is called the linear envelope of and denoted by. The sub-vector space is therefore exactly the vector space generated by in the sense of the definition above. The set is thus a generating system of .
Generating systems in group theory
If a group , then a subset is called a generating system of , if each element can be represented as a finite product of elements and their inverses. That is, each group element has a representation of the shape
with and or for . Such a decomposition is generally not clearly defined. A group is called finitely generated if it has a generating system made up of finitely many elements.
Group of whole numbers
A clear example is the group of whole numbers with addition as a link and the neutral element . The operations allowed here are the addition of numbers and the transition to the negative of a number. This group is called the one-element set
generates, for every positive number can be explained by successive addition of the win and all through . Analog is also
a generating system of . These two generating systems are minimal, because their only real subset is the empty set, and this does not represent a generating system for . Another generating system is
because and through is already completely generated. It is even minimal, that is, no real subset of is a generating system. This example shows that minimal generating systems do not necessarily have to be of minimal power , because and are generating systems of really smaller power. In general, a non-empty subset is generated when the greatest common divisor of all elements is the amount . This is shown by the Euclidean algorithm , because it produces as a by-product a representation of as a complete linear combination of elements (and each such linear combination is divided by).
If a group has a one-element generating system
then the group is called cyclical with the producer . Then applies here
that is, the group consists of the integer powers of the producer . So that's too
a generating system of . The cyclic groups can be fully classified. For every natural number there is a cyclic group with exactly elements and there is the infinite cyclic group . Every other cyclic group is isomorphic to one of these groups . In particular, is isomorphic to the above additive group of integers and is isomorphic to the remainder class group with addition ( modulo ) as a link. This residue class group is any number that is relatively prime to is a producer. If prime , then even every number represents a generator.
An example of a group that is created by at least two elements is the dihedral group . The dihedral group is the isometric group of a regular corner in the plane. It consists of elements, namely rotations and reflections . The rotation turns the polygon by the angle and the mirroring reflects it on an axis that is inclined at an angle . A generating system of the dihedral group is
because each rotation can be represented by repeated application of (the rotations form a cyclic subgroup), that is , and each mirroring by application of and a subsequent rotation, that is . The reflection can also be replaced by any other reflection . The dihedral group also has the generating system
consisting of two reflections, because the rotation has the representation and has already been identified as a generating system. Instead of any two adjacent reflections, a generating system of the dihedral group also forms, because it also applies .
Groups of rational numbers
An example of a group that is not finite is the group of rational numbers with addition as a link. This group is, for example, determined by the number of original fractions
generated. However, it cannot be generated by a finite set of rational numbers. For every such set one can find another rational number that cannot be represented as the sum of the numbers and their opposing numbers. To this end, the denominator the number is simply prime the denominators of the numbers selected. Even the group of positive rational numbers with multiplication as a link is not finite. A generating system of this group is the set of prime numbers
The trivial group , which consists only of the neutral element , has the two generating systems
- and .
The empty set forms a generating system of the trivial group, since the empty product of group elements yields the neutral element by definition.
A generating system is called symmetric if
applies. Each finite, symmetrical generating system of a group can be assigned its Cayley graph . Different finite, symmetrical generating systems of the same group give quasi-isometric Cayley graphs, the quasi-isometric type of Cayley graph is therefore an invariant of finitely generated groups.
Presentation of groups
In general, a group can be represented as an image under the canonical mapping of the free group above the generating system, with the inclusion continuing. This explains the above explicit description of the product. Furthermore, this interpretation has important applications in group theory. We assume that is surjective , that is, that of is generated. Knowing the kernel of then unambiguously determines except for isomorphism. In favorable cases, the core itself can again be simply described by the producer . The date then clearly defines except for isomorphism.
Of any amount generated subset of is with designated, it consists of the neutral element and all finite products for which for each case or is. So is
a symmetric generating system of .
In the theory of topological groups one is usually interested in closed subgroups and therefore agrees to understand the product of a subset to be the smallest closed subgroup that contains.
Since the link and the inverse are continuous, the conclusion of the algebraic product is again a subgroup of . Therefore the product of a subset of a topological group is the closure of the group product .
If the topological group has a finite generating system, it is also called topologically finite generation.
Since is dense in the whole p-adic numbers , is generated as a topological group of . So it is topologically generated finitely. From the terminology of the pro- finite groups it can be deduced that it is procyclical.
Generating systems in algebra
Be a commutative ring with one . A generating system of an ideal is a set with the property that each is
with , and can be disassembled. An ideal is said to be finitely generated if there is a finite subset with . A main ideal is an ideal generated by a one-element set. In particular, the ring is a main ideal because it is created by . A ring is noetherian if and only if all ideals are finitely generated.
A subset of a (left) module is a generating system if each is represented as a finite sum
with , and can be displayed. An analogous definition applies to right modules. A module is called free if it has a generating system consisting of linearly independent elements.
Generating systems in measure theory and topology
So-called σ-algebras are investigated in measurement and integration theory . For a basic set and an arbitrary subset of the power set of denotes the σ-algebra generated by , i.e. the smallest σ-algebra containing all sets from . It is constructed as the average of all σ-algebras it contains , since it is generally difficult to explicitly state the product as such. For example, one looks at a topological space and looks for a smallest σ-algebra in it that contains all open sets, i.e. the σ-algebra generated by . The σ-algebra that is clearly determined by this is called Borel's σ-algebra . This is of central importance in integration theory.
In topology , the concept of the generating system is synonymous with that of the sub-base . This is a set system of open subsets of a topological space that creates the topology . This means that every open set is generated from the elements contained in solely by the two operations of forming the average of finitely many sets and forming the union of any number of sets .
is thus characterized in that the coarsest topology is on the basic set , with respect to which the sets are open in all. Hence the average of all topologies that contain.
If the topology can even be generated from just by forming arbitrary union sets, then one calls a basis of the topology
Set theoretical formulation
Let a basic set and a system of subsets of be given. These subsets correspond to the substructures of , which are considered below. Be given a lot further . Then the smallest amount is asked, so that applies. The quantity is then the producer of . Such an element exists and is uniquely determined if it applies
- is stable under arbitrary averages , that is , if a subset is not empty, so is the average .
- There is at least one element of the property (usually true ).
The product then has the representation
This applies to all of the above examples. In the case of vector spaces, the set system under consideration is the set of sub-vector spaces of a vector space and is the basic set . In the case of groups, the set is the subgroups of a group and the basic set is . In the case of σ-algebras, the set of σ-algebras is on and the basic set . This also applies mutatis mutandis to all other examples mentioned.
- Heinz Bauer : Measure and integration theory (= De Gruyter textbook ). 2nd, revised edition. de Gruyter , Berlin (inter alia) 1992, ISBN 3-11-013625-2 .
- Gerd Fischer : Linear Algebra . 15th, improved edition. Vieweg , Wiesbaden 2005, ISBN 3-8348-0031-7 .
- Kurt Meyberg : Algebra. Vol. 1 . Carl Hanser Verlag , Munich [u. a.] 1975, ISBN 3-446-11965-5 .
- Christian Karpfinger - Kurt Meyberg: Algebra. Groups - rings - bodies . 2nd Edition. Spectrum Akademischer Verlag , Heidelberg 2010, ISBN 978-3-8274-2600-0 .
- Horst Schubert : Topology. An introduction (= mathematical guidelines ). 4th edition. BG Teubner Verlag , Stuttgart 1975, ISBN 3-519-12200-6 .
- yark: Generating set of a group . In: PlanetMath . (English)