Genererende verzameling

In de abstracte algebra is een genererende verzameling of voortbrengende verzameling van een groep ${\displaystyle G}$ een deelverzameling ${\displaystyle S\subseteq G}$, zodat elk element van ${\displaystyle G}$ kan worden uitgedrukt als het product van een eindig aantal elementen van ${\displaystyle S}$ en hun inversen. Het gaat hier om het product bepaald door de bewerking die er tussen de elementen in ${\displaystyle G}$ is gedefinieerd. Als ${\displaystyle G}$ door ${\displaystyle S}$ wordt gegenereerd, schrijft men ${\displaystyle G=\langle S\rangle }$. De elementen van ${\displaystyle S}$ worden de voortbrengers^[1] van ${\displaystyle G}$ genoemd.

Andersom, als ${\displaystyle S}$ een deelverzameling is van een groep ${\displaystyle G}$, dan is ${\displaystyle \langle S\rangle }$, de ondergroep gegenereerd door ${\displaystyle S}$ de kleinste ondergroep van ${\displaystyle G}$ die elk element van ${\displaystyle S}$ bevat, wat betekent dat het de doorsnede is van alle ondergroepen die elk element van ${\displaystyle S}$ bevatten. Dat komt ermee overeen dat ${\displaystyle \langle S\rangle }$ de ondergroep is van alle elementen van ${\displaystyle G}$ die als het eindige product van de elementen van ${\displaystyle S}$ en hun inversen kunnen worden geschreven.

Als er maar een enkel element ${\displaystyle x\in G}$ deel uitmaakt van ${\displaystyle S}$, wordt ${\displaystyle \langle S\rangle }$ meestal geschreven als ${\displaystyle \langle x\rangle }$. In dat geval is ${\displaystyle G=\langle x\rangle }$, is ${\displaystyle x}$ de voortbrenger van ${\displaystyle G}$ en is ${\displaystyle G}$ een cyclische groep van de machten van ${\displaystyle x}$.

De orde ${\displaystyle \mathrm {ord} (x_{i})}$ van een element ${\displaystyle x_{i}\in S}$ kan op twee manieren worden gedefinieerd: als het aantal elementen van ${\displaystyle \langle x_{i}\rangle }$ en als het kleinste positieve gehele getal ${\displaystyle m_{i}}$ zodat ${\displaystyle x^{m_{i}}=e}$, waarin ${\displaystyle e}$ het neutrale element van ${\displaystyle \langle x_{i}\rangle }$ is. ${\displaystyle G}$ kan met de tweede definitie als een verzameling worden geschreven. Gegeven dat

${\displaystyle G=\langle S\rangle =\langle x_{1},\cdots ,x_{n}\rangle }$

is

${\displaystyle G=\{x_{1}^{m_{1}}x_{2}^{m_{2}}\cdots x_{n}^{m_{n}}\mid x_{i}\in S\ {\mbox{en}}\ 0\leq m_{j}<\mathrm {ord} (x_{j})\}}$

Altijd is ${\displaystyle x^{0}=e\ }$ en ${\displaystyle \langle e\rangle }$ is de groep met alleen het neutrale element ${\displaystyle e}$.

• De multiplicatieve groep ${\displaystyle U_{9}=\{\ 1,\ 2,\ 4,\ 5,\ 7,\ 8\ \}}$ is de groep van de gehele getallen die met 9 onderling ondeelbaar zijn. ${\displaystyle \{7\}}$ is geen genererende verzameling van ${\displaystyle U_{9}}$, omdat

${\displaystyle \{\ 7^{i}{\bmod {9}}\ |\ i\in \mathbb {N} \}=\{\ 7,\ 4,\ 1\}\neq U_{9}}$

${\displaystyle \{2\}}$ is wel een genererende verzameling van ${\displaystyle U_{9}}$:

${\displaystyle \{\ 2^{i}{\bmod {9}}\ |\ i\in \mathbb {N} \}=\{\ 2,\ 4,\ 8,\ 7,\ 5,\ 1\}}$

• De groep ${\displaystyle (\mathbb {Z} ,+)}$ wordt door een element voortgebracht, maar de groepen ${\displaystyle (\mathbb {Q} ,+)}$, ${\displaystyle (\mathbb {R} ,+)}$ en ${\displaystyle (\mathbb {C} ,+)}$ zijn niet eindig voortgebracht.