Matematyka dyskretna 2/Wykład 4: Elementy teorii grup: Różnice pomiędzy wersjami

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
Arek (dyskusja | edycje)
Nie podano opisu zmian
m Zastępowanie tekstu – „,↵</math>” na „</math>,”
 
(Nie pokazano 31 wersji utworzonych przez 5 użytkowników)
Linia 8: Linia 8:
Euler, Gauss, Lagrange, Abel i Galois byli pionierami badań w tej dziedzinie.  
Euler, Gauss, Lagrange, Abel i Galois byli pionierami badań w tej dziedzinie.  
W szczególności, Galois jest uważany za pierwszego matematyka,  
W szczególności, Galois jest uważany za pierwszego matematyka,  
który powiązał teorię grup z teorią ciał.
2który powiązał teorię grup z teorią ciał.


'''Grupa''' to uporządkowana czwórka <math>{\mathbf G}=(G,*,',e)</math>,  
'''Grupa''' to uporządkowana czwórka <math>{\mathbf G}=(G,*,',e)</math>,  
Linia 19: Linia 19:
* ('''łączność''') <math>(x*y)*z=x*(y*z)</math>,  
* ('''łączność''') <math>(x*y)*z=x*(y*z)</math>,  


* <math>e*x=x*e=x</math>,  
* <math>e*x=x*e=x</math>, czyli <math>e</math> to '''element neutralny''' grupy <math>{\mathbf G}</math>.
czyli <math>e</math> to '''element neutralny''' grupy <math>{\mathbf G}</math>.


* <math>x*x'=x'*x=e</math>, czyli <math>x'</math> jest '''elementem odwrotnym''' do <math>x</math> w <math>{\mathbf G}</math>.
* <math>x*x'=x'*x=e</math>, czyli <math>x'</math> jest '''elementem odwrotnym''' do <math>x</math> w <math>{\mathbf G}</math>.


'''Rząd grupy skończonej''' <math>{\mathbf G}=(G,*,e)</math> to liczba <math>\left\vertG\right\vert</math> jej elementów.
'''Rząd grupy skończonej''' <math>{\mathbf G}=(G,*,e)</math> to liczba <math>\left\vert G \right\vert</math> jej elementów.
Gdy grupa <math>{\mathbf G}</math> nie jest skończona, to mówimy, że ma rząd nieskończony.
Gdy grupa <math>{\mathbf G}</math> nie jest skończona, to mówimy, że ma rząd nieskończony.


Linia 41: Linia 40:
* suma dwu liczb całkowitych zawsze jest liczbą całkowitą,
* suma dwu liczb całkowitych zawsze jest liczbą całkowitą,


* <math>(a+b)+c=a+(b+c)</math> dla dowolnych <math>a,b,c\in\mathbb{Z}</math>  
* <math>(a+b)+c=a+(b+c)</math> dla dowolnych <math>a,b,c\in\mathbb{Z}</math> (łączność dodawania liczb całkowitych),
(łączność dodawania liczb całkowitych),


* <math>0</math> jest elementem neutralnym, gdyż <math>0+a=a+0=a</math>,
* <math>0</math> jest elementem neutralnym, gdyż <math>0+a=a+0=a</math>,
Linia 76: Linia 74:
* identyczność jest elementem neutralnym przy składaniu funkcji,  
* identyczność jest elementem neutralnym przy składaniu funkcji,  


* permutacja odwrotna do <math>\pi</math> jest elementem odwrotnym do <math>\pi</math> w <math>{\mathbf S}_n</math>,  
* permutacja odwrotna do <math>\pi</math> jest elementem odwrotnym do <math>\pi</math> w <math>{\mathbf S}_n</math>, gdyż <math>\pi\cdot\pi^{-1}=\pi^{-1}\cdot\pi=id</math>.
gdyż <math>\pi\cdot\pi^{-1}=\pi^{-1}\cdot\pi=id</math>.


}}
}}
Linia 87: Linia 84:
gdzie działanie <math>\cdot</math> to mnożenie modulo <math>p</math>. Rzeczywiście:
gdzie działanie <math>\cdot</math> to mnożenie modulo <math>p</math>. Rzeczywiście:


* gdy <math>a,b\in\mathbb{Z}_p^*</math>, to oczywiście <math>(ab \mbox{ {\sf mod} } p )\in{\left\{ {0,\ldots,p-1} \right\} }</math>.  
* gdy <math>a,b\in\mathbb{Z}_p^*</math>, to oczywiście <math>(ab \mathsf{ mod} p )\in{\left\{ {0,\ldots,p-1} \right\} }</math>. Gdyby jednak <math>ab \mathsf{ mod} p =0</math>, to <math>ab=qp</math> dla pewnego <math>q>0</math>.  
Gdyby jednak <math>ab \mbox{ {\sf mod} } p =0</math>, to <math>ab=qp</math> dla pewnego <math>q>0</math>.  
Liczba <math>p</math> byłaby więc rozkładzie <math>ab=p_1\cdot\ldots\cdot p_k</math>, co jest niemożliwe wobec  
Liczba <math>p</math> byłaby więc rozkładzie <math>ab=p_1\cdot\ldots\cdot p_k</math>, co jest niemożliwe wobec  
<math>p_i\leqslant\max(a,b)<p</math>.  
<math>p_i\leqslant\max(a,b)<p</math>.  
Linia 94: Linia 90:
* dla dowolnych <math>a,b,c</math> zachodzi
* dla dowolnych <math>a,b,c</math> zachodzi


<center><math>(ab \mbox{ {\sf mod} } p )\cdot c \mbox{ {\sf mod} } p =a\cdot(bc \mbox{ {\sf mod} } p ) \mbox{ {\sf mod} } p .
<center><math>(ab \mathsf{ mod} p )\cdot c \mathsf{ mod} p =a\cdot(bc \mathsf{ mod} p ) \mathsf{ mod} p </math></center>
</math></center>


* <math>1</math> jest elementem neutralnym, gdyż <math>1\cdot a=a\cdot1=a</math>,
* <math>1</math> jest elementem neutralnym, gdyż <math>1\cdot a=a\cdot1=a</math>,


* Dowolny <math>a\in{\left\{ {1,\ldots,p-1} \right\} }=\mathbb{Z}_p^*</math> ma element odwrotny w  
* Dowolny <math>a\in{\left\{ {1,\ldots,p-1} \right\} }=\mathbb{Z}_p^*</math> ma element odwrotny w <math>{\mathbf \mathbb{Z}_p^*}</math>. Możemy go wskazać np. przy pomocy rozszerzonego algorytmu Euklidesa.  
<math>{\mathbf \mathbb{Z}_p^*}</math>.  
Z pierwszości <math>p</math> mamy <math>\mathsf{ NWD}(a,p)=1</math> zatem istnieją <math>x,y</math> takie,  
Możemy go wskazać np. przy pomocy rozszerzonego algorytmu Euklidesa.  
że <math>xa+yp=1</math>, czyli <math>xa \mathsf{ mod} p =1</math>. To oznacza, iż <math>x \mathsf{ mod} p</math> jest elementem odwrotnym do <math>a</math> w <math>{\mathbf \mathbb{Z}_p^*}</math>.
Z pierwszości <math>p</math> mamy <math>\mbox{\sf NWD}(a,p)=1</math> zatem istnieją <math>x,y</math> takie,  
że <math>xa+yp=1</math>, czyli <math>xa \mbox{ {\sf mod} } p =1</math>.  
To oznacza, iż <math>x \mbox{ {\sf mod} } p </math> jest elementem odwrotnym do <math>a</math> w <math>{\mathbf \mathbb{Z}_p^*}</math>.


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


** <math>a^{p-2}</math>, jeśli <math>p>2</math>,
** <math>a^{p-2}</math>, jeśli <math>p>2</math>,
Linia 114: Linia 105:


}}
}}
[[File:SW 8.1.svg|250x250px|thumb|left|SW 8.1.swf]]
[[File:SW 8.2.svg|250x250px|thumb|right|SW 8.2.swf]]


{{przyklad|||
{{przyklad|||
Rozważmy trójkąt równoboczny z poetykietowanymi wierzchołkami
Rozważmy trójkąt równoboczny z poetykietowanymi wierzchołkami
''Rysunek:'' 8.1 Szkic na kartce.


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


''Rysunek:'' 8.2 Szkic na kartce.


Wtedy <math>({\left\{ {i,p,l,x,y,z} \right\} },\circ, i)</math> jest grupą,  
Wtedy <math>({\left\{ {i,p,l,x,y,z} \right\} },\circ, i)</math> jest grupą,  
gdzie <math>\circ</math> jest składaniem przekształceń.
gdzie <math>\circ</math> jest składaniem przekształceń.


* Poniższa tabela pokazuje wyniki wszystkich możliwych złożeń,  
* Poniższa tabela pokazuje wyniki wszystkich możliwych złożeń, a tym samym pokazuje, że składanie nie wyprowadza poza zbiór  
a tym samym pokazuje, że składanie nie wyprowadza poza zbiór  
<math>{\left\{ {i,p,l,x,y,z} \right\} }</math>.
<math>{\left\{ {i,p,l,x,y,z} \right\} }</math>.


Linia 147: Linia 138:
* Jak zawsze <math>i</math>, będąc identycznością, jest elementem neutralnym dla składania.
* Jak zawsze <math>i</math>, będąc identycznością, jest elementem neutralnym dla składania.


* Każde z rozważanych przekształceń ma odwrotne do siebie.  
* Każde z rozważanych przekształceń ma odwrotne do siebie. Odwrotnym przekształceniem do rotacji w prawo <math>p</math> jest oczywiście rotacja w lewo <math>l</math>. Symetrie względem kolejnych osi są same do siebie odwrotne.
Odwrotnym przekształceniem do rotacji w prawo <math>p</math> jest oczywiście rotacja w lewo <math>l</math>.  
Symetrie względem kolejnych osi są same do siebie odwrotne.
 
Zauważmy, że w każdym wierszu (i każdej kolumnie) występuje <math>i</math>,  
Zauważmy, że w każdym wierszu (i każdej kolumnie) występuje <math>i</math>,  
skąd też można wywnioskować istnienie elementów odwrotnych.
skąd też można wywnioskować istnienie elementów odwrotnych.
Linia 156: Linia 144:
}}
}}


{{obserwacja|prawo skracania||
{{obserwacja|4.1 [prawo skracania]|obs 4.1|
 
Dla grupy <math>(G,*,e)</math> i <math>x,y,z\in G</math> mamy:
Dla grupy <math>(G,*,e)</math> i <math>x,y,z\in G</math> mamy:


Linia 172: Linia 159:
}}
}}


{{obserwacja|||
{{obserwacja|4.2|obs 4.2|
Jeśli <math>(G,*,e)</math> jest grupą i <math>a,b\in G</math>, to równanie  
Jeśli <math>(G,*,e)</math> jest grupą i <math>a,b\in G</math>, to równanie  


<center><math>a*x=b
<center><math>a*x=b
</math></center>
</math></center>


ma dokładnie jedno rozwiązanie <math>x</math> w <math>G</math>.
ma dokładnie jedno rozwiązanie <math>x</math> w <math>G</math>.
Linia 185: Linia 174:
Wtedy <math>x=a'*b</math> jest rozwiązaniem równania, gdyż  
Wtedy <math>x=a'*b</math> jest rozwiązaniem równania, gdyż  


<center><math>a*(a'*b)=(a*a')*b=e*b=b.
 
</math></center>
<center><math>a*(a'*b)=(a*a')*b=e*b=b</math></center>
 


Dla dowodu jednoznaczności załóżmy, że <math>x_0</math> i <math>x_1</math> są rozwiązaniami naszego równania.  
Dla dowodu jednoznaczności załóżmy, że <math>x_0</math> i <math>x_1</math> są rozwiązaniami naszego równania.  
Linia 192: Linia 182:
}}
}}


{{wniosek|||
{{wniosek|4.3|wn 4.3|
Każda grupa ma dokładnie jeden element spełniający warunki elementu neutralnego  
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.
oraz każdy jej element ma dokładnie jeden element odwrotny.
Linia 209: Linia 199:
* <math>xy</math> oznacza <math>x * y</math>,
* <math>xy</math> oznacza <math>x * y</math>,


* <math>1</math> to jedyny element neutralny grupy <math>{\mathbf G}</math>.  
* <math>1</math> to jedyny element neutralny grupy <math>{\mathbf G}</math>. Rozważając więcej niż jedną grupę dla jednoznaczności piszemy czasem <math>1_G</math>.
Rozważając więcej niż jedną grupę dla jednoznaczności piszemy czasem <math>1_G</math>.


* <math>x^{-1}</math> to jedyny element odwrotny do <math>x</math> w <math>{\mathbf G}</math>.
* <math>x^{-1}</math> to jedyny element odwrotny do <math>x</math> w <math>{\mathbf G}</math>.
Linia 222: Linia 211:
w której działanie <math>\cdot</math> jest przemienne tzn. dla dowolnych <math>x,y\in G</math> mamy
w której działanie <math>\cdot</math> jest przemienne tzn. dla dowolnych <math>x,y\in G</math> mamy


<center><math>xy=yx.
 
</math></center>
<center><math>xy=yx</math></center>
 


Nazwa grup abelowych pochodzi od nazwiska Nielsa Abela,  
Nazwa grup abelowych pochodzi od nazwiska Nielsa Abela,  
Linia 235: Linia 225:
nie jest abelowa, gdyż np. <math>xp\neq px</math>.
nie jest abelowa, gdyż np. <math>xp\neq px</math>.


''Rysunek:'' 8.3 Szkic na kartce
}}


}}
<center>
[[File:SW 8.3.svg|350x350px|thumb|SW 8.3.svg]]
</center>


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


<center><math>\aligned x^0&=&1,\\
x^{n+1}&=&x^n\cdot x,\\
x^{-n}&=&(x^n)^{-1}.
\endaligned</math></center>


{{obserwacja|||
<center><math>\begin{align} x^0&=1,\\
x^{n+1}&=x^n\cdot x,\\
x^{-n}&=(x^n)^{-1}.
\end{align}</math></center>
 
 
{{obserwacja|4.4|obs 4.4|
Dla dowolnej grupy <math>{\mathbf G}=(G,\cdot,1)</math>, <math>x\in G</math> i <math>m,n\in\mathbb{Z}</math> zachodzi
Dla dowolnej grupy <math>{\mathbf G}=(G,\cdot,1)</math>, <math>x\in G</math> i <math>m,n\in\mathbb{Z}</math> zachodzi


<center><math>1^m=1,\qquad x^{m+n}=x^mx^n,\qquad x^{mn}=(x^m)^n.
 
</math></center>
<center><math>1^m=1,\qquad x^{m+n}=x^mx^n,\qquad x^{mn}=(x^m)^n</math></center>
 


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


<center><math>(xy)^n = x^n y^n.
 
</math></center>
<center><math>(xy)^n = x^n y^n</math></center>
 


}}
}}
Linia 274: Linia 270:
o ile taka liczba istnieje. Jeśli nie to <math>x</math> ma rząd nieskończony.
o ile taka liczba istnieje. Jeśli nie to <math>x</math> ma rząd nieskończony.


{{obserwacja|||
{{obserwacja|4.5|obs 4.5|
 
Dla elementu <math>x</math> rzędu <math>m</math> w grupie <math>(G,\cdot,1)</math>
Dla elementu <math>x</math> rzędu <math>m</math> w grupie <math>(G,\cdot,1)</math>
mamy <math>x^n=1</math> wtedy i tylko wtedy, gdy <math>m|n</math>.
mamy <math>x^n=1</math> wtedy i tylko wtedy, gdy <math>m|n</math>.
Linia 283: Linia 278:
Jeśli <math>m|n</math> to <math>n=q\cdot m</math> dla pewnego <math>q</math>, a zatem
Jeśli <math>m|n</math> to <math>n=q\cdot m</math> dla pewnego <math>q</math>, a zatem


<center><math>x^n=x^{qm}=(x^{m})^q=1^q=1.
 
</math></center>
<center><math>x^n=x^{qm}=(x^{m})^q=1^q=1</math></center>
 


Na odwrót załóżmy, że <math>x^n=1</math> dla pewnego <math>n</math>.  
Na odwrót załóżmy, że <math>x^n=1</math> dla pewnego <math>n</math>.  
Linia 290: Linia 286:
Wtedy mamy
Wtedy mamy


<center><math>1=x^n=x^{qm+r}=(x^m)^qx^r=1^qx^r=x^r,
 
</math></center>
<center><math>1=x^n=x^{qm+r}=(x^m)^qx^r=1^qx^r=x^r</math>,</center>
 


co wraz z minimalnością <math>m</math> jako rzędu elementu <math>x</math> daje <math>r=0</math>, czyli <math>m|n</math>.
co wraz z minimalnością <math>m</math> jako rzędu elementu <math>x</math> daje <math>r=0</math>, czyli <math>m|n</math>.
Linia 301: Linia 298:
zachodzi
zachodzi


<center><math>f(xy)=f(x)f(y).
</math></center>


{{obserwacja|||
<center><math>f(xy)=f(x)f(y)</math></center>
 
 
{{obserwacja|4.6|obs 4.6|
Dla dowolnego homomorfizmu <math>f:G_0\rightarrow G_1</math> grup  
Dla dowolnego homomorfizmu <math>f:G_0\rightarrow G_1</math> grup  
<math>{\mathbf G_0}</math> i <math>{\mathbf G_1}</math> mamy:
<math>{\mathbf G_0}</math> i <math>{\mathbf G_1}</math> mamy:
Linia 330: Linia 328:
oraz mnożenie w grupie <math>{\mathbf H}</math> jest restrykcją mnożenia w <math>{\mathbf G}</math>.
oraz mnożenie w grupie <math>{\mathbf H}</math> jest restrykcją mnożenia w <math>{\mathbf G}</math>.


{{obserwacja|||
{{obserwacja|4.7|obs 4.7|
 
Dla <math>\emptyset\neq H\subseteq G</math>, gdzie <math>{\mathbf G}=(G,\cdot,1)</math> jest grupą, jeśli
Dla <math>\emptyset\neq H\subseteq G</math>, gdzie <math>{\mathbf G}=(G,\cdot,1)</math> jest grupą, jeśli


Linia 360: Linia 357:
}}
}}


Z Obserwacji [[##obserwacja - warunki wystarczajace na podgrupe|Uzupelnic obserwacja - warunki wystarczajace na podgrupe|]] dostajemy natychmiast:
Z [[#obs_4.7|Obserwacji 4.7]] dostajemy natychmiast:


{{wniosek|||
{{wniosek|4.8|wn 4.8|
Przecięcie dowolnej rodziny podgrup grupy
Przecięcie dowolnej rodziny podgrup grupy
<math>{\mathbf G}</math> jest podgrupą <math>{\mathbf G}</math>.
<math>{\mathbf G}</math> jest podgrupą <math>{\mathbf G}</math>.
Linia 376: Linia 373:
to jakikolwiek zbiór <math>X \subseteq G</math> spełniający <math>G(X)=G</math>.
to jakikolwiek zbiór <math>X \subseteq G</math> spełniający <math>G(X)=G</math>.


{{obserwacja|||
{{obserwacja|4.9|obs 4.9|


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


<center><math>G(X)={\left\{ {x_0\cdot\ldots\cdot x_{n-1} :  
<center><math>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\} }.
n\in\mathbb{N} \mbox{ i } (x_i\in X \mbox{ lub }x_i^{-1}\in X)} \right\} }</math></center>
</math></center>
 


}}
}}
Linia 392: Linia 390:
Nadto zbiór <math>Z</math> wszystkich takich iloczynów jest zamknięty na iloczyn i odwracanie,   
Nadto zbiór <math>Z</math> wszystkich takich iloczynów jest zamknięty na iloczyn i odwracanie,   
bo <math>(x_0\cdot\ldots\cdot x_{n-1})^{-1}=x_{n-1}^{-1}\cdot x_{n-2}^{-1}\cdot\ldots\cdot x_0^{-1}</math>.
bo <math>(x_0\cdot\ldots\cdot x_{n-1})^{-1}=x_{n-1}^{-1}\cdot x_{n-2}^{-1}\cdot\ldots\cdot x_0^{-1}</math>.
A zatem Obserwacja [[##obserwacja - warunki wystarczajace na podgrupe|Uzupelnic obserwacja - warunki wystarczajace na podgrupe|]] gwarantuje,  
A zatem [[#obs_4.7|Obserwacja 4.7]] gwarantuje,  
że <math>(Z, \cdot, 1)</math> jest podgrupą.  
że <math>(Z, \cdot, 1)</math> jest podgrupą.  
Musi zatem być czynnikiem przecięcia wyznaczającego <math>G(X)</math>, czyli  
Musi zatem być czynnikiem przecięcia wyznaczającego <math>G(X)</math>, czyli  
Linia 403: Linia 401:
<math>G={\left\{ {x^n : n\in \mathbb{Z}} \right\} }</math>.
<math>G={\left\{ {x^n : n\in \mathbb{Z}} \right\} }</math>.
Gdy ponadto <math>{\mathbf G}</math> jest skończona, to jej rząd pokrywa się z rzędem  
Gdy ponadto <math>{\mathbf G}</math> jest skończona, to jej rząd pokrywa się z rzędem  
elementu generującego <math>x</math>, czyli <math>G={\left\{ {1,x,x^2,\ldots, x^{\left\vertG\right\vert-1}} \right\} }</math>.
elementu generującego <math>x</math>, czyli <math>G={\left\{ {1,x,x^2,\ldots, x^{\left\vert G \right\vert-1}} \right\} }</math>.


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


<center><math>\begin{array} {lrrrrrrr}
<center><math>\begin{array} {lrrrrrrr}
Linia 414: Linia 413:
\end{array}  
\end{array}  
</math></center>
</math></center>


Czy grupa ta ma jeszcze jakiś inny jednoelemtowy zbiór generujacy?
Czy grupa ta ma jeszcze jakiś inny jednoelemtowy zbiór generujacy?
Linia 422: Linia 422:
generowaną przez <math>{\left\{ {1} \right\} }</math>. Rzeczywiście:
generowaną przez <math>{\left\{ {1} \right\} }</math>. Rzeczywiście:


<center><math>\mathbb{Z}_n={\left\{ {1,1+1,\ldots,\underbrace{1+1+\ldots+1}_{n\ razy}} \right\} }.
 
</math></center>
<center><math>\mathbb{Z}_n={\left\{ {1,1+1,\ldots,\underbrace{1+1+\ldots+1}_{n\ razy}} \right\} }</math></center>
 


}}
}}


{{obserwacja|||
{{obserwacja|4.10|obs 4.10|
Dowolne dwie grupy cykliczne tego samego rzędu są izomorficzne.
Dowolne dwie grupy cykliczne tego samego rzędu są izomorficzne.
}}
}}
Linia 439: Linia 440:
}}
}}


{{wniosek|||
{{wniosek|4.11|obs 4.11|
 
Dowolna skończona grupa cykliczna rzędu <math>n</math> jest izomorficzna z <math>\mathbb{Z}_n</math>.  
Dowolna skończona grupa cykliczna rzędu <math>n</math> jest izomorficzna z <math>\mathbb{Z}_n</math>.  
Dowolna nieskończona grupa cykliczna jest izomorficzna z <math>\mathbb{Z}</math>.
Dowolna nieskończona grupa cykliczna jest izomorficzna z <math>\mathbb{Z}</math>.
}}
}}
[[File:SW 8.4.svg|250x150px|thumb|right|SW 8.4.swf]]
[[File:SW 8.5.svg|250x250px|thumb|right|SW 8.5.swf]]
[[File:SW 8.6.svg|250x150px|thumb|right|SW 8.6.swf]]


{{przyklad|||
{{przyklad|||
Linia 449: Linia 455:
jako podgrupy grupy <math>S_n</math>.
jako podgrupy grupy <math>S_n</math>.
Poetykietujmy wierzchołki <math>n</math>-kąta foremnego liczbami <math>0,\ldots,n-1</math>.
Poetykietujmy wierzchołki <math>n</math>-kąta foremnego liczbami <math>0,\ldots,n-1</math>.
Obrót wielokąta foremnego o jeden wierzchołek w prawo, jak na rysunku,
Obrót wielokąta foremnego o jeden wierzchołek w prawo, jak na rysunku, odpowiada cyklicznej permutacji <math>\pi=(0,1,\ldots,n-1)</math>.  
 
''Rysunek:'' 8.4 Szkic na kartce.
 
odpowiada cyklicznej permutacji <math>\pi=(0,1,\ldots,n-1)</math>.  
Zastanówmy się teraz jakie elementy składają się na <math>{\mathbf S}_n(\pi)</math>   
Zastanówmy się teraz jakie elementy składają się na <math>{\mathbf S}_n(\pi)</math>   
i jaka jest ich interpretacja geometryczna.
i jaka jest ich interpretacja geometryczna.
Linia 462: Linia 464:
aż <math>\pi^n</math> przekręca go do pozycji wyjściowej (czyli jest identycznością).  
aż <math>\pi^n</math> przekręca go do pozycji wyjściowej (czyli jest identycznością).  
Zatem <math>{\mathbf S}_n(\pi)</math> jest grupą cykliczną rzędu <math>n</math>,  
Zatem <math>{\mathbf S}_n(\pi)</math> jest grupą cykliczną rzędu <math>n</math>,  
czyli z Wniosku [[##wniosek - nie ma za duzo grup cyklicznych|Uzupelnic wniosek - nie ma za duzo grup cyklicznych|]]  
czyli z [[#wn_4.11|Wniosku 4.11]]  
mamy <math>{\mathbf S}_n(\pi)\approx \mathbb{Z}_n</math>.
mamy <math>{\mathbf S}_n(\pi)\approx \mathbb{Z}_n</math>.


Linia 472: Linia 474:
jeśli zaś <math>n</math> jest nieparzyste to osie symetrii przechodzą przez wierzchołek  
jeśli zaś <math>n</math> jest nieparzyste to osie symetrii przechodzą przez wierzchołek  
i środek przeciwległego do niego boku.
i środek przeciwległego do niego boku.
''Rysunek:'' 8.5 Szkic na kartce.


Permutacja odpowiadająca symetrii osiowej posiada poza cyklami wielkości <math>2</math>:
Permutacja odpowiadająca symetrii osiowej posiada poza cyklami wielkości <math>2</math>:
Linia 483: Linia 483:
Na przykład, gdy <math>n</math> jest parzyste oraz :
Na przykład, gdy <math>n</math> jest parzyste oraz :


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


<center><math>\sigma=(0,n-1)(1,n-2)(2,n-3)\ldots(n/2-1,n/2+1),
<center>
</math></center>
<math>\sigma=(0,n-1)(1,n-2)(2,n-3)\ldots(n/2-1,n/2+1)</math>,
</center>


* gdy <math>\sigma</math> jest symetrią względem osi przechodzącej przez wierzchołki
* gdy <math>\sigma</math> jest symetrią względem osi przechodzącej przez wierzchołki <math>0</math> i <math>(n+1)/2</math>,
<math>0</math> i <math>(n+1)/2</math>,
to  <math>\sigma</math> rozkłada się na cykle
to  <math>\sigma</math> rozkłada się na cykle


<center><math>\sigma=(0)(1,n-1)(2,n-2)\ldots(n/2-1,n/2+1)( (n+1)/2 ),
<center>
</math></center>
<math>\sigma=(0)(1,n-1)(2,n-2)\ldots(n/2-1,n/2+1)( (n+1)/2 )</math>,
</center>


a dla nieparzystego <math>n</math>:
a dla nieparzystego <math>n</math>:


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


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


Jakie elementy składają się na <math>{\mathbf S}_n({\left\{ {\pi,\sigma} \right\} })</math>?  
Jakie elementy składają się na <math>{\mathbf S}_n({\left\{ {\pi,\sigma} \right\} })</math>?  
Linia 512: Linia 511:
* <math>\pi^n=id</math>, <math>\pi^{-1}=\pi^{n-1}</math>.
* <math>\pi^n=id</math>, <math>\pi^{-1}=\pi^{n-1}</math>.


* <math>\sigma</math> jest inwolucją,  
* <math>\sigma</math> jest inwolucją, czyli jest sama do siebie odwrotna, <math>\sigma^{-1}=\sigma</math>.  
czyli jest sama do siebie odwrotna, <math>\sigma^{-1}=\sigma</math>.  


''Rysunek:'' 8.6 Szkic na kartce.
* <math>\pi\sigma\pi=\sigma</math> ([[SW 8.7.swf|Zobacz rysunek]])


* <math>\pi\sigma\pi=\sigma</math>
Pokażemy tę własność jedynie dla <math>n</math> nieparzystych
(dowód dla <math>n</math> parzystych znacząco się nie różni):


''Rysunek:'' 8.7 Szkic na kartce.


Pokażemy tę własność jedynie dla <math>n</math> nieparzystych
<center>
(dowód dla <math>n</math> parzystych znacząco się nie różni):
<math>\begin{align} \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),
\end{align}</math>
</center>


<center><math>\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</math></center>


dla <math>i\in{\left\{ {2,\ldots,n-1} \right\} }</math>.
dla <math>i\in{\left\{ {2,\ldots,n-1} \right\} }</math>.


Z Obserwacji [[##obserwacja - postac zbioru generowanego|Uzupelnic obserwacja - postac zbioru generowanego|]] i naszych spostrzeżeń mamy:
Z [[#obs_4.9|Obserwacji 4.9]] i naszych spostrzeżeń mamy:
 
 
<center>
<math>\begin{align} 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\} }
\end{align}</math>
</center>


<center><math>\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</math></center>


Zatem podgrupa generowana przez <math>{\left\{ {\pi,\sigma} \right\} }</math> ma co najwyżej <math>2n</math> elementów.
Zatem podgrupa generowana przez <math>{\left\{ {\pi,\sigma} \right\} }</math> ma co najwyżej <math>2n</math> elementów.
Jako ćwiczenie zostawiamy dowód, że w istocie wymienione elementy są parami różne.
Jako ćwiczenie zostawiamy dowód, że w istocie wymienione elementy są parami różne. Okazuje się, że
Okazuje się, że
 
<center><math>\begin{array} {ll}
 
\pi,\pi^2,\pi^3,\ldots,\pi^n&\textrm{-- to wszystkie obroty wraz z identycznością},\\
<center>
\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}.
<math>\begin{array} {ll}
\pi,\pi^2,\pi^3,\ldots,\pi^n&\text{- to wszystkie obroty wraz z identycznością},\\
\pi\sigma,\pi^2\sigma,\pi^3\sigma,\ldots,\pi^n\sigma&\text{- to symetrie wobec każdej z }\mathit{n} \text{osi symetrii} \mathit{n} \text{-kąta foremnego}.
\end{array}  
\end{array}  
</math></center>
</math>
</center>
 


'''Grupa dihedralna''' <math>{\mathbf D}_{n}</math> to podgrupa grupy <math>{\mathbf S_n}</math>  
'''Grupa dihedralna''' <math>{\mathbf D}_{n}</math> to podgrupa grupy <math>{\mathbf S_n}</math>  
Linia 556: Linia 562:
w której działanie <math>\cdot</math> zdefiniowane jest przez
w której działanie <math>\cdot</math> zdefiniowane jest przez


<center><math>(x,y)\cdot(z,w)=(x\cdot z,y\cdot w).
 
</math></center>
<center><math>(x,y)\cdot(z,w)=(x\cdot z,y\cdot w)</math></center>
 


Weryfikację, że tak określone działanie po współrzędnych spełnia wszystkie warunki
Weryfikację, że tak określone działanie po współrzędnych spełnia wszystkie warunki
Linia 565: Linia 572:
Rozważmy <math>\mathbb{Z}_2\times\mathbb{Z}_3</math>.
Rozważmy <math>\mathbb{Z}_2\times\mathbb{Z}_3</math>.


<center><math>\mathbb{Z}_2\times \mathbb{Z}_3={\left\{ {(0,0),(0,1),(0,2),(1,0),(1,1),(1,2)} \right\} }.
 
</math></center>
<center><math>\mathbb{Z}_2\times \mathbb{Z}_3={\left\{ {(0,0),(0,1),(0,2),(1,0),(1,1),(1,2)} \right\} }</math></center>
 


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


<center><math>f(a) = (a \mbox{ {\sf mod} } 2 , \ a \mbox{ {\sf mod} } 3 )
 
<center><math>f(a) = (a \mathsf{ mod} 2 , \ a \mathsf{ mod} 3 )
</math></center>
</math></center>


definiuje izomorfizm grup <math>\mathbb{Z}_6</math> i <math>\mathbb{Z}_2\times\mathbb{Z}_3</math>.  
definiuje izomorfizm grup <math>\mathbb{Z}_6</math> i <math>\mathbb{Z}_2\times\mathbb{Z}_3</math>.  
Linia 579: Linia 589:
<math>\mathbb{Z}_2\times\mathbb{Z}_4</math> i <math>\mathbb{Z}_8</math>.  
<math>\mathbb{Z}_2\times\mathbb{Z}_4</math> i <math>\mathbb{Z}_8</math>.  
Rzędy elementów w produkcie <math>\mathbb{Z}_2\times\mathbb{Z}_4</math> przedstawia tabela:
Rzędy elementów w produkcie <math>\mathbb{Z}_2\times\mathbb{Z}_4</math> przedstawia tabela:


<center><math>\begin{array} {|c||c|c|c|c|c|c|c|c|}
<center><math>\begin{array} {|c||c|c|c|c|c|c|c|c|}
Linia 584: Linia 595:
\mathbb{Z}_2\times\mathbb{Z}_4&(0,0)&(0,1)&(0,2)&(0,3)&(1,0)&(1,1)&(1,2)&(1,3)\\
\mathbb{Z}_2\times\mathbb{Z}_4&(0,0)&(0,1)&(0,2)&(0,3)&(1,0)&(1,1)&(1,2)&(1,3)\\
\hline
\hline
\textrm{rząd}&1&4&2&4&2&4&2&4\\
\text{rząd}&1&4&2&4&2&4&2&4\\
\hline
\hline
\end{array}  
\end{array}  
</math></center>
</math></center>


A zatem grupa <math>\mathbb{Z}_2\times\mathbb{Z}_4</math> nie ma elementu rzędu <math>8</math>, nie może więc być
A zatem grupa <math>\mathbb{Z}_2\times\mathbb{Z}_4</math> nie ma elementu rzędu <math>8</math>, nie może więc być
Linia 593: Linia 605:
}}
}}


{{obserwacja|||
{{obserwacja|4.12|obs 4.12|
Jeśli <math>m\perp n</math>, to <math>\mathbb{Z}_m\times\mathbb{Z}_n \approx \mathbb{Z}_{mn}</math>.
Jeśli <math>m\perp n</math>, to <math>\mathbb{Z}_m\times\mathbb{Z}_n \approx \mathbb{Z}_{mn}</math>.
}}
}}
Linia 605: Linia 617:
Licząc kolejno na obu osiach produktu dostajemy
Licząc kolejno na obu osiach produktu dostajemy


<center><math>\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}}.
<center><math>\begin{align} \underbrace{1+\ldots+1}_{r\ razy} \mathsf{ mod} m &=r \mathsf{ mod} m =0,\text{ czyli }\mathit{m|r},\\
\endaligned</math></center>
\underbrace{1+\ldots+1}_{r\ razy} \mathsf{ mod} n &=r \mathsf{ mod} n =0,\text{ czyli }\mathit{n|r}.
\end{align}</math></center>
 


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


<center><math>r=\mbox{\sf NWW}(m,n)=\frac{mn}{\mbox{\sf NWD}(m,n)}=\frac{mn}{1}=mn.
 
</math></center>
<center><math>r=\mathsf{ NWW}(m,n)=\frac{mn}{\mathsf{ NWD}(m,n)}=\frac{mn}{1}=mn</math></center>
 


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


Linia 636: Linia 651:
względem elementu <math>g\in G</math> to zbiór  
względem elementu <math>g\in G</math> to zbiór  


<center><math>gH={\left\{ {gh : h\in H} \right\} }.
 
</math></center>
<center><math>gH={\left\{ {gh : h\in H} \right\} }</math></center>
 


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


<center><math>Hg={\left\{ {hg : h\in H} \right\} }.
 
</math></center>
<center><math>Hg={\left\{ {hg : h\in H} \right\} }</math></center>
 


Skoncentrujemy się teraz na lewych warstwach.  
Skoncentrujemy się teraz na lewych warstwach.  
Linia 656: Linia 673:
Zauważmy, że elementy lewej warstwy  
Zauważmy, że elementy lewej warstwy  


<center><math>\sigma C_4={\left\{ {\sigma\pi,\sigma\pi^2,\sigma\pi^3,\sigma\pi^4} \right\} }.
 
</math></center>
<center><math>\sigma C_4={\left\{ {\sigma\pi,\sigma\pi^2,\sigma\pi^3,\sigma\pi^4} \right\} }</math></center>
 


wszystkie symetrie osiowe kwadratu.  
wszystkie symetrie osiowe kwadratu.  
Linia 667: Linia 685:
Nastepna obserwacja orzeka, że wszystkie warstwy lewo- i prawo-stronne są równoliczne.
Nastepna obserwacja orzeka, że wszystkie warstwy lewo- i prawo-stronne są równoliczne.


{{obserwacja|||
{{obserwacja|4.13|obs 4.13|
Jeśli <math>{\mathbf H}</math> jest skończoną podgrupą grupy <math>{\mathbf G}</math> i <math>g\in G</math>,  
Jeśli <math>{\mathbf H}</math> jest skończoną podgrupą grupy <math>{\mathbf G}</math> i <math>g\in G</math>,  
to <math>\left\vertgH\right\vert=\left\vertH\right\vert= \left\vertHg\right\vert</math>.
to <math>\left\vert gH\right\vert=\left\vert H \right\vert= \left\vert Hg \right\vert</math>.
}}
}}


Linia 677: Linia 695:
są parami różne i zbiór
są parami różne i zbiór


<center><math>gH={\left\{ {gh_0,gh_1,\cdots,gh_{m-1}} \right\} },
 
</math></center>
<center><math>gH={\left\{ {gh_0,gh_1,\cdots,gh_{m-1}} \right\} }</math>,</center>
 


ma dokładnie <math>m</math> elementów.
ma dokładnie <math>m</math> elementów.
}}
}}


{{obserwacja|||
{{obserwacja|4.14|obs 4.14|
Dla dowolnej podgrupy <math>{\mathbf H}</math>  
Dla dowolnej podgrupy <math>{\mathbf H}</math>  
grupy <math>{\mathbf G}</math> i <math>g_0,g_1\in G</math>  
grupy <math>{\mathbf G}</math> i <math>g_0,g_1\in G</math>  
Linia 698: Linia 717:
Wtedy
Wtedy


<center><math>y=g_0 h=g_1 h_1 h_0^{-1} h,
 
</math></center>
<center><math>y=g_0 h=g_1 h_1 h_0^{-1} h</math>,</center>
 


co wobec <math>h_1,h_0^{-1},h\in H</math> daje  
co wobec <math>h_1,h_0^{-1},h\in H</math> daje  
Linia 705: Linia 725:
}}
}}


{{twierdzenie|Lagrange'a||
{{twierdzenie|4.15[Lagrange'a]|tw 4.15|
 
Dla dowolnej podgrupy <math>{\mathbf H}</math> skończonej grupy <math>{\mathbf G}</math>,   
Dla dowolnej podgrupy <math>{\mathbf H}</math> skończonej grupy <math>{\mathbf G}</math>,   
rząd <math>{\mathbf H}</math> dzieli rząd <math>{\mathbf G}</math>.
rząd <math>{\mathbf H}</math> dzieli rząd <math>{\mathbf G}</math>.
Linia 718: Linia 737:
* każdy <math>g_i</math> jest we własnej warstwie <math>g_iH</math>, gdyż <math>g_i\cdot1\in g_iH</math>,
* każdy <math>g_i</math> jest we własnej warstwie <math>g_iH</math>, gdyż <math>g_i\cdot1\in g_iH</math>,


* <math>\left\vertg_iH\right\vert=\left\vertH\right\vert</math> dla dowolnego <math>i</math>,
* <math>\left\vert g_iH \right\vert=\left\vert H \right\vert</math> dla dowolnego <math>i</math>,


* lewe warstwy <math>g_iH</math>, <math>g_jH</math> są albo identyczne albo rozłączne,
* lewe warstwy <math>g_iH</math>, <math>g_jH</math> są albo identyczne albo rozłączne,
Linia 727: Linia 746:
}}
}}


{{wniosek|||
{{wniosek|4.16|wn 4.16|
Niech <math>{\mathbf G}=(G,\cdot,1)</math> będzie grupą rzędu <math>n</math>. Wtedy dla <math>g \in G</math> mamy:
Niech <math>{\mathbf G}=(G,\cdot,1)</math> będzie grupą rzędu <math>n</math>. Wtedy dla <math>g \in G</math> mamy:


Linia 744: Linia 763:
}}
}}


{{wniosek|||
{{wniosek|4.17|wn 4.17|
Każda grupa <math>{\mathbf G}</math> której rząd jest liczbą pierwszą <math>p</math>   
Każda grupa <math>{\mathbf G}</math> której rząd jest liczbą pierwszą <math>p</math>   
jest cykliczna i izomorficzna z <math>\mathbb{Z}_p</math>.
jest cykliczna i izomorficzna z <math>\mathbb{Z}_p</math>.
Linia 754: Linia 773:
To oznacza zaś, iż <math>g</math> generuje grupę <math>{\mathbf G}</math>,  
To oznacza zaś, iż <math>g</math> generuje grupę <math>{\mathbf G}</math>,  
czyli <math>{\mathbf G}</math> jest cykliczna.  
czyli <math>{\mathbf G}</math> jest cykliczna.  
Reszta wynika już z Wniosku [[##wniosek - nie ma za duzo grup cyklicznych|Uzupelnic wniosek - nie ma za duzo grup cyklicznych|]].
Reszta wynika już z [[#wn_4.11|Wniosku 4.11]].
}}
}}


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


#
1. <math>{\mathbf G}</math> jest grupa cykliczną,
<math>{\mathbf G}</math> jest grupa cykliczną,


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


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


}}
}}
Linia 775: Linia 791:
{{dowod|||
{{dowod|||
Dla dowodu implikacji  
Dla dowodu implikacji  
([[##obserwacja - ostatnia 1|Uzupelnic obserwacja - ostatnia 1|]] <math>\Rightarrow</math> [[##obserwacja - ostatnia 2|Uzupelnic obserwacja - ostatnia 2|]])  
(1 <math>\Rightarrow</math> 2)  
załóżmy że grupa <math>{\mathbf G}</math> jest cykliczna i generowana przez <math>g</math>.
załóżmy że grupa <math>{\mathbf G}</math> jest cykliczna i generowana przez <math>g</math>.
Niech <math>d</math> będzie dzielnikiem <math>n</math>, czyli <math>n=dq</math> dla pewnego <math>q</math>.  
Niech <math>d</math> będzie dzielnikiem <math>n</math>, czyli <math>n=dq</math> dla pewnego <math>q</math>.  
Elementy
Elementy


<center><math>1,g^q,g^{2q},\ldots,g^{(d-1)q}
<center><math>1,g^q,g^{2q},\ldots,g^{(d-1)q}
</math></center>
</math></center>


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


<center><math>(g^{iq})^d=(g^{dq})^i=1^i=1.
 
</math></center>
<center><math>(g^{iq})^d=(g^{dq})^i=1^i=1</math></center>
 


Zatem elementów <math>x\in G</math> spełniających <math>x^d=1</math> jest co najmniej <math>d</math>.  
Zatem elementów <math>x\in G</math> spełniających <math>x^d=1</math> jest co najmniej <math>d</math>.  
Załóżmy teraz, że pewien <math>y\in G</math> spełnia <math>y^d=1</math>.  
Załóżmy teraz, że pewien <math>y\in G</math> spełnia <math>y^d=1</math>.  
Ponieważ <math>g</math> generuje <math>{\mathbf G}</math>, mamy <math>y=g^k</math> dla pewnego <math>k</math>, skąd <math>g^{kd}=y^d=1</math>.
Ponieważ <math>g</math> generuje <math>{\mathbf G}</math>, mamy <math>y=g^k</math> dla pewnego <math>k</math>, skąd <math>g^{kd}=y^d=1</math>.
Z Wniosku [[##obserwacja - rzad elementu|Uzupelnic obserwacja - rzad elementu|]] mamy <math>n|kd</math>,  
Z [[#obs_4.5|Obserwacji 4.5]] mamy <math>n|kd</math>,  
czyli <math>kd=fn=fdq</math> i <math>k=fq</math> dla pewnego <math>f</math>.  
czyli <math>kd=fn=fdq</math> i <math>k=fq</math> dla pewnego <math>f</math>.  
Zatem <math>y=g^{k}=g^{fq}</math> znajduje się na naszej liście rozwiązań równania <math>x^d=1</math>.  
Zatem <math>y=g^{k}=g^{fq}</math> znajduje się na naszej liście rozwiązań równania <math>x^d=1</math>.  
Linia 798: Linia 817:


Dla dowodu implikacji  
Dla dowodu implikacji  
([[##obserwacja - ostatnia 2|Uzupelnic obserwacja - ostatnia 2|]] <math>\Rightarrow</math> [[##obserwacja - ostatnia 3|Uzupelnic obserwacja - ostatnia 3|]])
(2 <math>\Rightarrow</math> 3)
przypomnijmy, za Obserwacją [[##obserwacja - rzad elementu|Uzupelnic obserwacja - rzad elementu|]],  
przypomnijmy, za [[#obs_4.5|Obserwacją 4.5]],  
że element <math>x</math> rzędu <math>r</math> spełnia <math>x^d=1</math>  
że element <math>x</math> rzędu <math>r</math> spełnia <math>x^d=1</math>  
wtedy i tylko wtedy, gdy <math>r|d</math>.  
wtedy i tylko wtedy, gdy <math>r|d</math>.  
A zatem  założenie 2 daje
A zatem  założenie 2 daje


<center><math>d=\sum_{r|d}f(r),  
<center><math>d=\sum_{r|d}f(r),  
</math></center>
</math></center>


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


<center><math>f(d)=\sum_{r|d}\mu(r)\frac{d}{r}.
 
</math></center>
<center><math>f(d)=\sum_{r|d}\mu(r)\frac{d}{r}</math></center>
 


Wobec znanego nam już przedstawienia funkcji Eulera przez funkcje Mobiusa,  
Wobec znanego nam już przedstawienia funkcji Eulera przez funkcje Mobiusa,  
Linia 818: Linia 840:


Wreszcie, dla dowodu ostatniej implikacji  
Wreszcie, dla dowodu ostatniej implikacji  
([[##obserwacja - ostatnia 3|Uzupelnic obserwacja - ostatnia 3|]] <math>\Rightarrow</math> [[##obserwacja - ostatnia 1|Uzupelnic obserwacja - ostatnia 1|]])  
(3 <math>\Rightarrow</math> 1)  
zauważmy najpierw, że  zawsze <math>\varphi(n)\geq 1</math>.  
zauważmy najpierw, że  zawsze <math>\varphi(n)\geq 1</math>.  
To oczywiście daje, że istnieje co najmniej jeden element rzędu <math>n</math> w <math>{\mathbf G}</math>.  
To oczywiście daje, że istnieje co najmniej jeden element rzędu <math>n</math> w <math>{\mathbf G}</math>.  
Linia 826: Linia 848:
{{przyklad|||
{{przyklad|||
Zbadajmy rzędy elementów grupy cyklicznej <math>\mathbb{Z}_{12}</math>.
Zbadajmy rzędy elementów grupy cyklicznej <math>\mathbb{Z}_{12}</math>.


<center><math>\begin{array} {|c|c|c|c|c|c|c|c|c|c|c|c|}
<center><math>\begin{array} {|c|c|c|c|c|c|c|c|c|c|c|c|}
Linia 835: Linia 858:
\end{array}  
\end{array}  
</math></center>
</math></center>


* dzielniki liczby <math>12</math> to <math>1,2,3,4,6,12</math>.
* dzielniki liczby <math>12</math> to <math>1,2,3,4,6,12</math>.
Linia 842: Linia 866:
<center><math>\begin{array} {|c|c|c|c|c|c|c|}
<center><math>\begin{array} {|c|c|c|c|c|c|c|}
\hline
\hline
\textrm{dzielnik \textsl{d} liczby \textsl{12}}&1&2&3&4&6&12\\
\text{dzielnik } \mathit{d} \text{liczby } \mathit{12}&1&2&3&4&6&12\\
\hline
\hline
\textrm{liczba elementów rzędu \textsl{d}}&1&1&2&2&2&4\\
\text{liczba elementów rzędu }\mathit{d}&1&1&2&2&2&4\\
\hline
\hline
\end{array}  
\end{array}  
</math></center>
</math></center>


* <math>\varphi(1)=1</math>, <math>\varphi(2)=1</math>, <math>\varphi(3)=2</math>,  
* <math>\varphi(1)=1</math>, <math>\varphi(2)=1</math>, <math>\varphi(3)=2</math>, <math>\varphi(4)=2</math>, <math>\varphi(6)=2</math>, <math>\varphi(12)=4</math>.
<math>\varphi(4)=2</math>, <math>\varphi(6)=2</math>, <math>\varphi(12)=4</math>.


}}
}}

Aktualna wersja na dzień 21:43, 11 wrz 2023

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 𝐆=(G,*,,e), gdzie G jest dowolnym zbiorem niepustym, * działaniem dwuargumentowym, jest działaniem jednoargumentowym, a eG, przy czym, dla dowolnych x,y,zG, 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 𝐆.
  • x*x=x*x=e, czyli x jest elementem odwrotnym do x w 𝐆.

Rząd grupy skończonej 𝐆=(G,*,e) to liczba |G| 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ś x, jeśli istnieje to jest jedyny.

Przykład

=(,+,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 (łą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 n1, zbiór reszt modulo n wraz z dodawaniem modulo n, tzn. n=(n,+,0) jest grupą. Rzeczywiście:

  • suma dwu liczb modulo n wpada do zbioru n,
  • (a+b)+c=a+(b+c) dla dowolnych a,b,cn,
  • 0 jest elementem neutralnym, gdyż 0+a=a+0=a,
  • na jest elementem odwrotnym liczby a, gdyż a+(na)=(na)+a=nn0.

Przykład

𝐒n=(Sn,) jest grupą, gdzie Sn to zbiór permutacji zbioru n={0,,n1}, a to składanie permutacji. Rzeczywiście:

  • złożenie dwóch permutacji n jest permutacją n,
  • 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 𝐒n, gdyż ππ1=π1π=id.

Przykład

Gdy p*=p{0}={1,,p1} oraz p jest liczba pierwszą, to p*=(p*,,1) jest grupą, gdzie działanie to mnożenie modulo p. Rzeczywiście:

  • gdy a,bp*, to oczywiście (abmodp){0,,p1}. Gdyby jednak abmodp=0, to ab=qp dla pewnego q>0.

Liczba p byłaby więc rozkładzie ab=p1pk, co jest niemożliwe wobec pimax(a,b)<p.

  • dla dowolnych a,b,c zachodzi
(abmodp)cmodp=a(bcmodp)modp
  • 1 jest elementem neutralnym, gdyż 1a=a1=a,
  • Dowolny a{1,,p1}=p* ma element odwrotny w p*. Możemy go wskazać np. przy pomocy rozszerzonego algorytmu Euklidesa.

Z pierwszości p mamy NWD(a,p)=1 zatem istnieją x,y takie, że xa+yp=1, czyli xamodp=1. To oznacza, iż xmodp jest elementem odwrotnym do a w p*.

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

    • ap2, jeśli p>2,
    • a, jeśli p=2
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 ({i,p,l,x,y,z},,i) 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

{i,p,l,x,y,z}.

iplxyziiplxyzppliyzxllipzxyxxzyilpyyxzpilzzyxlpi
  • 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,zG 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.

Obserwacja 4.2

Jeśli (G,*,e) jest grupą i a,bG, 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 x0 i x1 są rozwiązaniami naszego równania. Wtedy mamy a*x0=a*x1 i z lewostronnego prawa skracania x0=x1.

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 aG. Element neutralny e jest jedynym rozwiązaniem równania e*x=e. Element odwrotny do a jest jedynym rozwiązaniem a*x=e.

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

  • xy oznacza x*y,
  • 1 to jedyny element neutralny grupy 𝐆. Rozważając więcej niż jedną grupę dla jednoznaczności piszemy czasem 1G.
  • x1 to jedyny element odwrotny do x w 𝐆.

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

Grupa abelowa to 𝐆=(G,,1), w której działanie jest przemienne tzn. dla dowolnych x,yG 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 n i p* są abelowe, gdyż tak dodawanie, jak i mnożenie modularne jest przemienne.

Grupa przekształceń trójkąta równobocznego ({i,p,l,x,y,z},,i) nie jest abelowa, gdyż np. xppx.

SW 8.3.svg

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


x0=1,xn+1=xnx,xn=(xn)1.


Obserwacja 4.4

Dla dowolnej grupy 𝐆=(G,,1), xG i m,n zachodzi


1m=1,xm+n=xmxn,xmn=(xm)n


Jeśli 𝐆 jest abelowa i x,yG, to


(xy)n=xnyn


Jeśli grupa 𝐆=(G,,1) ma rząd skończony, to oczywiście dla dowolnego xG w ciągu nieujemnych potęg: 1,x,x2,x3, elementy muszą zacząć się powtarzać. Załóżmy zatem, że m<n i xm=xn. Mnożąc te równość przez xm otrzymujemy 1=xnm. 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 xG w grupie 𝐆=(G,,1) o skończonym rzędzie to najmniejsza dodatnia liczba n taka, że xn=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,,1) mamy xn=1 wtedy i tylko wtedy, gdy m|n.

Dowód

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


xn=xqm=(xm)q=1q=1


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


1=xn=xqm+r=(xm)qxr=1qxr=xr,


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

Homomorfizm grup 𝐆0=(G0,,1G0), 𝐆1=(G1,,1G1) to dowolna funkcja f:G0G1 taka, że dla dowolnych x,yG0 zachodzi


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


Obserwacja 4.6

Dla dowolnego homomorfizmu f:G0G1 grup 𝐆0 i 𝐆1 mamy:

  • f(1G0)=1G1,
  • f(x1)=f(x)1, dla wszystkich xG0,

Dowód

Oczywiście f(1G0)=f(1G01G0)=f(1G0)f(1G0). Prawo skracania w grupie 𝐆1 daje więc 1G1=f(1G0). Z kolei, gdy xG0, to f(x)f(x1)=f(xx1)=f(1G0)=1G1, czyli f(x1) jest elementem odwrotnym do f(x) w 𝐆1.

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

Podgrupa grupy 𝐆=(G,,1G) to taka grupa 𝐇=(H,,1G), że HG oraz mnożenie w grupie 𝐇 jest restrykcją mnożenia w 𝐆.

Obserwacja 4.7

Dla HG, gdzie 𝐆=(G,,1) jest grupą, jeśli

  • xyH dla dowolnych xyH,
  • x1H dla dowolnych xH,

to 𝐇=(H,,1) 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 H. Łączność w H wynika bezpośrednio z łączności w G. Drugi punkt świadczy, iż każdy element w H ma element odwrotny także w H. Dla dowodu, że 1H skorzystamy z niepustości H i wybierzmy hH. Wtedy, z drugiego punktu, h1H, więc 1=hh1H na mocy punktu pierwszego.

Załóżmy teraz, że grupa 𝐆 ma rząd skończony oraz podzbiór HG jest zamknięty na mnożenie. Wtedy oczywiście wszystkie potęgi o nieujemnych wykładnikach h,h2,h3, wpadają do H. Ponieważ G ma rząd skończony, to rząd dowolnego elementu też jest skończony, czyli istnieje m takie, że hm=1. Zatem 1H i hm1h=1=hhm1, czyli hm1H jest elementem odwrotnym do h.

Z Obserwacji 4.7 dostajemy natychmiast:

Wniosek 4.8

Przecięcie dowolnej rodziny podgrup grupy 𝐆 jest podgrupą 𝐆.

Grupy cykliczne

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

Obserwacja 4.9

Dla dowolnej grupy 𝐆=(G,,1) i XG


G(X)={x0xn1:n i (xiX lub xi1X)}


Dowód

Oczywiście wszystkie iloczyny postaci x0xn1 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 (x0xn1)1=xn11xn21x01. A zatem Obserwacja 4.7 gwarantuje, że (Z,,1) jest podgrupą. Musi zatem być czynnikiem przecięcia wyznaczającego G(X), czyli G(X)Z.

Grupa cykliczna to grupa generowana zbiorem jednoelementowym.

Jeśli 𝐆=𝐆({x}), to G={xn:n}. Gdy ponadto 𝐆 jest skończona, to jej rząd pokrywa się z rzędem elementu generującego x, czyli G={1,x,x2,,x|G|1}.

Przykład

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


={,3,2,1,0,1,2,3,}={,111,11,1,11,1,1+1,1+1+1,}


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

Przykład

Dla n>0 grupa n=(n,+,0) jest skończoną grupą cykliczną generowaną przez {1}. Rzeczywiście:


n={1,1+1,,1+1++1n razy}


Obserwacja 4.10

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

Dowód

Niech gi będzie generatorem grupy cyklicznej 𝐆i, dla i=0,1. Łatwo sprawdzić, że równość rzędów tych grup daje, iż g0k=g0l wtedy i tylko wtedy, gdy g1k=g1l. A zatem f:G0g0kg1kG1 ustala izomorfizm grup 𝐆0 i 𝐆1.

Wniosek 4.11

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

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

Przykład

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

Rząd cyklu n-elementowego jest oczywiście równy n. Kolejne złożenia π,π2,π3,,πn odpowiadają kolejnym obrotom πk w prawo naszego wielokąta o 360ok, aż πn przekręca go do pozycji wyjściowej (czyli jest identycznością). Zatem 𝐒n(π) jest grupą cykliczną rzędu n, czyli z Wniosku 4.11 mamy 𝐒n(π)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 :

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

σ=(0,n1)(1,n2)(2,n3)(n/21,n/2+1),

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

to σ rozkłada się na cykle

σ=(0)(1,n1)(2,n2)(n/21,n/2+1)((n+1)/2),

a dla nieparzystego n:

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

σ=(0)(1,n1)(2,n2)(3,n3)((n1)/2,(n+1)/2)

Jakie elementy składają się na 𝐒n({π,σ})? Jaka jest ich interpretacja geometryczna?

Zbierzmy kilka prostych faktów:

  • πn=id, π1=πn1.
  • σ jest inwolucją, czyli jest sama do siebie odwrotna, σ1=σ.

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


πσπ(0)=πσ(n1)=π(1)=0=σ(0),πσπ(1)=πσ(0)=π(0)=n1=σ(1),πσπ(i)=πσ(i1)=π(ni+1)=ni=σ(i),


dla i{2,,n1}.

Z Obserwacji 4.9 i naszych spostrzeżeń mamy:


Sn({π,σ})={x0xm1:m>0,xi{π,π1,σ,σ1}}={πk,πkσ:0<kn}


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


π,π2,π3,,πn- to wszystkie obroty wraz z identycznością,πσ,π2σ,π3σ,,πnσ- to symetrie wobec każdej z nosi symetriin-kąta foremnego.


Grupa dihedralna 𝐃n to podgrupa grupy 𝐒n (dla n3) generowana przez {π,σ}.

Produkt grup 𝐆0=(G0,,1G0) i 𝐆1=(G1,,1G1) to grupa 𝐆0×𝐆1=(G0×G1,,(1G0,1G1)), w której działanie zdefiniowane jest przez


(x,y)(z,w)=(xz,yw)


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 2×3.


2×3={(0,0),(0,1),(0,2),(1,0),(1,1),(1,2)}


Zauważmy, że f:62×3 zadana przez


f(a)=(amod2, amod3)


definiuje izomorfizm grup 6 i 2×3.

Czy zawsze mnm×n? Zbadajmy jeszcze jeden przykład: 2×4 i 8. Rzędy elementów w produkcie 2×4 przedstawia tabela:


2×4(0,0)(0,1)(0,2)(0,3)(1,0)(1,1)(1,2)(1,3)rząd14242424


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

Obserwacja 4.12

Jeśli mn, to m×nmn.

Dowód

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

Niech więc r będzie rzędem (1,1) w grupie m×n. Licząc kolejno na obu osiach produktu dostajemy


1++1r razymodm=rmodm=0, czyli m|r,1++1r razymodn=rmodn=0, czyli n|r.


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


r=NWW(m,n)=mnNWD(m,n)=mn1=mn


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 𝐀4 będzie podgrupą grupy 𝐒4 składającą się z tych permutacji, które są złożeniami parzystej liczby transpozycji. Wtedy |A4|=12, ale grupa 𝐀4 nie ma podgrup rzędu 4.

Lewa warstwa gH podgrupy 𝐇 grupy 𝐆 względem elementu gG to zbiór


gH={gh:hH}


Prawa warstwa Hg podgrupy 𝐇 grupy 𝐆 względem elementu gG to zbiór


Hg={hg:hH}


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

Przykład

Niech 𝐃4=({π,,π4,πσ,,π4σ},) będzie grupa dihedralną symetrii kwadratu. Posiada ona podgrupę cykliczną 𝐂4=({π,π2,π3,π4},). Niech σ będzie symetrią osiową. Zauważmy, że elementy lewej warstwy


σC4={σπ,σπ2,σπ3,σπ4}


wszystkie symetrie osiowe kwadratu. Jako ćwiczenie pozostawiamy wyznaczenie warstw πC4, π2C4 oraz σπ2C4.

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 𝐇 jest skończoną podgrupą grupy 𝐆 i gG, to |gH|=|H|=|Hg|.

Dowód

Niech H={h0,,hm1} i załóżmy, że ghi=ghj. Wtedy z prawa skracania mamy hi=hj. Zatem elementy gh0,gh1,,ghm1 są parami różne i zbiór


gH={gh0,gh1,,ghm1},


ma dokładnie m elementów.

Obserwacja 4.14

Dla dowolnej podgrupy 𝐇 grupy 𝐆 i g0,g1G lewe warstwy g0H, g1H są albo identyczne albo rozłączne.

Dowód

Pokażemy, że jeśli g0H i g1H mają jakiś wspólny element to są one identyczne. Załóżmy zatem, że xg0Hg1H, czyli g0h0=x=g1h1 dla pewnych h0,h1H. Wtedy g0=g1h1h01g1H. Dla dowodu inkluzji g0Hg1H, niech yg0H, czyli y=g0h dla pewnego hH. Wtedy


y=g0h=g1h1h01h,


co wobec h1,h01,hH daje yg1H.

Twierdzenie 4.15[Lagrange'a]

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

Dowód

Niech 𝐇=({h0,,hm1},,1) oraz 𝐆=({g0,,gn1},,1). Ponieważ:

  • każdy gi jest we własnej warstwie giH, gdyż gi1giH,
  • |giH|=|H| dla dowolnego i,
  • lewe warstwy giH, gjH są albo identyczne albo rozłączne,

to lewe warstwy g0H,g1H,,gn1H tworzą podział zbioru G={g0,g1,gn1} na równoliczne bloki wielkości m, skąd natychmiast m|n.

Wniosek 4.16

Niech 𝐆=(G,,1) będzie grupą rzędu n. Wtedy dla gG mamy:

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

Dowód

Niech r będzie rzędem elementu gG. Wtedy r jest rzędem podgrupy cyklicznej 𝐆(g)=({g,g2,,gr},,1). Z Twierdzenia Lagrange'a r, czyli rząd tej podgrupy cyklicznej, dzieli n. Skoro teraz n=kr to oczywiście xn=xkr=(xr)k=1k=1

Wniosek 4.17

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

Dowód

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

Obserwacja 4.18

Dla dowolnej grupy 𝐆=(G,,1) rzędu n2 następujące warunki są równoważne:

1. 𝐆 jest grupa cykliczną,

2. dla każdego d|n, grupa 𝐆 ma dokładnie d elementów xG takich, że xd=1,

3. dla każdego d|n, grupa 𝐆 ma dokładnie φ(d) elementów rzędu d.

Dowód

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


1,gq,g2q,,g(d1)q


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


(giq)d=(gdq)i=1i=1


Zatem elementów xG spełniających xd=1 jest co najmniej d. Załóżmy teraz, że pewien yG spełnia yd=1. Ponieważ g generuje 𝐆, mamy y=gk dla pewnego k, skąd gkd=yd=1. Z Obserwacji 4.5 mamy n|kd, czyli kd=fn=fdq i k=fq dla pewnego f. Zatem y=gk=gfq znajduje się na naszej liście rozwiązań równania xd=1. To dowodzi, że elementów xG spełniających xd=1 jest dokładnie d.

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


d=r|df(r),


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


f(d)=r|dμ(r)dr


Wobec znanego nam już przedstawienia funkcji Eulera przez funkcje Mobiusa, tzn. φ(d)=r|dμ(r)df, mamy f(d)=φ(d).

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

Przykład

Zbadajmy rzędy elementów grupy cyklicznej 12.


012345678910111126431221234612


  • dzielniki liczby 12 to 1,2,3,4,6,12.
  • liczba elementów rzędu d dla kolejnych dzielników d|12
dzielnik dliczby 121234612liczba elementów rzędu d112224
  • φ(1)=1, φ(2)=1, φ(3)=2, φ(4)=2, φ(6)=2, φ(12)=4.