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, który powiązał teorię grup z teorią ciał.

Grupa to uporządkowana czwórka $\mathbf{𝐆}=(G,*{,}^{\prime },e)$, gdzie $G$ jest dowolnym zbiorem niepustym, $*$ działaniem dwuargumentowym, ${\displaystyle }$ 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{𝐆}$.

• $x*x^{\prime }=x^{\prime }*x=e$, czyli $x^{\prime }$ jest elementem odwrotnym do $x$ w $\mathbf{𝐆}$.

Rząd grupy skończonej $\mathbf{𝐆}=(G,*,e)$ to liczba Parser nie mógł rozpoznać (błąd składni): {\displaystyle \left\vertG\right\vert} jej elementów. Gdy grupa $\mathbf{𝐆}$ 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

$\mathbb{\mathbb{Z}}=(\mathbb{\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{\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\ge 1$, zbiór reszt modulo $n$ wraz z dodawaniem modulo $n$, tzn. ${\mathbb{\mathbb{Z}}}_n=({\mathbb{\mathbb{Z}}}_n,+,0)$ jest grupą. Rzeczywiście:

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

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

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

• $n-a$ jest elementem odwrotnym liczby $a$, gdyż $a+(n-a)=(n-a)+a=n{\equiv }_{n}0$.

Przykład

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

• złożenie dwóch permutacji ${\mathbb{\mathbb{Z}}}_n$ jest permutacją ${\mathbb{\mathbb{Z}}}_n$,

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

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

• permutacja odwrotna do $\pi$ jest elementem odwrotnym do $\pi$ w ${\mathbf{𝐒}}_n$,

gdyż $\pi \cdot {\pi }^{-1}={\pi }^{-1}\cdot \pi =id$.

Przykład

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

• gdy $a,b\in {\mathbb{\mathbb{Z}}}_p^{*}$, to oczywiście Parser nie mógł rozpoznać (błąd składni): {\displaystyle (ab \mbox{ {\sf mod} } p )\in{\left\{ {0,\ldots,p-1} \right\} }} .

Gdyby jednak Parser nie mógł rozpoznać (błąd składni): {\displaystyle ab \mbox{ {\sf mod} } p =0} , to $ab=qp$ dla pewnego $q>0$. Liczba $p$ byłaby więc rozkładzie $ab=p_1\cdot \dots \cdot p_k$, co jest niemożliwe wobec $p_i⩽\max (a,b)<p$.

• dla dowolnych $a,b,c$ zachodzi

Parser nie mógł rozpoznać (błąd składni): {\displaystyle (ab \mbox{ {\sf mod} } p )\cdot c \mbox{ {\sf mod} } p =a\cdot(bc \mbox{ {\sf mod} } p ) \mbox{ {\sf mod} } p . }

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

• Dowolny $a\in \left\{1,\dots ,p-1\right\}={\mathbb{\mathbb{Z}}}_p^{*}$ ma element odwrotny w

${\mathbb{\mathbb{Z}}}_p^{*}$. Możemy go wskazać np. przy pomocy rozszerzonego algorytmu Euklidesa. Z pierwszości $p$ mamy Parser nie mógł rozpoznać (błąd składni): {\displaystyle \mbox{\sf NWD}(a,p)=1} zatem istnieją $x,y$ takie, że $xa+yp=1$, czyli Parser nie mógł rozpoznać (błąd składni): {\displaystyle xa \mbox{ {\sf mod} } p =1} . To oznacza, iż Parser nie mógł rozpoznać (błąd składni): {\displaystyle x \mbox{ {\sf mod} } p } jest elementem odwrotnym do $a$ w ${\mathbb{\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$

Przykład

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:

Rysunek: 8.2 Szkic na kartce.

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}{ccccccc}\circ & i& p& l& x& y& z\\ 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\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 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^{\prime }$ będzie elementem odwrotnym do $x$. Wtedy $y=1*y=(x^{\prime }*x)*y=x^{\prime }*(x*y)=x^{\prime }*(x*z)=(x^{\prime }*x)*z=1*z=z$.

Obserwacja

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^{\prime }$ będzie elementem odwrotnym do $a$ w $(G,*)$. Wtedy $x=a^{\prime }*b$ jest rozwiązaniem równania, gdyż

$a*(a^{\prime }*b)=(a*a^{\prime })*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

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{𝐆}$ jest grupą

• $xy$ oznacza $x*y$,

• $1$ to jedyny element neutralny grupy $\mathbf{𝐆}$.

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{𝐆}$.

Pamietajmy, że symbol $1$ w większości wypadków nie oznacza dobrze znanej liczby $1\in \mathbb{\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{𝐒}}_n$ dla $n>2$).

Grupa abelowa to $\mathbf{𝐆}=(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 ${\mathbb{\mathbb{Z}}}_n$ i ${\mathbb{\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\ne px$.

Rysunek: 8.3 Szkic na kartce

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

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \aligned x^0&=&1,\\ x^{n+1}&=&x^n\cdot x,\\ x^{-n}&=&(x^n)^{-1}. \endaligned}

Obserwacja

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

$1^m=1,x^{m+n}=x^m{x}^n,x^{mn}=(x^m{)}^n.$

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

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

Jeśli grupa $\mathbf{𝐆}=(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,\dots$ 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,\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

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\le 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{𝐆}}_0=(G_0,\cdot ,1_{G_0})$, ${\mathbf{𝐆}}_1=(G_1,\cdot ,1_{G_1})$ to dowolna funkcja $f:G_0\to G_1$ taka, że dla dowolnych $x,y\in G_0$ zachodzi

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

Obserwacja

Dla dowolnego homomorfizmu $f:G_0\to G_1$ grup ${\mathbf{𝐆}}_0$ i ${\mathbf{𝐆}}_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{𝐆}}_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(x{x}^{-1})=f(1_{G_0})=1_{G_1}$, czyli $f(x^{-1})$ jest elementem odwrotnym do $f(x)$ w ${\mathbf{𝐆}}_1$.

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

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

Obserwacja

Dla $\mathrm{\varnothing }\ne H\subseteq G$, gdzie $\mathbf{𝐆}=(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,\cdot ,1)$ jest podgrupą $\mathbf{𝐆}$. Ponadto jeśli $\mathbf{𝐆}$ ma rząd skończony, to już pierwszy punkt implikuje, iż $\mathbf{𝐇}$ jest podgrupą grupy $\mathbf{𝐆}$.

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=h{h}^{-1}\in H$ na mocy punktu pierwszego.

Załóżmy teraz, że grupa $\mathbf{𝐆}$ 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,\dots$ 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=h{h}^{m-1}$, czyli $h^{m-1}\in H$ jest elementem odwrotnym do $h$.

Z Obserwacji Uzupelnic obserwacja - warunki wystarczajace na podgrupe| dostajemy natychmiast:

Wniosek

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

Grupy cykliczne

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

Obserwacja

Dla dowolnej grupy $\mathbf{𝐆}=(G,\cdot ,1)$ i $\mathrm{\varnothing }\ne X\subseteq G$

Parser nie mógł rozpoznać (błąd składni): {\displaystyle G(X)={\left\{ {x_0\cdot\ldots\cdot x_{n-1} : n\in\mathbb{N} \mbox{ \rm i } (x_i\in X \mbox{ \rm lub }x_i^{-1}\in X)} \right\} }. }

Dowód

Oczywiście wszystkie iloczyny postaci $x_0\cdot \dots \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 \dots \cdot x_{n-1}{)}^{-1}=x_{n-1}^{-1}\cdot x_{n-2}^{-1}\cdot \dots \cdot x_0^{-1}$. A zatem Obserwacja Uzupelnic obserwacja - warunki wystarczajace na podgrupe| 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{𝐆}=\mathbf{𝐆}(\left\{x\right\})$, to $G=\left\{x^n:n\in \mathbb{\mathbb{Z}}\right\}$. Gdy ponadto $\mathbf{𝐆}$ jest skończona, to jej rząd pokrywa się z rzędem elementu generującego $x$, czyli Parser nie mógł rozpoznać (błąd składni): {\displaystyle G={\left\{ {1,x,x^2,\ldots, x^{\left\vertG\right\vert-1}} \right\} }} .

Przykład

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

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

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

Przykład

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

${\mathbb{\mathbb{Z}}}_n=\left\{1,1+1,\dots ,\underset{nrazy}{\underbrace{1+1+\dots +1}}\right\}.$

Obserwacja

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

Dowód

Niech $g_i$ będzie generatorem grupy cyklicznej ${\mathbf{𝐆}}_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{𝐆}}_0$ i ${\mathbf{𝐆}}_1$.

Wniosek

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

Przykład

Dla $n⩾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,\dots ,n-1$. Obrót wielokąta foremnego o jeden wierzchołek w prawo, jak na rysunku,

Rysunek: 8.4 Szkic na kartce.

odpowiada cyklicznej permutacji $\pi =(0,1,\dots ,n-1)$. Zastanówmy się teraz jakie elementy składają się na ${\mathbf{𝐒}}_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,\dots ,{\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{𝐒}}_n(\pi )$ jest grupą cykliczną rzędu $n$, czyli z Wniosku Uzupelnic wniosek - nie ma za duzo grup cyklicznych| mamy ${\mathbf{𝐒}}_n(\pi )\approx {\mathbb{\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.

Rysunek: 8.5 Szkic na kartce.

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)\dots (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)\dots (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)\dots ((n-1)/2,(n+1)/2).$

Jakie elementy składają się na ${\mathbf{𝐒}}_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$.

Rysunek: 8.6 Szkic na kartce.

• $\pi \sigma \pi =\sigma$

Rysunek: 8.7 Szkic na kartce.

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

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \aligned \pi\sigma\pi(0)&=&\pi\sigma(n-1)=\pi(1)=0=\sigma(0),\\ \pi\sigma\pi(1)&=&\pi\sigma(0)=\pi(0)=n-1=\sigma(1),\\ \pi\sigma\pi(i)&=&\pi\sigma(i-1)=\pi(n-i+1)=n-i=\sigma(i), \endaligned}

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

Z Obserwacji Uzupelnic obserwacja - postac zbioru generowanego| i naszych spostrzeżeń mamy:

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \aligned S_n({\left\{ {\pi,\sigma} \right\} }) &=&{\left\{ {x_0\cdot\ldots\cdot x_{m-1}: m>0, x_i\in{\left\{ {\pi,\pi^{-1},\sigma,\sigma^{-1}} \right\} }} \right\} }\\ &=&{\left\{ {\pi^k, \pi^k\sigma : 0<k\leq n} \right\} } \endaligned}

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

Parser nie mógł rozpoznać (nieznana funkcja „\begin{array}”): {\displaystyle \begin{array} {ll} \pi,\pi^2,\pi^3,\ldots,\pi^n&\textrm{-- to wszystkie obroty wraz z identycznością},\\ \pi\sigma,\pi^2\sigma,\pi^3\sigma,\ldots,\pi^n\sigma&\textrm{-- to symetrie wobec każdej z } n$osisymetrii$nParser nie mógł rozpoznać (błąd składni): {\displaystyle -kąta foremnego}. \end{array} }

Grupa dihedralna ${\mathbf{𝐃}}_n$ to podgrupa grupy ${\mathbf{𝐒}}_n$ (dla $n⩾3$) generowana przez $\left\{\pi ,\sigma \right\}$.

Produkt grup ${\mathbf{𝐆}}_0=(G_0,\cdot ,1_{G_0})$ i ${\mathbf{𝐆}}_1=(G_1,\cdot ,1_{G_1})$ to grupa ${\mathbf{𝐆}}_0\times {\mathbf{𝐆}}_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{\mathbb{Z}}}_2\times {\mathbb{\mathbb{Z}}}_3$.

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

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

Parser nie mógł rozpoznać (błąd składni): {\displaystyle f(a) = (a \mbox{ {\sf mod} } 2 , \ a \mbox{ {\sf mod} } 3 ) }

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

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

Parser nie mógł rozpoznać (nieznana funkcja „\begin{array}”): {\displaystyle \begin{array} {|c||c|c|c|c|c|c|c|c|} \hline \mathbb{Z}_2\times\mathbb{Z}_4&(0,0)&(0,1)&(0,2)&(0,3)&(1,0)&(1,1)&(1,2)&(1,3)\\ \hline \textrm{rząd}&1&4&2&4&2&4&2&4\\ \hline \end{array} }

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

Obserwacja

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

Dowód

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

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

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \aligned \underbrace{1+\ldots+1}_{r\ razy} \mbox{ {\sf mod} } m &=&r \mbox{ {\sf mod} } m =0,\textrm{ czyli } m

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

Przykład

Niech ${\mathbf{𝐀}}_4$ będzie podgrupą grupy ${\mathbf{𝐒}}_4$ składającą się z tych permutacji, które są złożeniami parzystej liczby transpozycji. Wtedy Parser nie mógł rozpoznać (błąd składni): {\displaystyle \left\vertA_4\right\vert=12} , ale grupa ${\mathbf{𝐀}}_4$ nie ma podgrup rzędu $4$.

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

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

Prawa warstwa $Hg$ podgrupy $\mathbf{𝐇}$ grupy $\mathbf{𝐆}$ 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{𝐃}}_4=(\left\{\pi ,\dots ,{\pi }^4,\pi \sigma ,\dots ,{\pi }^4\sigma \right\},\circ )$ będzie grupa dihedralną symetrii kwadratu. Posiada ona podgrupę cykliczną ${\mathbf{𝐂}}_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

Jeśli $\mathbf{𝐇}$ jest skończoną podgrupą grupy $\mathbf{𝐆}$ i $g\in G$, to Parser nie mógł rozpoznać (błąd składni): {\displaystyle \left\vertgH\right\vert=\left\vertH\right\vert= \left\vertHg\right\vert} .

Dowód

Niech $H=\left\{h_0,\dots ,h_{m-1}\right\}$ i załóżmy, że $g{h}_i=g{h}_j$. Wtedy z prawa skracania mamy $h_i=h_j$. Zatem elementy $g{h}_0,g{h}_1,\cdots ,g{h}_{m-1}$ są parami różne i zbiór

$gH=\left\{g{h}_0,g{h}_1,\cdots ,g{h}_{m-1}\right\},$

ma dokładnie $m$ elementów.

Obserwacja

Dla dowolnej podgrupy $\mathbf{𝐇}$ grupy $\mathbf{𝐆}$ 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 Lagrange'a

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

Dowód

Niech $\mathbf{𝐇}=(\left\{h_0,\dots ,h_{m-1}\right\},\cdot ,1)$ oraz $\mathbf{𝐆}=(\left\{g_0,\dots ,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$,

• Parser nie mógł rozpoznać (błąd składni): {\displaystyle \left\vertg_iH\right\vert=\left\vertH\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,\dots ,g_{n-1}H$ tworzą podział zbioru $G=\left\{g_0,g_1\dots ,g_{n-1}\right\}$ na równoliczne bloki wielkości $m$, skąd natychmiast $m|n$.

Wniosek

Niech $\mathbf{𝐆}=(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)=(\left\{g,g^2,\dots ,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

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

Dowód

Ponieważ $p>1$, to w $G$ jest jakiś element $g\ne 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{𝐆}$, czyli $\mathbf{𝐆}$ jest cykliczna. Reszta wynika już z Wniosku Uzupelnic wniosek - nie ma za duzo grup cyklicznych|.

Obserwacja

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

$\mathbf{𝐆}$ jest grupa cykliczną,

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

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

Dowód

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

$1,g^q,g^{2q},\dots ,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{𝐆}$, mamy $y=g^k$ dla pewnego $k$, skąd $g^{kd}=y^d=1$. Z Wniosku Uzupelnic obserwacja - rzad elementu| 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 (Uzupelnic obserwacja - ostatnia 2| $\Rightarrow$ Uzupelnic obserwacja - ostatnia 3|) przypomnijmy, za Obserwacją Uzupelnic obserwacja - rzad elementu|, ż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. $\phi (d)=\sum _{r|d}\mu (r)\frac{d}{f}$, mamy $f(d)=\phi (d)$.

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

Przykład

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

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

• dzielniki liczby $12$ to $1,2,3,4,6,12$.

• liczba elementów rzędu $d$ dla kolejnych dzielników $d|12$

Parser nie mógł rozpoznać (nieznana funkcja „\begin{array}”): {\displaystyle \begin{array} {|c|c|c|c|c|c|c|} \hline \textrm{dzielnik } d$liczby$12Parser nie mógł rozpoznać (błąd składni): {\displaystyle }&1&2&3&4&6&12\\ \hline \textrm{liczba elementów rzędu } dParser nie mógł rozpoznać (błąd składni): {\displaystyle }&1&1&2&2&2&4\\ \hline \end{array} }

• $\phi (1)=1$, $\phi (2)=1$, $\phi (3)=2$,

$\phi (4)=2$, $\phi (6)=2$, $\phi (12)=4$.