Matematyka dyskretna 2/Ćwiczenia 4: Elementy teorii grup

From Studia Informatyczne

Elementy teorii grup

Ćwiczenie 1

Jeśli \displaystyle x\in G ma rząd \displaystyle n w grupie \displaystyle {\mathbf G}=(G,\cdot,1), to jaki rząd mają kolejne potęgi \displaystyle x^m, dla \displaystyle m\in\mathbb{N}?

Wskazówka

Skorzystaj z faktu, że \displaystyle x^a=1 wtedy i tylko wtedy, gdy \displaystyle n|a.

Rozwiązanie

Element \displaystyle x ma rząd \displaystyle n, zatem \displaystyle x^a=1 wtedy i tylko wtedy, gdy \displaystyle n|a. Tym samym \displaystyle x^m ma rząd \displaystyle b wtedy i tylko wtedy, gdy \displaystyle mb jest najmniejszą dodatnią liczbą taką, że \displaystyle n|mb. Innymi słowy, \displaystyle mb jest najmniejszą wielokrotnością liczb \displaystyle m i \displaystyle n, czyli


\displaystyle \aligned mb&= \textrm{ NWW } \displaystyle  (m,n)=\frac{mn}{ \textrm{ NWD } \displaystyle  (m,n)},\\ b&=\frac{n}{ \textrm{  NWD } \displaystyle  (m,n)}. \endaligned


Ćwiczenie 2

Pokaż, że zbiór funkcji z \displaystyle \mathbb{R} \longrightarrow\mathbb{R} postaci \displaystyle f_{a,b}(x)=ax+b dla \displaystyle a,b\in\mathbb{R}, \displaystyle a\neq0 wraz z operacją składania tworzy grupę. Scharakteryzuj rzędy wszystkich elementów tej grupy.

Wskazówka

Policz złożenie postaci \displaystyle f_{a,b}f_{c,d}.

Rozwiązanie

Najpierw uzasadnimy, że \displaystyle (\left\lbrace f_{a,b}(x):a,b\in\mathbb{R},a\neq0 \right\rbrace,\cdot,f_{1,0}) jest grupą:

  • składanie funkcji jest oczywiście łączne,
  • \displaystyle f_{1,0} jest elementem neutralnym, gdyż jest funkcją identycznościową: \displaystyle f_{1,0}(x)= 1x+0 = x,
  • elementem odwrotnym do \displaystyle f_{a,b} jest \displaystyle f_{\frac{1}{a},\frac{-b}{a}}, gdyż


\displaystyle \aligned \left( f_{\frac{1}{a},\frac{-b}{a}}\cdot f_{a,b} \right)(x) &=f_{\frac{1}{a},\frac{-b}{a}}(ax+b) =\frac{1}{a}(ax+b)-\frac{b}{a}=x=f_{1,0}(x),\\ \left( f_{a,b}\cdot f_{\frac{1}{a},\frac{-b}{a}} \right)(x) &=f_{a,b}\left( \frac{1}{a}x-\frac{b}{a} \right) =a\left( \frac{1}{a}x-\frac{b}{a} \right)+b=x=f_{1,0}(x). \endaligned


Rozważmy teraz rzędy elementów naszej grupy. Z definicji elementu neutralnego \displaystyle f_{1,0} ma rząd \displaystyle 1. Okazuje się, że dowolny inny element ma rząd nieskończony, tzn. żadna jego dodatnia potęga nie równa się \displaystyle f_{1,0}. Rzeczywiście:

  • gdy \displaystyle a\neq1, to funkcja \displaystyle f_{a,b}^n ma postać \displaystyle f_{a^n,c} dla pewnego \displaystyle c, ale dla \displaystyle a\neq1 mamy oczywiście \displaystyle a^n\neq1,
  • gdy zaś \displaystyle a=1, to \displaystyle f_{a,b}^n=f_{1,nb}, co z kolei przy \displaystyle n\neq 0, jest równe \displaystyle f_{1,0} tylko wtedy, gdy \displaystyle b=0.

Ćwiczenie 3

Niech \displaystyle \varphi: G_0 \longrightarrow G_1 będzie homomorfizmem grup \displaystyle {\mathbf G_0}=(G_0,\cdot,1_{G_0}) w \displaystyle {\mathbf G_1}=(G_1,\cdot,1_{G_1}). Co można powiedzieć o rzędzie \displaystyle \varphi(x) w \displaystyle {\mathbf G_1}, gdy \displaystyle x\in G_0 ma rząd \displaystyle r w \displaystyle {\mathbf G_0}? A jeśli \displaystyle \varphi jest izomorfizmem grup?

Wskazówka

Gdy \displaystyle \varphi jest homomorfizmem, to \displaystyle \varphi(x)^r =\varphi(x^r)= \varphi(1)=1. Gdy \displaystyle \varphi jest izomorfizmem rząd \displaystyle \varphi(x) równy jest rzędowi \displaystyle x, czyli \displaystyle r.

Rozwiązanie

Z równości \displaystyle \varphi(x)^r=\varphi(x^r)=\varphi(1_{G_0})=1_{G_1} wiemy, że \displaystyle r jest wielokrotnością rzędu \displaystyle \varphi(x).

Ponieważ dla dowolnego \displaystyle n mamy \displaystyle \varphi(x)^n=\varphi(x^n), to gdy \displaystyle \varphi jest izomorfizmem, \displaystyle x^n=1 wtedy i tylko wtedy, gdy \displaystyle \varphi(x)^n=1. Oznacza to, że rzędy \displaystyle x i \displaystyle \varphi(x) są równe.

Ćwiczenie 4

Pokaż, że w skończonej grupie \displaystyle {\mathbf G}=(G,\cdot,1_G) dla jej podgrup \displaystyle {\mathbf H_0}=(H_0,\cdot,1_G), \displaystyle {\mathbf H_1}=(H_1,\cdot,1_G) takich, że NWD \displaystyle  (\left\vert H_0 \right\vert,\left\vert H_1 \right\vert)=1 mamy


\displaystyle \left\vert H_0\cap H_1 \right\vert=1.


Wskazówka

Rozważ rząd elementu \displaystyle x\in H_0\cap H_1.

Rozwiązanie

Przecięcie \displaystyle (H_0\cap H_1,\cdot,1_G) jest podgrupą grupy \displaystyle {\mathbf G}. Ponieważ \displaystyle {\mathbf G} jest skończona, to element \displaystyle x\in H_0\cap H_1 musi mieć rząd skończony, powiedzmy \displaystyle n. Zatem


\displaystyle x,x^2,x^3,\ldots,x^n=1\in H_0\cap H_1,


i elementy te tworzą podgrupę grupy \displaystyle H_0\cap H_1 ale także podgrupę grupy \displaystyle {\mathbf H_0} i grupy \displaystyle {\mathbf H_1}. Z Twierdzenia Lagrange'a rząd \displaystyle n elementu \displaystyle x dzieli rząd \displaystyle \left\vert H_0 \right\vert i rząd \displaystyle \left\vert H_1 \right\vert, co wobec NWD \displaystyle  (\left\vert H_0 \right\vert,\left\vert H_1 \right\vert)=1 daje \displaystyle n=1, a zatem \displaystyle x=1. Udowodniliśmy więc, że jedynym elementem \displaystyle H_0\cap H_1 jest element neutralny \displaystyle 1_G.

Ćwiczenie 5

Dla podgrup \displaystyle {\mathbf H_0}=(H_0,\cdot,1_G), \displaystyle {\mathbf H_1}=(H_1,\cdot,1_G) skończonej grupy \displaystyle {\mathbf G} rozważ


\displaystyle H_0H_1=\left\lbrace g\in G:g=h_0h_1\ dla \displaystyle  \ h_0\in H_0, h_1\in H_1 \right\rbrace.


Pokaż, że \displaystyle H_0H_1=H_1H_0 wtedy i tylko wtedy, gdy \displaystyle H_0H_1 i \displaystyle H_1H_0 są podgrupami grupy \displaystyle {\mathbf G}.

Rozwiązanie

Załóżmy najpierw, że \displaystyle H_0H_1=H_1H_0. Ponieważ \displaystyle G jest skończony, to aby udowodnić, że \displaystyle H_0H_1 jest podgrupą \displaystyle {\mathbf G} wystarczy sprawdzić czy \displaystyle xy\in H_0H_1 dla \displaystyle x,y\in H_0H_1. Niech więc \displaystyle x=h_0h_1 oraz \displaystyle y=h_0'h_1', gdzie \displaystyle h_0,h_0'\in H_0 i \displaystyle h_1,h_1'\in H_1. Aby pokazać, że


\displaystyle (h_0h_1)(h_0'h_1')\in H_0H_1


zauważmy najpierw, że \displaystyle h_1h_0'\in H_1H_0=H_0H_1, czyli \displaystyle h_1h_0'=h_0''h_1'' dla pewnych \displaystyle h_0''\in H_0, \displaystyle h_1''\in H_1. Mamy zatem


\displaystyle (h_0h_1)(h_0'h_1')=h_0(h_1h_0')h_1'=h_0(h_0''h_1'')h_1'=(h_0h_0'')(h_1''h_1')\in H_0H_1.


Dla dowodu implikacji odwrotnej załóżmy, że \displaystyle H_0H_1 i \displaystyle H_1H_0 są podgrupami grupy \displaystyle {\mathbf G}. Niech \displaystyle x\in H_0H_1, czyli \displaystyle x=h_0h_1 dla pewnych \displaystyle h_0\in H_0, \displaystyle h_1\in H_1. Pokażemy, że \displaystyle x\in H_1H_0. Istotnie, \displaystyle x = h_0h_1=(h_1^{-1}h_0^{-1})^{-1}\in H_1H_0, bo \displaystyle h_1^{-1}h_0^{-1}\in H_1H_0. A zatem \displaystyle H_0H_1\subseteq H_1H_0. Odwrotną inkluzję dowodzi się analogicznie.

Ćwiczenie 6

Grupa \displaystyle {\mathbf \mathbb{Z}_{60}}=(\mathbb{Z}_{60},+,0) jest cykliczna. Jak wiele jej elementów generuje całą grupę?

Wskazówka

Skorzystaj z Obserwacji opisującej liczbę elementów zadanego rzędu w grupie cyklicznej.

Rozwiązanie

W grupie cyklicznej \displaystyle \mathbb{Z}_{n} jest dokładnie \displaystyle \varphi(n) elementów rzędu \displaystyle n, czyli generujących całą grupę.


\displaystyle \varphi(60)=\varphi(2^2)\varphi(3)\varphi(5)= (2^2-2)(3-1)(5-1)=16.