Matematyka dyskretna 2/Wykład 4: Elementy teorii grup

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

Teoria grup

to jeden z działów matematyki badający własności obiektów algebraicznych zwanych grupami. Wraz z zastosowaniami stanowi on obecnie ogromną, autonomiczną dziedzinę wiedzy. Historyczne korzenie teorii to: rozwiązywanie równań algebraicznych, teoria liczb oraz geometria. Euler, Gauss, Lagrange, Abel i Galois byli pionierami badań w tej dziedzinie. W szczególności, Galois jest uważany za pierwszego matematyka, 2który powiązał teorię grup z teorią ciał.

Grupa to uporządkowana czwórka , gdzie jest dowolnym zbiorem niepustym, działaniem dwuargumentowym, jest działaniem jednoargumentowym, a , przy czym, dla dowolnych , spełnione sa następujące warunki:

  • (łączność) ,
  • , czyli to element neutralny grupy .
  • , czyli jest elementem odwrotnym do w .

Rząd grupy skończonej to liczba jej elementów. Gdy grupa nie jest skończona, to mówimy, że ma rząd nieskończony.

Uwaga

Czasem w grupie nie podaje się w sposób jawny elementu neutralnego lub jednoargumentowego działania zwracającego element odwrotny. Zobaczymy, że takie postępowanie jest uprawnione, bo zarówno element neutralny jak i element odwrotny do jakiegoś , jeśli istnieje to jest jedyny.

Przykład

, czyli zbiór liczb całkowitych z dodawaniem i elementem neutralnym , jest grupą. Rzeczywiście:

  • suma dwu liczb całkowitych zawsze jest liczbą całkowitą,
  • dla dowolnych (łączność dodawania liczb całkowitych),
  • jest elementem neutralnym, gdyż ,
  • jest elementem odwrotnym liczby , gdyż .

Przykład

Dla dowolnej liczby naturalnej , zbiór reszt modulo wraz z dodawaniem modulo , tzn. jest grupą. Rzeczywiście:

  • suma dwu liczb modulo wpada do zbioru ,
  • dla dowolnych ,
  • jest elementem neutralnym, gdyż ,
  • jest elementem odwrotnym liczby , gdyż .

Przykład

jest grupą, gdzie to zbiór permutacji zbioru , a to składanie permutacji. Rzeczywiście:

  • złożenie dwóch permutacji jest permutacją ,
  • składanie funkcji, więc i permutacji, jest łączne,
  • identyczność jest elementem neutralnym przy składaniu funkcji,
  • permutacja odwrotna do jest elementem odwrotnym do w , gdyż .

Przykład

Gdy oraz jest liczba pierwszą, to jest grupą, gdzie działanie to mnożenie modulo . Rzeczywiście:

  • gdy , to oczywiście . Gdyby jednak , to dla pewnego .

Liczba byłaby więc rozkładzie , co jest niemożliwe wobec .

  • dla dowolnych zachodzi
  • jest elementem neutralnym, gdyż ,
  • Dowolny ma element odwrotny w . Możemy go wskazać np. przy pomocy rozszerzonego algorytmu Euklidesa.

Z pierwszości mamy zatem istnieją takie, że , czyli . To oznacza, iż jest elementem odwrotnym do w .

Można też, używając Małego Twierdzenia Fermata sprawdzić, że elementem odwrotnym do jest

    • , jeśli ,
    • , jeśli
SW 8.1.swf
Plik:SW 8.2.svg
SW 8.2.swf

Przykład

Rozważmy trójkąt równoboczny z poetykietowanymi wierzchołkami

oraz wybrane przekształcenia tego trójkąta pozostawiające go w tym samym miejscu płaszczyzny:


Wtedy jest grupą, gdzie jest składaniem przekształceń.

  • Poniższa tabela pokazuje wyniki wszystkich możliwych złożeń, a tym samym pokazuje, że składanie nie wyprowadza poza zbiór

.

  • Jak zawsze , będąc identycznością, jest elementem neutralnym dla składania.
  • Każde z rozważanych przekształceń ma odwrotne do siebie. Odwrotnym przekształceniem do rotacji w prawo jest oczywiście rotacja w lewo . Symetrie względem kolejnych osi są same do siebie odwrotne.

Zauważmy, że w każdym wierszu (i każdej kolumnie) występuje , skąd też można wywnioskować istnienie elementów odwrotnych.

Obserwacja 4.1 [prawo skracania]

Dla grupy i mamy:

  • (lewostronne) jeśli , to ,
  • (prawostronne) jeśli , to .

Dowód

Z uwagi na symetrię, pokażemy jedynie pierwszy punkt. Załóżmy zatem, że i niech będzie elementem odwrotnym do . Wtedy .

End of proof.gif

Obserwacja 4.2

Jeśli jest grupą i , to równanie



ma dokładnie jedno rozwiązanie w .

Dowód

Niech będzie elementem odwrotnym do w . Wtedy jest rozwiązaniem równania, gdyż



Dla dowodu jednoznaczności załóżmy, że i są rozwiązaniami naszego równania. Wtedy mamy i z lewostronnego prawa skracania .

End of proof.gif

Wniosek 4.3

Każda grupa ma dokładnie jeden element spełniający warunki elementu neutralnego oraz każdy jej element ma dokładnie jeden element odwrotny.

Dowód

Niech będzie grupą i . Element neutralny jest jedynym rozwiązaniem równania . Element odwrotny do jest jedynym rozwiązaniem .

End of proof.gif

W dalszych rozważaniach o abstrakcyjnych grupach porzucimy ornamentyczny symbol i będziemy się posługiwać notacją multiplikatywną. Zatem dla dowolnego , gdzie jest grupą

  • oznacza ,
  • to jedyny element neutralny grupy . Rozważając więcej niż jedną grupę dla jednoznaczności piszemy czasem .
  • to jedyny element odwrotny do w .

Pamietajmy, że symbol w większości wypadków nie oznacza dobrze znanej liczby . Podobnie nie możemy zakładać, iż działanie zachowuje prawa zwykłego mnożenia. W szczególności zachodzi dalece nie w każdej grupie (np. nie zachodzi w grupie dla ).

Grupa abelowa to ,1), w której działanie jest przemienne tzn. dla dowolnych mamy



Nazwa grup abelowych pochodzi od nazwiska Nielsa Abela, norweskiego matematyka, w którego pracach implicite pojawia się to pojęcie.

Przykład

Grupy i są abelowe, gdyż tak dodawanie, jak i mnożenie modularne jest przemienne.

Grupa przekształceń trójkąta równobocznego nie jest abelowa, gdyż np. .

SW 8.3.svg

W naturalny sposób w notacji multiplikatywnej definiujemy rekurencyjnie:
Dodatnie i ujemne potęgi elementu w grupie



Obserwacja 4.4

Dla dowolnej grupy , i zachodzi



Jeśli jest abelowa i , to



Jeśli grupa ma rząd skończony, to oczywiście dla dowolnego w ciągu nieujemnych potęg: elementy muszą zacząć się powtarzać. Załóżmy zatem, że i . Mnożąc te równość przez otrzymujemy . Udowodniliśmy zatem, iż w grupie o skończonym rzędzie każdy element w pewnej dodatniej potędze równy jest . Z Zasady Minimum dla każdego elementu istnieje więc najmniejsza taka dodatnia potęga.

Rząd elementu w grupie o skończonym rzędzie to najmniejsza dodatnia liczba taka, że . Dla grup nieskończonych rząd elementu jest tak samo zdefiniowany o ile taka liczba istnieje. Jeśli nie to ma rząd nieskończony.

Obserwacja 4.5

Dla elementu rzędu w grupie mamy wtedy i tylko wtedy, gdy .

Dowód

Jeśli to dla pewnego , a zatem



Na odwrót załóżmy, że dla pewnego . Niech gdzie . Wtedy mamy



co wraz z minimalnością jako rzędu elementu daje , czyli .

End of proof.gif

Homomorfizm grup , to dowolna funkcja taka, że dla dowolnych zachodzi



Obserwacja 4.6

Dla dowolnego homomorfizmu grup i mamy:

  • ,
  • , dla wszystkich ,

Dowód

Oczywiście . Prawo skracania w grupie daje więc . Z kolei, gdy , to , czyli jest elementem odwrotnym do w .

End of proof.gif

Izomorfizm grup to homomorfizm, który jest bijekcją.
Grupy izomorficzne to grupy, miedzy którymi istnieje izomorfizm. Izomorficzność grup i zapisujemy .

Podgrupa grupy to taka grupa , że oraz mnożenie w grupie jest restrykcją mnożenia w .

Obserwacja 4.7

Dla , gdzie jest grupą, jeśli

  • dla dowolnych ,
  • dla dowolnych ,

to jest podgrupą . Ponadto jeśli ma rząd skończony, to już pierwszy punkt implikuje, iż jest podgrupą grupy .

Dowód

Pierwszy punkt gwarantuje, że działanie nie wyprowadza poza zbiór . Łączność w wynika bezpośrednio z łączności w . Drugi punkt świadczy, iż każdy element w ma element odwrotny także w . Dla dowodu, że skorzystamy z niepustości i wybierzmy . Wtedy, z drugiego punktu, , więc na mocy punktu pierwszego.

Załóżmy teraz, że grupa ma rząd skończony oraz podzbiór jest zamknięty na mnożenie. Wtedy oczywiście wszystkie potęgi o nieujemnych wykładnikach wpadają do . Ponieważ ma rząd skończony, to rząd dowolnego elementu też jest skończony, czyli istnieje takie, że . Zatem i , czyli jest elementem odwrotnym do .

End of proof.gif

Z Obserwacji 4.7 dostajemy natychmiast:

Wniosek 4.8

Przecięcie dowolnej rodziny podgrup grupy jest podgrupą .

Grupy cykliczne

Podgrupa generowana przez podzbiór grupy , to przecięcie wszystkich podgrup zawierających zbiór . Podgrupę taką oznaczamy przez .
Zbiór generatorów grupy to jakikolwiek zbiór spełniający .

Obserwacja 4.9

Dla dowolnej grupy i



Dowód

Oczywiście wszystkie iloczyny postaci leżą w każdej podgrupie zawierającej , więc i w . Nadto zbiór wszystkich takich iloczynów jest zamknięty na iloczyn i odwracanie, bo . A zatem Obserwacja 4.7 gwarantuje, że jest podgrupą. Musi zatem być czynnikiem przecięcia wyznaczającego , czyli .

End of proof.gif

Grupa cykliczna to grupa generowana zbiorem jednoelementowym.

Jeśli , to . Gdy ponadto jest skończona, to jej rząd pokrywa się z rzędem elementu generującego , czyli .

Przykład

Grupa addytywna liczb całkowitych jest cykliczna. Rzeczywiście generuje te grupę:



Czy grupa ta ma jeszcze jakiś inny jednoelemtowy zbiór generujacy?

Przykład

Dla grupa jest skończoną grupą cykliczną generowaną przez . Rzeczywiście:



Obserwacja 4.10

Dowolne dwie grupy cykliczne tego samego rzędu są izomorficzne.

Dowód

Niech będzie generatorem grupy cyklicznej , dla . Łatwo sprawdzić, że równość rzędów tych grup daje, iż wtedy i tylko wtedy, gdy . A zatem ustala izomorfizm grup i .

End of proof.gif

Wniosek 4.11

Dowolna skończona grupa cykliczna rzędu jest izomorficzna z . Dowolna nieskończona grupa cykliczna jest izomorficzna z .

SW 8.4.swf
SW 8.5.swf
SW 8.6.swf

Przykład

Dla rozważymy pewne grupy przekształceń -kątów foremnych jako podgrupy grupy . Poetykietujmy wierzchołki -kąta foremnego liczbami . Obrót wielokąta foremnego o jeden wierzchołek w prawo, jak na rysunku, odpowiada cyklicznej permutacji . Zastanówmy się teraz jakie elementy składają się na i jaka jest ich interpretacja geometryczna.

Rząd cyklu -elementowego jest oczywiście równy . Kolejne złożenia odpowiadają kolejnym obrotom w prawo naszego wielokąta o , aż przekręca go do pozycji wyjściowej (czyli jest identycznością). Zatem jest grupą cykliczną rzędu , czyli z Wniosku 4.11 mamy .

Zwiększmy trochę zbiór generatorów i do obrotu w prawo dołóżmy symetrię względem jednej z osi symetrii naszego -kąta foremnego. W przypadku gdy jest parzyste osie symetrii przechodzą przez środki przeciwległych boków lub naprzeciwległe wierzchołki, jeśli zaś jest nieparzyste to osie symetrii przechodzą przez wierzchołek i środek przeciwległego do niego boku.

Permutacja odpowiadająca symetrii osiowej posiada poza cyklami wielkości :

  • jeden cykl jednoelementowy, gdy jest nieparzyste,
  • dwa cykle jednoelementowe, gdy jest parzyste.

Na przykład, gdy jest parzyste oraz :

  • jest symetrią względem osi przechodzącej przez bok , to rozkłada się na cykle:

  • gdy jest symetrią względem osi przechodzącej przez wierzchołki i ,

to rozkłada się na cykle

a dla nieparzystego :

  • gdy jest symetrią względem osi przechodzącej przez wierzchołek i bok , to rozkłada się na cykle

Jakie elementy składają się na ? Jaka jest ich interpretacja geometryczna?

Zbierzmy kilka prostych faktów:

  • , .
  • jest inwolucją, czyli jest sama do siebie odwrotna, .

Pokażemy tę własność jedynie dla nieparzystych (dowód dla parzystych znacząco się nie różni):



dla .

Z Obserwacji 4.9 i naszych spostrzeżeń mamy:



Zatem podgrupa generowana przez ma co najwyżej elementów. Jako ćwiczenie zostawiamy dowód, że w istocie wymienione elementy są parami różne. Okazuje się, że



Grupa dihedralna to podgrupa grupy (dla ) generowana przez .

Produkt grup i to grupa , w której działanie zdefiniowane jest przez



Weryfikację, że tak określone działanie po współrzędnych spełnia wszystkie warunki wymagane od grupy zostawiamy jako ćwiczenie.

Przykład

Rozważmy .



Zauważmy, że zadana przez



definiuje izomorfizm grup i .

Czy zawsze ? Zbadajmy jeszcze jeden przykład: i . Rzędy elementów w produkcie przedstawia tabela:



A zatem grupa nie ma elementu rzędu , nie może więc być izomorficzna z cykliczna grupą .

Obserwacja 4.12

Jeśli , to .

Dowód

Wystarczy oczywiście pokazać, że rząd elementu wynosi , wtedy bowiem grupa będzie cykliczna i, jako -elementowa, musi być izomorficzna z .

Niech więc będzie rzędem w grupie . Licząc kolejno na obu osiach produktu dostajemy



Zatem jest najmniejszą wspólną wielokrotnością i . Ponieważ , to



End of proof.gif

Twierdzenie Lagrange'a

Zajmiemy się teraz możliwymi rzędami podgrup grupy skończonej. Z rozważań tej części wykładu dowiemy się, że jeśli jest podgrupą skończonej grupy , to rząd dzieli rząd . Zwracamy jednak uwagę, iż to nie oznacza, że grupa ma podgrupy o rzędzie będącym jakimkolwiek dzielnikiem rzędu grupy .

Przykład

Niech będzie podgrupą grupy składającą się z tych permutacji, które są złożeniami parzystej liczby transpozycji. Wtedy , ale grupa nie ma podgrup rzędu .

Lewa warstwa podgrupy grupy względem elementu to zbiór



Prawa warstwa podgrupy grupy względem elementu to zbiór



Skoncentrujemy się teraz na lewych warstwach. Oczywiście wszystkie rozumowania można powtórzyć dla warstw prawych

Przykład

Niech będzie grupa dihedralną symetrii kwadratu. Posiada ona podgrupę cykliczną . Niech będzie symetrią osiową. Zauważmy, że elementy lewej warstwy



wszystkie symetrie osiowe kwadratu. Jako ćwiczenie pozostawiamy wyznaczenie warstw , oraz .

Zauważmy, że warstwa elementu neutralnego , to podgrupa . Nastepna obserwacja orzeka, że wszystkie warstwy lewo- i prawo-stronne są równoliczne.

Obserwacja 4.13

Jeśli jest skończoną podgrupą grupy i , to .

Dowód

Niech i załóżmy, że . Wtedy z prawa skracania mamy . Zatem elementy są parami różne i zbiór



ma dokładnie elementów.

End of proof.gif

Obserwacja 4.14

Dla dowolnej podgrupy grupy i lewe warstwy , są albo identyczne albo rozłączne.

Dowód

Pokażemy, że jeśli i mają jakiś wspólny element to są one identyczne. Załóżmy zatem, że , czyli dla pewnych . Wtedy . Dla dowodu inkluzji , niech , czyli dla pewnego . Wtedy



co wobec daje .

End of proof.gif

Twierdzenie 4.15[Lagrange'a]

Dla dowolnej podgrupy skończonej grupy , rząd dzieli rząd .

Dowód

Niech oraz . Ponieważ:

  • każdy jest we własnej warstwie , gdyż ,
  • dla dowolnego ,
  • lewe warstwy , są albo identyczne albo rozłączne,

to lewe warstwy tworzą podział zbioru na równoliczne bloki wielkości , skąd natychmiast .

End of proof.gif

Wniosek 4.16

Niech będzie grupą rzędu . Wtedy dla mamy:

  • rząd elementu dzieli ,
  • .

Dowód

Niech będzie rzędem elementu . Wtedy jest rzędem podgrupy cyklicznej . Z Twierdzenia Lagrange'a , czyli rząd tej podgrupy cyklicznej, dzieli . Skoro teraz to oczywiście

End of proof.gif

Wniosek 4.17

Każda grupa której rząd jest liczbą pierwszą jest cykliczna i izomorficzna z .

Dowód

Ponieważ , to w jest jakiś element . Wtedy rząd jest większy od i dzieli , więc musi wynosić . To oznacza zaś, iż generuje grupę , czyli jest cykliczna. Reszta wynika już z Wniosku 4.11.

End of proof.gif

Obserwacja 4.18

Dla dowolnej grupy rzędu następujące warunki są równoważne:

1. jest grupa cykliczną,

2. dla każdego , grupa ma dokładnie elementów takich, że ,

3. dla każdego , grupa ma dokładnie elementów rzędu .

Dowód

Dla dowodu implikacji (1 2) załóżmy że grupa jest cykliczna i generowana przez . Niech będzie dzielnikiem , czyli dla pewnego . Elementy



są parami różne (bo ma rząd ) oraz wszystkie spełniają równanie , gdyż



Zatem elementów spełniających jest co najmniej . Załóżmy teraz, że pewien spełnia . Ponieważ generuje , mamy dla pewnego , skąd . Z Obserwacji 4.5 mamy , czyli i dla pewnego . Zatem znajduje się na naszej liście rozwiązań równania . To dowodzi, że elementów spełniających jest dokładnie .

Dla dowodu implikacji (2 3) przypomnijmy, za Obserwacją 4.5, że element rzędu spełnia wtedy i tylko wtedy, gdy . A zatem założenie 2 daje



gdzie to liczba elementów rzędu spełniających =1. Wzór inwersyjny Mobiusa daje teraz



Wobec znanego nam już przedstawienia funkcji Eulera przez funkcje Mobiusa, tzn. , mamy .

Wreszcie, dla dowodu ostatniej implikacji (3 1) zauważmy najpierw, że zawsze . To oczywiście daje, że istnieje co najmniej jeden element rzędu w . Element ten generuje więc cały zbiór , stąd jest cykliczna.

End of proof.gif

Przykład

Zbadajmy rzędy elementów grupy cyklicznej .



  • dzielniki liczby to .
  • liczba elementów rzędu dla kolejnych dzielników
  • , , , , , .