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} }=(G,\cdot ,1)$ , to jaki rząd mają kolejne potęgi $x^{m}$ , dla $m\in \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{aligned}mb&={\text{ NWW }}(m,n)={\frac {mn}{{\text{ NWD }}(m,n)}},\\b&={\frac {n}{{\text{  NWD }}(m,n)}}\end{aligned}}

Ćwiczenie 2

Pokaż, że zbiór funkcji z $\mathbb {R} \longrightarrow \mathbb {R}$ postaci $f_{a,b}(x)=ax+b$ dla $a,b\in \mathbb {R}$ , $a\neq 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 $(\left\lbrace f_{a,b}(x):a,b\in \mathbb {R} ,a\neq 0\right\rbrace ,\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{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)\end{aligned}}

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\neq 1$ , to funkcja $f_{a,b}^{n}$ ma postać $f_{a^{n},c}$ dla pewnego $c$ , ale dla $a\neq 1$ mamy oczywiście $a^{n}\neq 1$ ,
gdy zaś $a=1$ , to $f_{a,b}^{n}=f_{1,nb}$ , co z kolei przy $n\neq 0$ , jest równe $f_{1,0}$ tylko wtedy, gdy $b=0$ .

Ćwiczenie 3

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

Wskazówka

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

Rozwiązanie

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

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

Ćwiczenie 4

Pokaż, że w skończonej grupie ${\mathbf {G} }=(G,\cdot ,1_{G})$ dla jej podgrup ${\mathbf {H} _{0}}=(H_{0},\cdot ,1_{G})$ , ${\mathbf {H} _{1}}=(H_{1},\cdot ,1_{G})$ takich, że NWD $(\left\vert H_{0}\right\vert ,\left\vert H_{1}\right\vert )=1$ mamy

\left\vert H_{0}\cap H_{1}\right\vert =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 {G} }$ . Ponieważ ${\mathbf {G} }$ 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},\ldots ,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 {H} _{0}}$ i grupy ${\mathbf {H} _{1}}$ . Z Twierdzenia Lagrange'a rząd $n$ elementu $x$ dzieli rząd $\left\vert H_{0}\right\vert$ i rząd $\left\vert H_{1}\right\vert$ , co wobec NWD $(\left\vert H_{0}\right\vert ,\left\vert H_{1}\right\vert )=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 {H} _{0}}=(H_{0},\cdot ,1_{G})$ , ${\mathbf {H} _{1}}=(H_{1},\cdot ,1_{G})$ skończonej grupy ${\mathbf {G} }$ rozważ

H_{0}H_{1}=\left\lbrace g\in G:g=h_{0}h_{1}{\text{ dla }}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 {G} }$ .

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 {G} }$ 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}'h_{1}'$ , gdzie $h_{0},h_{0}'\in H_{0}$ i $h_{1},h_{1}'\in H_{1}$ . Aby pokazać, że

(h_{0}h_{1})(h_{0}'h_{1}')\in H_{0}H_{1}

zauważmy najpierw, że $h_{1}h_{0}'\in H_{1}H_{0}=H_{0}H_{1}$ , czyli $h_{1}h_{0}'=h_{0}''h_{1}''$ dla pewnych $h_{0}''\in H_{0}$ , $h_{1}''\in H_{1}$ . Mamy zatem

(h_{0}h_{1})(h_{0}'h_{1}')=h_{0}(h_{1}h_{0}')h_{1}'=h_{0}(h_{0}''h_{1}'')h_{1}'=(h_{0}h_{0}'')(h_{1}''h_{1}')\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 {G} }$ . 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.