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

From Studia Informatyczne

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 {\mathbf G}=(G,*,',e), gdzie G jest dowolnym zbiorem niepustym, * działaniem dwuargumentowym, ' jest działaniem jednoargumentowym, a e\in G, przy czym, dla dowolnych x,y,z\in G, spełnione sa następujące warunki:

  • (łączność) (x*y)*z=x*(y*z),
  • e*x=x*e=x, czyli e to element neutralny grupy {\mathbf G}.
  • x*x'=x'*x=e, czyli x' jest elementem odwrotnym do x w {\mathbf G}.

Rząd grupy skończonej {\mathbf G}=(G,*,e) to liczba \left\vertG\right\vert jej elementów. Gdy grupa {\mathbf G} 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ś x, jeśli istnieje to jest jedyny.

Przykład

{\mathbf \mathbb{Z}}=(\mathbb{Z},+,0), czyli zbiór liczb całkowitych z dodawaniem i elementem neutralnym 0, jest grupą. Rzeczywiście:

  • suma dwu liczb całkowitych zawsze jest liczbą całkowitą,
  • (a+b)+c=a+(b+c) dla dowolnych a,b,c\in\mathbb{Z} (łączność dodawania liczb całkowitych),
  • 0 jest elementem neutralnym, gdyż 0+a=a+0=a,
  • -a jest elementem odwrotnym liczby a, gdyż a+(-a)=(-a)+a=0.

Przykład

Dla dowolnej liczby naturalnej n\geq 1, zbiór reszt modulo n wraz z dodawaniem modulo n, tzn. {\mathbf \mathbb{Z}}_n=(\mathbb{Z}_n,+,0) jest grupą. Rzeczywiście:

  • suma dwu liczb modulo n wpada do zbioru \mathbb{Z}_n,
  • (a+b)+c = a+(b+c) dla dowolnych a,b,c\in\mathbb{Z}_n,
  • 0 jest elementem neutralnym, gdyż 0+a=a+0=a,
  • n-a jest elementem odwrotnym liczby a, gdyż a+(n-a)=(n-a)+a=n\equiv_n 0.

Przykład

{\mathbf S}_n=(S_n,\circ) jest grupą, gdzie S_n to zbiór permutacji zbioru \mathbb{Z}_n={\left\{ {0,\ldots,n-1} \right\} }, a \circ to składanie permutacji. Rzeczywiście:

  • złożenie dwóch permutacji \mathbb{Z}_n jest permutacją \mathbb{Z}_n,
  • składanie funkcji, więc i permutacji, jest łączne,
  • identyczność jest elementem neutralnym przy składaniu funkcji,
  • permutacja odwrotna do \pi jest elementem odwrotnym do \pi w {\mathbf S}_n, gdyż \pi\cdot\pi^{-1}=\pi^{-1}\cdot\pi=id.

Przykład

Gdy \mathbb{Z}_p^*=\mathbb{Z}_p-{\left\{ {0} \right\} }={\left\{ {1,\ldots,p-1} \right\} } oraz p jest liczba pierwszą, to {\mathbf \mathbb{Z}}_p^*=(\mathbb{Z}_p^*,\cdot,1) jest grupą, gdzie działanie \cdot to mnożenie modulo p. Rzeczywiście:

  • gdy a,b\in\mathbb{Z}_p^*, to oczywiście (ab \mbox{ {\sf mod} } p )\in{\left\{ {0,\ldots,p-1} \right\} }. Gdyby jednak ab \mbox{ {\sf mod} } p =0, to ab=qp dla pewnego q>0.

Liczba p byłaby więc rozkładzie ab=p_1\cdot\ldots\cdot p_k, co jest niemożliwe wobec p_i\leqslant\max(a,b)<p.

  • dla dowolnych a,b,c zachodzi
(ab \mbox{ {\sf mod} } p )\cdot c \mbox{ {\sf mod} } p =a\cdot(bc \mbox{ {\sf mod} } p ) \mbox{ {\sf mod} } p .
  • 1 jest elementem neutralnym, gdyż 1\cdot a=a\cdot1=a,
  • Dowolny a\in{\left\{ {1,\ldots,p-1} \right\} }=\mathbb{Z}_p^* ma element odwrotny w {\mathbf \mathbb{Z}_p^*}. Możemy go wskazać np. przy pomocy rozszerzonego algorytmu Euklidesa.

Z pierwszości p mamy \mbox{\sf NWD}(a,p)=1 zatem istnieją x,y takie, że xa+yp=1, czyli xa \mbox{ {\sf mod} } p =1. To oznacza, iż x \mbox{ {\sf mod} } p jest elementem odwrotnym do a w {\mathbf \mathbb{Z}_p^*}.

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

    • a^{p-2}, jeśli p>2,
    • a, jeśli p=2


SW 8.1.swf


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 ({\left\{ {i,p,l,x,y,z} \right\} },\circ, i) jest grupą, gdzie \circ 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

{\left\{ {i,p,l,x,y,z} \right\} }.

\begin{array} {|c|cccccc|} \hline \circ&i&p&l&x&y&z\\ \hline i&i&p&l&x&y&z\\ p&p&l&i&y&z&x\\ l&l&i&p&z&x&y\\ x&x&z&y&i&l&p\\ y&y&x&z&p&i&l\\ z&z&y&x&l&p&i\\ \hline \end{array}
  • Jak zawsze i, 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 p jest oczywiście rotacja w lewo l. Symetrie względem kolejnych osi są same do siebie odwrotne.

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

Obserwacja 4.1 [prawo skracania]

Dla grupy (G,*,e) i x,y,z\in G mamy:

  • (lewostronne) jeśli x*y=x*z, to y=z,
  • (prawostronne) jeśli y*x=z*x, to y=z.

Dowód

Z uwagi na symetrię, pokażemy jedynie pierwszy punkt. Załóżmy zatem, że x*y=x*z i niech x' będzie elementem odwrotnym do x. Wtedy y = 1*y =(x'*x)*y = x'*(x*y) = x'*(x*z) = (x'*x)*z = 1*z=z.

image:End_of_proof.gif

Obserwacja 4.2

Jeśli (G,*,e) jest grupą i a,b\in G, to równanie


a*x=b


ma dokładnie jedno rozwiązanie x w G.

Dowód

Niech a' będzie elementem odwrotnym do a w (G,*). Wtedy x=a'*b jest rozwiązaniem równania, gdyż


a*(a'*b)=(a*a')*b=e*b=b.


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

image: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 (G,*,e) będzie grupą i a\in G. Element neutralny e jest jedynym rozwiązaniem równania e*x=e. Element odwrotny do a jest jedynym rozwiązaniem a*x=e.

image: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 x,y\in G, gdzie {\mathbf G} jest grupą

  • xy oznacza x * y,
  • 1 to jedyny element neutralny grupy {\mathbf G}. Rozważając więcej niż jedną grupę dla jednoznaczności piszemy czasem 1_G.
  • x^{-1} to jedyny element odwrotny do x w {\mathbf G}.

Pamietajmy, że symbol 1 w większości wypadków nie oznacza dobrze znanej liczby 1\in\mathbb{N}. Podobnie nie możemy zakładać, iż działanie \cdot zachowuje prawa zwykłego mnożenia. W szczególności xy=yx zachodzi dalece nie w każdej grupie (np. nie zachodzi w grupie {\mathbf S}_n dla n>2).

Grupa abelowa to {\mathbf G}=(G,\cdot,1), w której działanie \cdot jest przemienne tzn. dla dowolnych x,y\in G mamy


xy=yx.


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

Przykład

Grupy {\mathbf \mathbb{Z}}_n i {\mathbf \mathbb{Z}}_p^* są abelowe, gdyż tak dodawanie, jak i mnożenie modularne jest przemienne.

Grupa przekształceń trójkąta równobocznego ({\left\{ {i,p,l,x,y,z} \right\} },\circ,i) nie jest abelowa, gdyż np. xp\neq px.



SW 8.3.swf

W naturalny sposób w notacji multiplikatywnej definiujemy rekurencyjnie:
Dodatnie i ujemne potęgi elementu x w grupie {\mathbf G}=(G,\cdot,1)


\aligned x^0&=1,\\ x^{n+1}&=x^n\cdot x,\\ x^{-n}&=(x^n)^{-1}. \endaligned


Obserwacja 4.4

Dla dowolnej grupy {\mathbf G}=(G,\cdot,1), x\in G i m,n\in\mathbb{Z} zachodzi


1^m=1,\qquad x^{m+n}=x^mx^n,\qquad x^{mn}=(x^m)^n.


Jeśli {\mathbf G} jest abelowa i x,y\in G, to


(xy)^n = x^n y^n.


Jeśli grupa {\mathbf G}=(G,\cdot,1) ma rząd skończony, to oczywiście dla dowolnego x\in G w ciągu nieujemnych potęg: 1,x,x^2,x^3,\ldots elementy muszą zacząć się powtarzać. Załóżmy zatem, że m<n i x^m=x^n. Mnożąc te równość przez x^{-m} otrzymujemy 1=x^{n-m}. Udowodniliśmy zatem, iż w grupie o skończonym rzędzie każdy element w pewnej dodatniej potędze równy jest 1. Z Zasady Minimum dla każdego elementu istnieje więc najmniejsza taka dodatnia potęga.

Rząd elementu x\in G w grupie {\mathbf G}=(G,\cdot,1) o skończonym rzędzie to najmniejsza dodatnia liczba n taka, że x^n=1. Dla grup nieskończonych rząd elementu jest tak samo zdefiniowany o ile taka liczba istnieje. Jeśli nie to x ma rząd nieskończony.

Obserwacja 4.5

Dla elementu x rzędu m w grupie (G,\cdot,1) mamy x^n=1 wtedy i tylko wtedy, gdy m|n.

Dowód

Jeśli m|n to n=q\cdot m dla pewnego q, a zatem


x^n=x^{qm}=(x^{m})^q=1^q=1.


Na odwrót załóżmy, że x^n=1 dla pewnego n. Niech n=qm+r gdzie 0\leq r<m. Wtedy mamy


1=x^n=x^{qm+r}=(x^m)^qx^r=1^qx^r=x^r,


co wraz z minimalnością m jako rzędu elementu x daje r=0, czyli m|n.

image:End_of_proof.gif

Homomorfizm grup {\mathbf G}_0=(G_0,\cdot,1_{G_0}), {\mathbf G}_1=(G_1,\cdot,1_{G_1}) to dowolna funkcja f:G_0\rightarrow G_1 taka, że dla dowolnych x,y\in G_0 zachodzi


f(xy)=f(x)f(y).


Obserwacja 4.6

Dla dowolnego homomorfizmu f:G_0\rightarrow G_1 grup {\mathbf G_0} i {\mathbf G_1} mamy:

  • f(1_{G_0})=1_{G_1},
  • f(x^{-1})=f(x)^{-1}, dla wszystkich x\in G_0,

Dowód

Oczywiście f(1_{G_0})=f(1_{G_0}\cdot 1_{G_0})=f(1_{G_0})f(1_{G_0}). Prawo skracania w grupie {\mathbf G}_1 daje więc 1_{G_1}=f(1_{G_0}). Z kolei, gdy x\in G_0, to f(x)\cdot f(x^{-1})=f(xx^{-1})=f(1_{G_0})=1_{G_1}, czyli f(x^{-1}) jest elementem odwrotnym do f(x) w {\mathbf G}_1.

image:End_of_proof.gif

Izomorfizm grup to homomorfizm, który jest bijekcją.
Grupy izomorficzne to grupy, miedzy którymi istnieje izomorfizm. Izomorficzność grup {\mathbf G_0} i {\mathbf G_1} zapisujemy {\mathbf G_0}\approx{\mathbf G_1}.

Podgrupa grupy {\mathbf G}=(G,\cdot,1_G) to taka grupa {\mathbf H}=(H,\cdot,1_G), że H\subseteq G oraz mnożenie w grupie {\mathbf H} jest restrykcją mnożenia w {\mathbf G}.

Obserwacja 4.7

Dla \emptyset\neq H\subseteq G, gdzie {\mathbf G}=(G,\cdot,1) jest grupą, jeśli

  • xy\in H dla dowolnych xy\in H,
  • x^{-1}\in H dla dowolnych x\in H,

to {\mathbf H}=(H,\cdot,1) jest podgrupą {\mathbf G}. Ponadto jeśli {\mathbf G} ma rząd skończony, to już pierwszy punkt implikuje, iż {\mathbf H} jest podgrupą grupy {\mathbf G}.

Dowód

Pierwszy punkt gwarantuje, że działanie \cdot nie wyprowadza poza zbiór H. Łączność \cdot w H wynika bezpośrednio z łączności \cdot w G. Drugi punkt świadczy, iż każdy element w H ma element odwrotny także w H. Dla dowodu, że 1\in H skorzystamy z niepustości H i wybierzmy h\in H. Wtedy, z drugiego punktu, h^{-1}\in H, więc 1=hh^{-1}\in H na mocy punktu pierwszego.

Załóżmy teraz, że grupa {\mathbf G} ma rząd skończony oraz podzbiór H \subseteq G jest zamknięty na mnożenie. Wtedy oczywiście wszystkie potęgi o nieujemnych wykładnikach h,h^2,h^3,\ldots wpadają do H. Ponieważ G ma rząd skończony, to rząd dowolnego elementu też jest skończony, czyli istnieje m takie, że h^m=1. Zatem 1\in H i h^{m-1}h=1=hh^{m-1}, czyli h^{m-1}\in H jest elementem odwrotnym do h.

image:End_of_proof.gif

Z Obserwacji 4.7 dostajemy natychmiast:

Wniosek 4.8

Przecięcie dowolnej rodziny podgrup grupy {\mathbf G} jest podgrupą {\mathbf G}.

Grupy cykliczne

Podgrupa generowana przez podzbiór X \subseteq G grupy {\mathbf G}, to przecięcie wszystkich podgrup {\mathbf G} zawierających zbiór X. Podgrupę taką oznaczamy przez {\mathbf G}(X).
Zbiór generatorów grupy {\mathbf G}=(G,\cdot,1) to jakikolwiek zbiór X \subseteq G spełniający G(X)=G.

Obserwacja 4.9

Dla dowolnej grupy {\mathbf G}=(G,\cdot,1) i \emptyset\neq X\subseteq G


G(X)={\left\{ {x_0\cdot\ldots\cdot x_{n-1} :  n\in\mathbb{N} \mbox{ \rm i } (x_i\in X \mbox{ \rm lub }x_i^{-1}\in X)} \right\} }.


Dowód

Oczywiście wszystkie iloczyny postaci x_0\cdot\ldots\cdot x_{n-1} leżą w każdej podgrupie zawierającej X, więc i w G(X). Nadto zbiór Z wszystkich takich iloczynów jest zamknięty na iloczyn i odwracanie, bo (x_0\cdot\ldots\cdot x_{n-1})^{-1}=x_{n-1}^{-1}\cdot x_{n-2}^{-1}\cdot\ldots\cdot x_0^{-1}. A zatem Obserwacja 4.7 gwarantuje, że (Z, \cdot, 1) jest podgrupą. Musi zatem być czynnikiem przecięcia wyznaczającego G(X), czyli G(X)\subseteq Z.

image:End_of_proof.gif

Grupa cykliczna to grupa generowana zbiorem jednoelementowym.

Jeśli {\mathbf G} = {\mathbf G}({\left\{ {x} \right\} }), to G={\left\{ {x^n : n\in \mathbb{Z}} \right\} }. Gdy ponadto {\mathbf G} jest skończona, to jej rząd pokrywa się z rzędem elementu generującego x, czyli G={\left\{ {1,x,x^2,\ldots, x^{\left\vertG\right\vert-1}} \right\} }.

Przykład

Grupa addytywna liczb całkowitych {\mathbf \mathbb{Z}}=(\mathbb{Z},+,0) jest cykliczna. Rzeczywiście {\left\{ {1} \right\} } generuje te grupę:


\begin{array} {lrrrrrrr} \mathbb{Z}=\{\ldots,&-3,&-2,&-1,&0,&1,&2,&3,\ldots\}\\ \mathbb{Z}=\{\ldots,&-1-1-1,&-1-1,&-1,&1-1,&1,&1+1,&1+1+1,\ldots\} \end{array}


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

Przykład

Dla n>0 grupa {\mathbf \mathbb{Z}}_n=(\mathbb{Z}_n,+,0) jest skończoną grupą cykliczną generowaną przez {\left\{ {1} \right\} }. Rzeczywiście:


\mathbb{Z}_n={\left\{ {1,1+1,\ldots,\underbrace{1+1+\ldots+1}_{n\ razy}} \right\} }.


Obserwacja 4.10

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

Dowód

Niech g_i będzie generatorem grupy cyklicznej {\mathbf G_i}, dla i=0,1. Łatwo sprawdzić, że równość rzędów tych grup daje, iż g_0^k =g_0^l wtedy i tylko wtedy, gdy g_1^k =g_1^l. A zatem f:G_0\ni g_0^k \mapsto g_1^k \in G_1 ustala izomorfizm grup {\mathbf G_0} i {\mathbf G_1}.

image:End_of_proof.gif

Wniosek 4.11

Dowolna skończona grupa cykliczna rzędu n jest izomorficzna z \mathbb{Z}_n. Dowolna nieskończona grupa cykliczna jest izomorficzna z \mathbb{Z}.



SW 8.4.swf


SW 8.5.swf


SW 8.6.swf

Przykład

Dla n\geqslant3 rozważymy pewne grupy przekształceń n-kątów foremnych jako podgrupy grupy S_n. Poetykietujmy wierzchołki n-kąta foremnego liczbami 0,\ldots,n-1. Obrót wielokąta foremnego o jeden wierzchołek w prawo, jak na rysunku, odpowiada cyklicznej permutacji \pi=(0,1,\ldots,n-1). Zastanówmy się teraz jakie elementy składają się na {\mathbf S}_n(\pi) i jaka jest ich interpretacja geometryczna.

Rząd cyklu n-elementowego jest oczywiście równy n. Kolejne złożenia \pi,\pi^2,\pi^3,\ldots,\pi^n odpowiadają kolejnym obrotom \pi^k w prawo naszego wielokąta o \frac{360^o}{k}, aż \pi^n przekręca go do pozycji wyjściowej (czyli jest identycznością). Zatem {\mathbf S}_n(\pi) jest grupą cykliczną rzędu n, czyli z Wniosku 4.11 mamy {\mathbf S}_n(\pi)\approx \mathbb{Z}_n.

Zwiększmy trochę zbiór generatorów i do obrotu w prawo dołóżmy symetrię względem jednej z n osi symetrii naszego n-kąta foremnego. W przypadku gdy n jest parzyste osie symetrii przechodzą przez środki przeciwległych boków lub naprzeciwległe wierzchołki, jeśli zaś n 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 2:

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

Na przykład, gdy n jest parzyste oraz :

  • \sigma jest symetrią względem osi przechodzącej przez bok [n-1,0], to \sigma rozkłada się na cykle:

\sigma=(0,n-1)(1,n-2)(2,n-3)\ldots(n/2-1,n/2+1),

  • gdy \sigma jest symetrią względem osi przechodzącej przez wierzchołki 0 i (n+1)/2,

to \sigma rozkłada się na cykle

\sigma=(0)(1,n-1)(2,n-2)\ldots(n/2-1,n/2+1)( (n+1)/2 ),

a dla nieparzystego n:

  • gdy \sigma jest symetrią względem osi przechodzącej przez wierzchołek 0 i bok [n/2, n/2+1], to \sigma rozkłada się na cykle

\sigma=(0)(1,n-1)(2,n-2)(3,n-3)\ldots((n-1)/2,(n+1)/2).

Jakie elementy składają się na {\mathbf S}_n({\left\{ {\pi,\sigma} \right\} })? Jaka jest ich interpretacja geometryczna?

Zbierzmy kilka prostych faktów:

  • \pi^n=id, \pi^{-1}=\pi^{n-1}.
  • \sigma jest inwolucją, czyli jest sama do siebie odwrotna, \sigma^{-1}=\sigma.

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


\aligned \pi\sigma\pi(0)&=\pi\sigma(n-1)=\pi(1)=0=\sigma(0),\\ \pi\sigma\pi(1)&=\pi\sigma(0)=\pi(0)=n-1=\sigma(1),\\ \pi\sigma\pi(i)&=\pi\sigma(i-1)=\pi(n-i+1)=n-i=\sigma(i), \endaligned


dla i\in{\left\{ {2,\ldots,n-1} \right\} }.

Z Obserwacji 4.9 i naszych spostrzeżeń mamy:


\aligned S_n({\left\{ {\pi,\sigma} \right\} }) &={\left\{ {x_0\cdot\ldots\cdot x_{m-1}: m>0, x_i\in{\left\{ {\pi,\pi^{-1},\sigma,\sigma^{-1}} \right\} }} \right\} }\\ &={\left\{ {\pi^k, \pi^k\sigma : 0<k\leq n} \right\} } \endaligned


Zatem podgrupa generowana przez {\left\{ {\pi,\sigma} \right\} } ma co najwyżej 2n elementów. Jako ćwiczenie zostawiamy dowód, że w istocie wymienione elementy są parami różne. Okazuje się, że


\begin{array} {ll} \pi,\pi^2,\pi^3,\ldots,\pi^n&\textrm{- to wszystkie obroty wraz z identycznością},\\ \pi\sigma,\pi^2\sigma,\pi^3\sigma,\ldots,\pi^n\sigma&\textrm{- to symetrie wobec każdej z \textsl{n} osi symetrii \textsl{n}-kąta foremnego}. \end{array}


Grupa dihedralna {\mathbf D}_{n} to podgrupa grupy {\mathbf S_n} (dla n\geqslant3) generowana przez {\left\{ {\pi,\sigma} \right\} }.

Produkt grup {\mathbf G_0}=(G_0,\cdot,1_{G_0}) i {\mathbf G_1}=(G_1,\cdot,1_{G_1}) to grupa {\mathbf G_0}\times{\mathbf G_1}=(G_0\times G_1,\cdot,(1_{G_0},1_{G_1})), w której działanie \cdot zdefiniowane jest przez


(x,y)\cdot(z,w)=(x\cdot z,y\cdot w).


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 \mathbb{Z}_2\times\mathbb{Z}_3.


\mathbb{Z}_2\times \mathbb{Z}_3={\left\{ {(0,0),(0,1),(0,2),(1,0),(1,1),(1,2)} \right\} }.


Zauważmy, że f:\mathbb{Z}_6\rightarrow\mathbb{Z}_2\times\mathbb{Z}_3 zadana przez


f(a) = (a \mbox{ {\sf mod} } 2 , \ a \mbox{ {\sf mod} } 3 )


definiuje izomorfizm grup \mathbb{Z}_6 i \mathbb{Z}_2\times\mathbb{Z}_3.

Czy zawsze \mathbb{Z}_{mn}\approx\mathbb{Z}_m\times\mathbb{Z}_n? Zbadajmy jeszcze jeden przykład: \mathbb{Z}_2\times\mathbb{Z}_4 i \mathbb{Z}_8. Rzędy elementów w produkcie \mathbb{Z}_2\times\mathbb{Z}_4 przedstawia tabela:


\begin{array} {|c||c|c|c|c|c|c|c|c|} \hline \mathbb{Z}_2\times\mathbb{Z}_4&(0,0)&(0,1)&(0,2)&(0,3)&(1,0)&(1,1)&(1,2)&(1,3)\\ \hline \textrm{rząd}&1&4&2&4&2&4&2&4\\ \hline \end{array}


A zatem grupa \mathbb{Z}_2\times\mathbb{Z}_4 nie ma elementu rzędu 8, nie może więc być izomorficzna z cykliczna grupą \mathbb{Z}_8.

Obserwacja 4.12

Jeśli m\perp n, to \mathbb{Z}_m\times\mathbb{Z}_n \approx \mathbb{Z}_{mn}.

Dowód

Wystarczy oczywiście pokazać, że rząd elementu (1,1)\in\mathbb{Z}_m\times\mathbb{Z}_n wynosi mn, wtedy bowiem grupa \mathbb{Z}_m\times\mathbb{Z}_n będzie cykliczna i, jako mn-elementowa, musi być izomorficzna z \mathbb{Z}_{mn}.

Niech więc r będzie rzędem (1,1) w grupie \mathbb{Z}_m\times\mathbb{Z}_n. Licząc kolejno na obu osiach produktu dostajemy


\aligned \underbrace{1+\ldots+1}_{r\ razy} \mbox{ {\sf mod} } m &=r \mbox{ {\sf mod} } m =0,\textrm{ czyli \textsl{m|r},}\\ \underbrace{1+\ldots+1}_{r\ razy} \mbox{ {\sf mod} } n &=r \mbox{ {\sf mod} } n =0,\textrm{ czyli \textsl{n|r}}. \endaligned


Zatem r jest najmniejszą wspólną wielokrotnością m i n. Ponieważ m\perp n, to


r=\mbox{\sf NWW}(m,n)=\frac{mn}{\mbox{\sf NWD}(m,n)}=\frac{mn}{1}=mn.


image: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 {\mathbf H} jest podgrupą skończonej grupy {\mathbf G}, to rząd {\mathbf H} dzieli rząd {\mathbf G}. Zwracamy jednak uwagę, iż to nie oznacza, że grupa {\mathbf G} ma podgrupy o rzędzie będącym jakimkolwiek dzielnikiem rzędu grupy {\mathbf G}.

Przykład

Niech {\mathbf A}_4 będzie podgrupą grupy {\mathbf S}_4 składającą się z tych permutacji, które są złożeniami parzystej liczby transpozycji. Wtedy \left\vertA_4\right\vert=12, ale grupa {\mathbf A}_4 nie ma podgrup rzędu 4.

Lewa warstwa gH podgrupy {\mathbf H} grupy {\mathbf G} względem elementu g\in G to zbiór


gH={\left\{ {gh : h\in H} \right\} }.


Prawa warstwa Hg podgrupy {\mathbf H} grupy {\mathbf G} względem elementu g\in G to zbiór


Hg={\left\{ {hg : h\in H} \right\} }.


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

Przykład

Niech {\mathbf D}_4=({\left\{ {\pi,\ldots,\pi^4,\pi\sigma,\ldots,\pi^4\sigma} \right\} },\circ) będzie grupa dihedralną symetrii kwadratu. Posiada ona podgrupę cykliczną {\mathbf C}_4=({\left\{ {\pi,\pi^2,\pi^3,\pi^4} \right\} },\circ). Niech \sigma będzie symetrią osiową. Zauważmy, że elementy lewej warstwy


\sigma C_4={\left\{ {\sigma\pi,\sigma\pi^2,\sigma\pi^3,\sigma\pi^4} \right\} }.


wszystkie symetrie osiowe kwadratu. Jako ćwiczenie pozostawiamy wyznaczenie warstw \pi C_4, \pi^2 C_4 oraz \sigma\pi^2 C_4.

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

Obserwacja 4.13

Jeśli {\mathbf H} jest skończoną podgrupą grupy {\mathbf G} i g\in G, to \left\vertgH\right\vert=\left\vertH\right\vert= \left\vertHg\right\vert.

Dowód

Niech H={\left\{ {h_0,\ldots,h_{m-1}} \right\} } i załóżmy, że gh_i=gh_j. Wtedy z prawa skracania mamy h_i=h_j. Zatem elementy gh_0,gh_1,\cdots,gh_{m-1} są parami różne i zbiór


gH={\left\{ {gh_0,gh_1,\cdots,gh_{m-1}} \right\} },


ma dokładnie m elementów.

image:End_of_proof.gif

Obserwacja 4.14

Dla dowolnej podgrupy {\mathbf H} grupy {\mathbf G} i g_0,g_1\in G lewe warstwy g_0 H, g_1H są albo identyczne albo rozłączne.

Dowód

Pokażemy, że jeśli g_0 H i g_1 H mają jakiś wspólny element to są one identyczne. Załóżmy zatem, że x\in g_0 H \cap g_1 H, czyli g_0 h_0 =x= g_1 h_1 dla pewnych h_0,h_1\in H. Wtedy g_0=g_1 h_1 h_0^{-1} \in g_1H. Dla dowodu inkluzji g_0 H \subseteq g_1 H, niech y\in g_0 H, czyli y=g_0h dla pewnego h\in H. Wtedy


y=g_0 h=g_1 h_1 h_0^{-1} h,


co wobec h_1,h_0^{-1},h\in H daje y\in g_1H.

image:End_of_proof.gif

Twierdzenie 4.15[Lagrange'a]

Dla dowolnej podgrupy {\mathbf H} skończonej grupy {\mathbf G}, rząd {\mathbf H} dzieli rząd {\mathbf G}.

Dowód

Niech {\mathbf H}=({\left\{ {h_0,\ldots,h_{m-1}} \right\} },\cdot,1) oraz {\mathbf G}=({\left\{ {g_0,\ldots,g_{n-1}} \right\} },\cdot,1). Ponieważ:

  • każdy g_i jest we własnej warstwie g_iH, gdyż g_i\cdot1\in g_iH,
  • \left\vertg_iH\right\vert=\left\vertH\right\vert dla dowolnego i,
  • lewe warstwy g_iH, g_jH są albo identyczne albo rozłączne,

to lewe warstwy g_0H,g_1H,\ldots,g_{n-1}H tworzą podział zbioru G={\left\{ {g_0,g_1\ldots,g_{n-1}} \right\} } na równoliczne bloki wielkości m, skąd natychmiast m|n.

image:End_of_proof.gif

Wniosek 4.16

Niech {\mathbf G}=(G,\cdot,1) będzie grupą rzędu n. Wtedy dla g \in G mamy:

  • rząd elementu g dzieli n,
  • g^n=1.

Dowód

Niech r będzie rzędem elementu g\in G. Wtedy r jest rzędem podgrupy cyklicznej {\mathbf G}(g) = ({\left\{ {g,g^2,\ldots,g^r} \right\} },\cdot,1). Z Twierdzenia Lagrange'a r, czyli rząd tej podgrupy cyklicznej, dzieli n. Skoro teraz n=kr to oczywiście x^n= x^{kr} = (x^r)^k = 1^k =1

image:End_of_proof.gif

Wniosek 4.17

Każda grupa {\mathbf G} której rząd jest liczbą pierwszą p jest cykliczna i izomorficzna z \mathbb{Z}_p.

Dowód

Ponieważ p>1, to w G jest jakiś element g\neq1. Wtedy rząd g jest większy od 1 i dzieli p, więc musi wynosić p. To oznacza zaś, iż g generuje grupę {\mathbf G}, czyli {\mathbf G} jest cykliczna. Reszta wynika już z Wniosku 4.11.

image:End_of_proof.gif

Obserwacja 4.18

Dla dowolnej grupy {\mathbf G}=(G,\cdot,1) rzędu n\geq 2 następujące warunki są równoważne:

1. {\mathbf G} jest grupa cykliczną,

2. dla każdego d|n, grupa {\mathbf G} ma dokładnie d elementów x\in G takich, że x^d=1,

3. dla każdego d|n, grupa {\mathbf G} ma dokładnie \varphi(d) elementów rzędu d.

Dowód

Dla dowodu implikacji (1 \Rightarrow 2) załóżmy że grupa {\mathbf G} jest cykliczna i generowana przez g. Niech d będzie dzielnikiem n, czyli n=dq dla pewnego q. Elementy


1,g^q,g^{2q},\ldots,g^{(d-1)q}


są parami różne (bo g ma rząd n=dq) oraz wszystkie spełniają równanie x^d=1, gdyż


(g^{iq})^d=(g^{dq})^i=1^i=1.


Zatem elementów x\in G spełniających x^d=1 jest co najmniej d. Załóżmy teraz, że pewien y\in G spełnia y^d=1. Ponieważ g generuje {\mathbf G}, mamy y=g^k dla pewnego k, skąd g^{kd}=y^d=1. Z Obserwacji 4.5 mamy n|kd, czyli kd=fn=fdq i k=fq dla pewnego f. Zatem y=g^{k}=g^{fq} znajduje się na naszej liście rozwiązań równania x^d=1. To dowodzi, że elementów x\in G spełniających x^d=1 jest dokładnie d.

Dla dowodu implikacji (2 \Rightarrow 3) przypomnijmy, za Obserwacją 4.5, że element x rzędu r spełnia x^d=1 wtedy i tylko wtedy, gdy r|d. A zatem założenie 2 daje


\displaystyle d=\sum_{r|d}f(r),


gdzie f(r) to liczba elementów rzędu r spełniających x^d=1. Wzór inwersyjny Mobiusa daje teraz


\displaystyle f(d)=\sum_{r|d}\mu(r)\frac{d}{r}.


Wobec znanego nam już przedstawienia funkcji Eulera przez funkcje Mobiusa, tzn. \displaystyle \varphi(d)=\sum_{r|d}\mu(r)\frac{d}{f}, mamy f(d)=\varphi(d).

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

image:End_of_proof.gif

Przykład

Zbadajmy rzędy elementów grupy cyklicznej \mathbb{Z}_{12}.


\begin{array} {|c|c|c|c|c|c|c|c|c|c|c|c|} \hline 0&1&2&3&4&5&6&7&8&9&10&11\\ \hline 1&12&6&4&3&12&2&12&3&4&6&12\\ \hline \end{array}


  • dzielniki liczby 12 to 1,2,3,4,6,12.
  • liczba elementów rzędu d dla kolejnych dzielników d|12
\begin{array} {|c|c|c|c|c|c|c|} \hline \textrm{dzielnik \textsl{d} liczby \textsl{12}}&1&2&3&4&6&12\\ \hline \textrm{liczba elementów rzędu \textsl{d}}&1&1&2&2&2&4\\ \hline \end{array}
  • \varphi(1)=1, \varphi(2)=1, \varphi(3)=2, \varphi(4)=2, \varphi(6)=2, \varphi(12)=4.