Matematyka dyskretna 2/Ćwiczenia 4: Elementy teorii grup

Elementy teorii grup

Ćwiczenie 1

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

Wskazówka

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

Rozwiązanie

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

$\begin{array}{rl}mb& =\text{ NWW }(m,n)=\frac{mn}{\text{ NWD }(m,n)},\\ b& =\frac{n}{\text{ NWD }(m,n)}.\end{array}$

Ćwiczenie 2

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

Wskazówka

Policz złożenie postaci $f_{a,b}{f}_{c,d}$.

Rozwiązanie

Najpierw uzasadnimy, że $(\{f_{a,b}(x):a,b\in \mathbb{ℝ},a\ne 0\},\cdot ,f_{1,0})$ jest grupą:

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

$\begin{array}{rl}(f_{\frac{1}{a},\frac{-b}{a}}\cdot f_{a,b})(x)& =f_{\frac{1}{a},\frac{-b}{a}}(ax+b)=\frac{1}{a}(ax+b)-\frac{b}{a}=x=f_{1,0}(x),\\ (f_{a,b}\cdot f_{\frac{1}{a},\frac{-b}{a}})(x)& =f_{a,b}(\frac{1}{a}x-\frac{b}{a})=a(\frac{1}{a}x-\frac{b}{a})+b=x=f_{1,0}(x).\end{array}$

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

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

Ćwiczenie 3

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

Wskazówka

Gdy $\phi$ jest homomorfizmem, to $\phi (x{)}^r=\phi (x^r)=\phi (1)=1$. Gdy $\phi$ jest izomorfizmem rząd $\phi (x)$ równy jest rzędowi $x$, czyli $r$.

Rozwiązanie

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

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

Ćwiczenie 4

Pokaż, że w skończonej grupie $\mathbf{𝐆}=(G,\cdot ,1_G)$ dla jej podgrup ${\mathbf{𝐇}}_0=(H_0,\cdot ,1_G)$, ${\mathbf{𝐇}}_1=(H_1,\cdot ,1_G)$ takich, że NWD $(\left|H_0\right|,\left|H_1\right|)=1$ mamy

$|H_0\cap H_1|=1.$

Wskazówka

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

Rozwiązanie

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

$x,x^2,x^3,\dots ,x^n=1\in H_0\cap H_1,$

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

Ćwiczenie 5

Dla podgrup ${\mathbf{𝐇}}_0=(H_0,\cdot ,1_G)$, ${\mathbf{𝐇}}_1=(H_1,\cdot ,1_G)$ skończonej grupy $\mathbf{𝐆}$ rozważ

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle H_0H_1=\left\lbrace g\in G:g=h_0h_1\ } dla Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle \ h_0\in H_0, h_1\in H_1 \right\rbrace. }

Pokaż, że $H_0{H}_1=H_1{H}_0$ wtedy i tylko wtedy, gdy $H_0{H}_1$ i $H_1{H}_0$ są podgrupami grupy $\mathbf{𝐆}$.

Rozwiązanie

Załóżmy najpierw, że $H_0{H}_1=H_1{H}_0$. Ponieważ $G$ jest skończony, to aby udowodnić, że $H_0{H}_1$ jest podgrupą $\mathbf{𝐆}$ wystarczy sprawdzić czy $xy\in H_0{H}_1$ dla $x,y\in H_0{H}_1$. Niech więc $x=h_0{h}_1$ oraz $y={h_0}^{\prime }{h_1}^{\prime }$, gdzie $h_0,{h_0}^{\prime }\in H_0$ i $h_1,{h_1}^{\prime }\in H_1$. Aby pokazać, że

$(h_0{h}_1)({h_0}^{\prime }{h_1}^{\prime })\in H_0{H}_1$

zauważmy najpierw, że $h_1{h_0}^{\prime }\in H_1{H}_0=H_0{H}_1$, czyli $h_1{h_0}^{\prime }={h_0}^{″}{h_1}^{″}$ dla pewnych ${h_0}^{″}\in H_0$, ${h_1}^{″}\in H_1$. Mamy zatem

$(h_0{h}_1)({h_0}^{\prime }{h_1}^{\prime })=h_0(h_1{h_0}^{\prime }){h_1}^{\prime }=h_0({h_0}^{″}{h_1}^{″}){h_1}^{\prime }=(h_0{h_0}^{″})({h_1}^{″}{h_1}^{\prime })\in H_0{H}_1.$

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

Ćwiczenie 6

Grupa ${\mathbb{\mathbb{Z}}}_{60}=({\mathbb{\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 ${\mathbb{\mathbb{Z}}}_n$ jest dokładnie $\phi (n)$ elementów rzędu $n$, czyli generujących całą grupę.

$\phi (60)=\phi (2^2)\phi (3)\phi (5)=(2^2-2)(3-1)(5-1)=16.$