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

Teoria grup

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

Grupa to uporządkowana czwórka ${\mathbf {G} }=(G,*,',e)$ , gdzie $G$ jest dowolnym zbiorem niepustym, $*$ działaniem dwuargumentowym, $'$ jest działaniem jednoargumentowym, a $e\in G$ , przy czym, dla dowolnych $x,y,z\in G$ , spełnione sa następujące warunki:

(łączność) $(x*y)*z=x*(y*z)$ ,

$e*x=x*e=x$ , czyli $e$ to element neutralny grupy ${\mathbf {G} }$ .

$x*x'=x'*x=e$ , czyli $x'$ jest elementem odwrotnym do $x$ w ${\mathbf {G} }$ .

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

Uwaga

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

Przykład

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

suma dwu liczb całkowitych zawsze jest liczbą całkowitą,

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

$0$ jest elementem neutralnym, gdyż $0+a=a+0=a$ ,

$-a$ jest elementem odwrotnym liczby $a$ , gdyż $a+(-a)=(-a)+a=0$ .

Przykład

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

suma dwu liczb modulo $n$ wpada do zbioru $\mathbb {Z} _{n}$ ,

$(a+b)+c=a+(b+c)$ dla dowolnych $a,b,c\in \mathbb {Z} _{n}$ ,

$0$ jest elementem neutralnym, gdyż Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle 0+a=a+0=a} ,

Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle n-a} jest elementem odwrotnym liczby Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle a} , gdyż Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle a+(n-a)=(n-a)+a=n\equiv_n 0} .

Przykład

Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle {\mathbf S}_n=(S_n,\circ)} jest grupą, gdzie Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle S_n} to zbiór permutacji zbioru Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \mathbb{Z}_n={\left\{ {0,\ldots,n-1} \right\} }} , a Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \circ} to składanie permutacji. Rzeczywiście:

złożenie dwóch permutacji Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \mathbb{Z}_n} jest permutacją Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \mathbb{Z}_n} ,

składanie funkcji, więc i permutacji, jest łączne,

identyczność jest elementem neutralnym przy składaniu funkcji,

permutacja odwrotna do Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \pi} jest elementem odwrotnym do Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \pi} w Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle {\mathbf S}_n} , gdyż Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \pi\cdot\pi^{-1}=\pi^{-1}\cdot\pi=id} .

Przykład

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

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

Liczba $p$ byłaby więc rozkładzie $ab=p_{1}\cdot \ldots \cdot p_{k}$ , co jest niemożliwe wobec $p_{i}\leqslant \max(a,b)<p$ .

dla dowolnych $a,b,c$ zachodzi

(ab{\mathsf {mod}}p)\cdot c{\mathsf {mod}}p=a\cdot (bc{\mathsf {mod}}p){\mathsf {mod}}p

$1$ jest elementem neutralnym, gdyż $1\cdot a=a\cdot 1=a$ ,

Dowolny $a\in {\left\{{1,\ldots ,p-1}\right\}}=\mathbb {Z} _{p}^{*}$ ma element odwrotny w ${\mathbf {\mathbb {Z} } _{p}^{*}}$ . Możemy go wskazać np. przy pomocy rozszerzonego algorytmu Euklidesa.

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

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

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

- $a$ , jeśli $p=2$

SW 8.1.swf

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 $({\left\{{i,p,l,x,y,z}\right\}},\circ ,i)$ jest grupą, gdzie $\circ$ jest składaniem przekształceń.

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

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

{\begin{array}{|c|cccccc|}\hline \circ &i&p&l&x&y&z\\\hline i&i&p&l&x&y&z\\p&p&l&i&y&z&x\\l&l&i&p&z&x&y\\x&x&z&y&i&l&p\\y&y&x&z&p&i&l\\z&z&y&x&l&p&i\\\hline \end{array}}

Jak zawsze $i$ , będąc identycznością, jest elementem neutralnym dla składania.

Każde z rozważanych przekształceń ma odwrotne do siebie. Odwrotnym przekształceniem do rotacji w prawo $p$ jest oczywiście rotacja w lewo $l$ . Symetrie względem kolejnych osi są same do siebie odwrotne.

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

Obserwacja 4.1 [prawo skracania]

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

(lewostronne) jeśli $x*y=x*z$ , to $y=z$ ,

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

Dowód

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

Obserwacja 4.2

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

a*x=b

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

Dowód

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

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

Dla dowodu jednoznaczności załóżmy, że $x_{0}$ i $x_{1}$ są rozwiązaniami naszego równania. Wtedy mamy $a*x_{0}=a*x_{1}$ i z lewostronnego prawa skracania $x_{0}=x_{1}$ .

Wniosek 4.3

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

Dowód

Niech $(G,*,e)$ będzie grupą i $a\in G$ . Element neutralny $e$ jest jedynym rozwiązaniem równania $e*x=e$ . Element odwrotny do $a$ jest jedynym rozwiązaniem $a*x=e$ .

W dalszych rozważaniach o abstrakcyjnych grupach porzucimy ornamentyczny symbol $*$ i będziemy się posługiwać notacją multiplikatywną. Zatem dla dowolnego $x,y\in G$ , gdzie ${\mathbf {G} }$ jest grupą

$xy$ oznacza $x*y$ ,

$1$ to jedyny element neutralny grupy ${\mathbf {G} }$ . Rozważając więcej niż jedną grupę dla jednoznaczności piszemy czasem $1_{G}$ .

$x^{-1}$ to jedyny element odwrotny do $x$ w ${\mathbf {G} }$ .

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

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

xy=yx

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

Przykład

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

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

SW 8.3.svg

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

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

Obserwacja 4.4

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

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

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

(xy)^{n}=x^{n}y^{n}

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

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

Obserwacja 4.5

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

Dowód

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

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

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

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

,

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

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

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

Obserwacja 4.6

Dla dowolnego homomorfizmu $f:G_{0}\rightarrow G_{1}$ grup ${\mathbf {G} _{0}}$ i ${\mathbf {G} _{1}}$ mamy:

$f(1_{G_{0}})=1_{G_{1}}$ ,

$f(x^{-1})=f(x)^{-1}$ , dla wszystkich $x\in G_{0}$ ,

Dowód

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

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

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

Obserwacja 4.7

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

$xy\in H$ dla dowolnych $xy\in H$ ,

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

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

Dowód

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

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

Z Obserwacji 4.7 dostajemy natychmiast:

Wniosek 4.8

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

Grupy cykliczne

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

Obserwacja 4.9

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

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

Dowód

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

Grupa cykliczna to grupa generowana zbiorem jednoelementowym.

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

Przykład

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

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

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

Przykład

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

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

Obserwacja 4.10

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

Dowód

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

Wniosek 4.11

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

SW 8.4.swf

SW 8.5.swf

SW 8.6.swf

Przykład

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

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

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

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

jeden cykl jednoelementowy, gdy $n$ jest nieparzyste,

dwa cykle jednoelementowe, gdy $n$ jest parzyste.

Na przykład, gdy $n$ jest parzyste oraz :

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

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

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

to $\sigma$ rozkłada się na cykle

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

a dla nieparzystego $n$ :

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

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

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

Zbierzmy kilka prostych faktów:

$\pi ^{n}=id$ , $\pi ^{-1}=\pi ^{n-1}$ .

$\sigma$ jest inwolucją, czyli jest sama do siebie odwrotna, $\sigma ^{-1}=\sigma$ .

$\pi \sigma \pi =\sigma$ (Zobacz rysunek)

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

${\begin{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),\end{aligned}}$

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

Z Obserwacji 4.9 i naszych spostrzeżeń mamy:

${\begin{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\}}\end{aligned}}$

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

${\begin{array}{ll}\pi ,\pi ^{2},\pi ^{3},\ldots ,\pi ^{n}&{\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}}$

Grupa dihedralna ${\mathbf {D} }_{n}$ to podgrupa grupy ${\mathbf {S} _{n}}$ (dla $n\geqslant 3$ ) generowana przez ${\left\{{\pi ,\sigma }\right\}}$ .

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

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

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

Przykład

Rozważmy $\mathbb {Z} _{2}\times \mathbb {Z} _{3}$ .

\mathbb {Z} _{2}\times \mathbb {Z} _{3}={\left\{{(0,0),(0,1),(0,2),(1,0),(1,1),(1,2)}\right\}}

Zauważmy, że $f:\mathbb {Z} _{6}\rightarrow \mathbb {Z} _{2}\times \mathbb {Z} _{3}$ zadana przez

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

definiuje izomorfizm grup $\mathbb {Z} _{6}$ i $\mathbb {Z} _{2}\times \mathbb {Z} _{3}$ .

Czy zawsze $\mathbb {Z} _{mn}\approx \mathbb {Z} _{m}\times \mathbb {Z} _{n}$ ? Zbadajmy jeszcze jeden przykład: $\mathbb {Z} _{2}\times \mathbb {Z} _{4}$ i $\mathbb {Z} _{8}$ . Rzędy elementów w produkcie $\mathbb {Z} _{2}\times \mathbb {Z} _{4}$ przedstawia tabela:

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

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

Obserwacja 4.12

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

Dowód

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

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

{\begin{aligned}\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{aligned}}

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

r={\mathsf {NWW}}(m,n)={\frac {mn}{{\mathsf {NWD}}(m,n)}}={\frac {mn}{1}}=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 ${\mathbf {H} }$ jest podgrupą skończonej grupy ${\mathbf {G} }$ , to rząd ${\mathbf {H} }$ dzieli rząd ${\mathbf {G} }$ . Zwracamy jednak uwagę, iż to nie oznacza, że grupa ${\mathbf {G} }$ ma podgrupy o rzędzie będącym jakimkolwiek dzielnikiem rzędu grupy ${\mathbf {G} }$ .

Przykład

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

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

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

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

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

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

Przykład

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

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

wszystkie symetrie osiowe kwadratu. Jako ćwiczenie pozostawiamy wyznaczenie warstw $\pi C_{4}$ , $\pi ^{2}C_{4}$ oraz $\sigma \pi ^{2}C_{4}$ .

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

Obserwacja 4.13

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

Dowód

Niech $H={\left\{{h_{0},\ldots ,h_{m-1}}\right\}}$ i załóżmy, że $gh_{i}=gh_{j}$ . Wtedy z prawa skracania mamy $h_{i}=h_{j}$ . Zatem elementy $gh_{0},gh_{1},\cdots ,gh_{m-1}$ są parami różne i zbiór

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

,

ma dokładnie $m$ elementów.

Obserwacja 4.14

Dla dowolnej podgrupy ${\mathbf {H} }$ grupy ${\mathbf {G} }$ i $g_{0},g_{1}\in G$ lewe warstwy $g_{0}H$ , $g_{1}H$ są albo identyczne albo rozłączne.

Dowód

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

y=g_{0}h=g_{1}h_{1}h_{0}^{-1}h

,

co wobec $h_{1},h_{0}^{-1},h\in H$ daje $y\in g_{1}H$ .

Twierdzenie 4.15[Lagrange'a]

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

Dowód

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

każdy $g_{i}$ jest we własnej warstwie $g_{i}H$ , gdyż $g_{i}\cdot 1\in g_{i}H$ ,

$\left\vert g_{i}H\right\vert =\left\vert H\right\vert$ dla dowolnego $i$ ,

lewe warstwy $g_{i}H$ , $g_{j}H$ są albo identyczne albo rozłączne,

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

Wniosek 4.16

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

rząd elementu $g$ dzieli $n$ ,

$g^{n}=1$ .

Dowód

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

Wniosek 4.17

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

Dowód

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

Obserwacja 4.18

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

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

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

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

Dowód

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

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

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

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

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

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

d=\sum _{r|d}f(r),

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

f(d)=\sum _{r|d}\mu (r){\frac {d}{r}}

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

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