Matematyka dyskretna 2/Wykład 4: Elementy teorii grup: Różnice pomiędzy wersjami
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, | ||
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\ | '''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 \ | * 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 \ | |||
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 \ | <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>\ | |||
że <math>xa+yp=1</math>, czyli <math>xa \ | |||
To oznacza, iż <math>x \ | |||
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 | ||
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: | ||
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>. | ||
}} | |||
<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> | ||
{{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 | ||
{{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 | 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{ | 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 | 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\ | 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>. | ||
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 | 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. | ||
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>. | |||
* <math>\pi\sigma\pi=\sigma</math> ([[SW 8.7.swf|Zobacz rysunek]]) | |||
Pokażemy tę własność jedynie dla <math>n</math> nieparzystych | |||
(dowód dla <math>n</math> parzystych znacząco się nie różni): | |||
<center> | |||
( | <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> | |||
dla <math>i\in{\left\{ {2,\ldots,n-1} \right\} }</math>. | dla <math>i\in{\left\{ {2,\ldots,n-1} \right\} }</math>. | ||
Z | 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> | |||
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&\ | <center> | ||
\pi\sigma,\pi^2\sigma,\pi^3\sigma,\ldots,\pi^n\sigma&\ | <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 \ | |||
<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 | ||
\ | \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>\ | |||
\underbrace{1+\ldots+1}_{r\ razy} \ | <center><math>\begin{align} \underbrace{1+\ldots+1}_{r\ razy} \mathsf{ mod} m &=r \mathsf{ mod} m =0,\text{ czyli }\mathit{m|r},\\ | ||
\ | \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=\ | |||
</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\ | 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\ | 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\ | * <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 | 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 | ||
( | (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 | 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 | ||
( | (2 <math>\Rightarrow</math> 3) | ||
przypomnijmy, za | 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 | ||
( | (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 | ||
\ | \text{dzielnik } \mathit{d} \text{liczby } \mathit{12}&1&2&3&4&6&12\\ | ||
\hline | \hline | ||
\ | \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 , 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.
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

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 .

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 .

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 .

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. .

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 .

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 .

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 .

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 .

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 .

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



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

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.

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
.

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 .

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

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.

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.

Przykład
Zbadajmy rzędy elementów grupy cyklicznej .
- dzielniki liczby to .
- liczba elementów rzędu dla kolejnych dzielników
- , , , , , .