Generaattorijoukko

Generaattorijoukko on joukko S ryhmässä G sellainen, että jokainen G:n alkio voidaan muodostaa S:n alkioiden kertolaskujen ja näiden käänteisten alkioiden avulla. Toisin sanoen G = ⟨S⟩. Generaattorijoukko kuvaa, miten laajempi rakenne voidaan rakentaa pienemmästä joukosta alkiota.

Jos G = ⟨S⟩, sanotaan, että S generoi G. S on silloin generaattorijoukko; jos S koostuu yhdestä alkiosta {g}, ja G = ⟨g⟩, G on syklinen. Generaattorijoukko voi olla joko finite tai infinite, ja ryhmä voidaan usein purkaa tai luokitella tämän ominaisuuden mukaan.

Esimerkkejä: Z lisäysryhmänä on ⟨1⟩, eli kaikki kokonaisluvut voi muodostaa lisäyksen avulla yhdellä generaattorilla. S_n on ryhmä, jota voivat generoida esimerkiksi transpoositio (1 2) ja kiertokone (1 2 … n), jolloin S_n = ⟨(1 2), (1 2 … n)⟩. Vapaat ryhmät F_k ovat ryhmiä, jotka ovat generoitu k:lla vierailla generaattorilla; vapaa abelilainen ryhmä Z^n on ⟨e1, …, en⟩.

Minimaalinen generaattorijoukko on sellainen, josta ei voi poistaa mitään alkiota ilman, että rakenne ei enää ole täysin generoitu. Generaattorijoukot eivät ole yksiselitteisiä; eri joukkoja voi generoida saman rakenteen. Käytäntöissä generaattorijoukot ovat keskeisiä, kun halutaan tiivistää kuvaus ryhmästä tai muista algorytmisista rakenteista; niitä sovelletaan myös moduuleihin ja muihin algebrallisiin rakenteisiin, joissa M = R·S tarkoittaa, että koko rakenne saadaan aikaan kertomalla R:n ja S:n alkioita.