Riešené úlohy zo skrípt

[ZuzanaHromcova]

3.2.7. Tvorí množina $M$ spolu s operáciou skladania zobrazení grupu?

a) $M = \{ f: \mathbb{Z} \to \mathbb{Z}, f$ je bijekcia$\}$

Musíme overiť, že
I. $M$ je neprázdna množina. To zrejme platí, napríklad identita na množine $\mathbb{Z}$ $id_{\mathbb{Z}}$ je bijekcia.
II. $\circ$ je binárna operácia na $M$
- platí, pretože zložením dvoch bijekcií je bijekcia
III. asociatívnosť $\circ$
- platí vďaka asociatívnosti skladania zobrazení
IV. existencia neutrálneho prvku
- pretože $f$ je zo $\mathbb{Z}$ do $\mathbb{Z}$, $id_z$ je obojstranný neutrálny prvok
V. existencia inverzného prvku ku každému prvku $M$
- ku každej bijekcii existuje inverzná funkcia, teda taká funkcia $f^{-1}$, že $f \circ f^{-1} = f^{-1} \circ f = id_{\mathbb{Z}}$

$\Rightarrow$ $M$ je GRUPA

JG: OK, len ešte je treba aspoň skonštatovať, že $M$ je neprázdna množina (napr. identita $id_{\mathbb{Z}}$ je bijekcia)
Opravené.
JG: OK. Čo s tým b) a c)?

Vedel by mi niekto poradiť, aký je rozdiel medzi úlohou b) a c) v tomto príklade?

JG: V tých príkladoch ide o "veľkosť" množiny $X_f=\{n\in\mathbb{Z}; f(n)=n\}$ a/alebo jej doplnku $\mathbb{Z}\setminus X_f$, v b) má byť doplnok $\mathbb{Z}\setminus X_f$ konečný, v c) má byť $X_f$ konečná.

Do $M_2$ patrí napr. $f=id_{\mathbb{Z}}$, lebo množina $X_f$ je celé $\mathbb{Z}$ a teda uvedená rovnosť platí pre všetky prvky okrem prvkov z prázdnej množiny, ktorá je konečná (t.j. $\mathbb{Z}\setminus X_f$ je konečná).
Do $M_3$ patrí napr. $g(x)=-x$, lebo $X_g=\{0\}$ je jednoprvková, a teda konečná.
A neplatí to "naopak, do kríža", t.j. $f\notin M_3$, $g\notin M_2$.

[ZuzanaHromcova]

3.2.11. Ak $(G,\circ)$ je grupa a $a \in G$ je nejaký jej prvok, tak zobrazenie $f_a: G \to G$ definované ako $f_a(b) = a \circ b$ je bijekcia.

Ukážeme, že $f_a$ je injekcia.
Nech pre nejaké $b_1, b_2 \in G: \quad f_a(b_1) = f_a(b_2)$. Potom podľa definície $a \circ b_1 = a \circ b_2$. Keďže $(G, \circ)$ je grupa a $a \in G$, musí existovať inverzný prvok k $a$, označme ho $a^{-1}$ a prenásobme ním zľava obe strany rovnosti. Dostaneme $a^{-1} \circ (a \circ b_1) = a^{-1} \circ (a \circ b_2)$. Vďaka asociatívnosti operácie $\circ$ v grupe platí $(a^{-1} \circ a) \circ b_1 = (a^{-1} \circ a) \circ b_2$. Podľa definície inverzného prvku ďalej dostávame $e \circ b_1 = e \circ b_2$, kde $e$ je neutrálny prvok grupy $G$. Z jeho definície nakoniec dostaneme $b_1 = b_2$. Tým sme dokázali, že $f_a$ je injekcia.

Ukážeme, že $f_a$ je surjekcia.
Nech $z \in G$, ukážeme, že existuje nejaké $b \in G$ také, že $f_a(b)=z$.
$f_a(b)=z \Leftrightarrow a \circ b = z$, zľava prenásobíme inverzným prvkom k prvku $a$, teda $a^{-1}$ a dostaneme $a^{-1} \circ (a \circ b) = a^{-1} \circ z$. Podobne ako v predošlej časti využijeme asociatívnosť operácie v grupe, definíciu inverzného a neutrálneho prvku a dostávame: $b = a^{-1} \circ z$. Pretože $a^{-1}$ aj $z$ sú prvkami $G$ a $\circ$ je binárna operácia na $G$, musí aj prvok $a^{-1} \circ z$ patriť tejto množine. Tým sme ale našli požadovaný prvok $b$, teda $f$ je surjekcia.

JG: OK, 1 bod

[ZuzanaHromcova]

3.2.17. Nech konečná množina $G=\{e,a_1,...,a_n\}$ tvorí s operáciou $\ast$ komutatívnu grupu a $e$ je jej neutrálny prvok. Dokážte, že $(a_1 \ast a_2 \ast ... \ast e)^2 = e$.

Keďže $(G,\ast)$ je grupa, musí ku každému prvku $a_i \in G$ existovať prvok $a_i^{-1}$ taký, že $a_i \ast a_i^{-1} = e$. Ak pre nejaké $a_i \neq e$ existuje $a_i^{-1}=e$, tak dostávame $a_i \ast a_i^{-1} = e \Leftrightarrow a_i \ast e = e \Leftrightarrow a_i = e$, čo je spor s $a_i \neq e$. Takže pre každé $a_i$ vieme nájsť práve inverzný prvok rôzny od $e$, teda $a_j$. Podľa vety dokázanej na prednáške platí, že v grupe je inverzný prvok jednoznačne určený, teda aj tu má každý prvok práve jeden inverzný prvok.
JG: tu je len dokázané, že pre $a\ne e$ je aj $a^{-1}\ne e$. To, že pre každé $a$ existuje práve jeden inverzný asi vyplýva z niečoho iného (neboo také tvrdenie náhodou na prednáške?).
Opravené.
JG: Skutočnosť, že inverzné prvky sú určené jednoznačne ale riešia len časť problému. V podstate jednoznačnosť sama o sebe len znamená, že máme FUNKCIU, pomenujem ju napr. $\text{inv}$ definovanú "predpisom" $\text{inv}(a)=c$, pričom $c$ je (teda jediné) také, že $c\star a = a \star c = e$. Priamo ale nehovorí ani o injektívnosti (ok, injektívnosť z jednoznačnosti asi ľahko vyplýva) ani o surjektívnosti tejto funkcie (v prípade konečných množín sú podľa príkladu, ktorý je tu o niečo vyššie vyriešený sú injektívnosť a surjektívnosť ekvivalentné, treba si uvedomiť, že v nasledujúcom postupe ich naozaj obe potrebujete. Vy nasledujúcom postupe v podstate využívate injektívnosť a teda skryte vďaka konečnosti aj surjektívnosť).

Teraz prepíšeme $(a_1 \ast a_2 \ast ... \ast e)^2 = e$ podľa definície na $(a_1 \ast a_2 \ast ... \ast e) \ast (a_1 \ast a_2 \ast ... \ast e)$. Vďaka asociatívnosti a komutatívnosti grupy $(G,\ast)$ môžeme tieto členy poprehadzovať tak, aby vedľa seba bol vždy prvok $a_i$ z prvej zátvorky a jemu príslušný inverzný prvok $a_j$ z druhej zátvorky. Pretože toto rozloženie je jednoznačné a ide o konečnú množinu, budeme mať vedľa seba konečný počet dvojíc "prvok a jeho inverzný prvok". Podľa definície ale $a_i \ast a_j = e$, takže vyjadrenie prepíšeme na $e \ast e \ast ... \ast e = e$ (vďaka viacnásobnému použitiu definície neutrálneho prvku), čo sme chceli dokázať.

JG: Tá druhá časť by potom už bola OK.

[ZuzanaHromcova]

3.2.18. Nech $\ast$ je binárna operácia na množine $A$ taká, že pre každé $a, b, c \in A$ platí $a \ast (b \ast c) = (a \ast c ) \ast b$ a $\ast$ má neutrálny prvok. Dokážte, že operácia je komutatívna a asociatívna.

Operácia má na množine neutrálny prvok, označme ho $e$. Platí $\exists e \in A \forall a \in A: \quad a \ast e = e \ast a = a$. Ďalej platí $a \ast (b \ast c) = (a \ast c ) \ast b$. Špeciálne, položme $a=e$, potom dostávame:
$e \ast (b \ast c) = (e \ast c) \ast b$, čo je na základe definície neutrálneho prvku ekvivalentné s $b \ast c = c \ast b$, teda platí komutatívnosť.
Pretože platí komutatívnosť, ľavú stranu $a \ast (b \ast c) = (a \ast c ) \ast b$ môžeme prepísať a dostávame $a \ast (c \ast b) = (a \ast c ) \ast b$, čo platí pre všetky $b, c \in A$, teda platí aj asociatívnosť operácie $\ast$.

JG: OK 1 bod. Pekný dôkaz.

[ZuzanaHromcova]

3.2.19. Nech $(G,\circ)$ je grupa. Dokážte, že ak $x \circ x = x$, tak $x = e$.

$(G,\circ)$ je grupa. Ak $x \in G$, musí k nemu existovať inverzný prvok $x^{-1}$ taký, že $x \circ x^{-1} = x^{-1} \circ x = e$, kde $e$ je neutrálny prvok v grupe. Nech platí $x \circ x = x$, túto rovnosť zľava prenásobíme prvkom $x^{-1}$ a dostávame $x^{-1} \circ (x \circ x) = x^{-1} \circ x$. Vďaka asociatívnosti operácie v grupe to je ekvivalentné s $(x^{-1} \circ x) \circ x = x^{-1} \circ x$. Teraz využijeme definíciu inverzného prvku a dostávame $e \circ x = e$. Podľa definície neutrálneho prvku sa ľavá strana rovná $x$, teda $x=e$, čo sme chceli dokázať.

JG: OK, 1 bod

[jaroslav.gurican]

2.1.1. Dokážte, že ak $g \circ f$ je surjekcia, tak aj $g$ je surjekcia. Platí aj opačná implikácia? Musí byť $f$ surjekcia?

Nech $f: X \to Y, g: Y \to Z$. Nech $g \circ f$ je surjekcia, teda pre každé $z \in Z \quad \exists x \in X$ také, že $g(f(x)) = z$. To ale znamená, že zobrazenie $g$ musí nadobúdať ľubovoľnú hodnotu zo $Z$, teda $g$ je surjekcia.
Teraz dokážeme opačnú implikáciu. Nech $g$ je surjekcia, potom $g(y)$ nadobúda všetky hodnoty $z \in Z$. Potom ale $(g \circ f)(x) = g(f(x))$ je tiež surjekcia, preto aj zložená funkcia $g \circ f$ nadobúda všetky hodnoty zo Z, teda je surjekcia.
Musí byť $f$ surjekcia? Sporom. Nech $f$ nie je surjekcia, teda $\exists y \in Y \quad \nexists x \in X \quad f(x)=y$. Potom ale $g \circ f$ nie je zobrazenie, pretože existuje také $y$ z definičného oboru, pre ktoré zobrazenie nie je definované. Funkcia $f$ preto musí byť tiež surjekcia.

Prvá časť je správne. Druhá nie, takže bod až potom, ako to opravíte.

[Martin Sleziak]

Vedel by mi niekto poradiť, aký je rozdiel medzi úlohou b) a c) v tomto príklade?

V zadaní je

b) $M_2=\{f\in M_1; f(n)=n \text{ pre všetky celé čísla $n$ až na konečný počet}\}$
c) $M_3=\{f\in M_1; f(n)=n \text{ len pre konečný počet }n\}$.

Len pre konečný počet $n$ znamená, že tých $n$-ov, ktoré spĺňajú $f(n)=n$ má byť konečne veľa. Napríklad: $f(n)=n+1$ pre párne $n$ a $f(n)=n-1$ pre nepárne $n$. (T.j. funkcia, ktorá vždy vymení susedné čísla.) V tomto prípade je ich počet 0, teda konečný.

Až na konečný počet $n$ znamená, že tých $n$-ov, ktoré nespĺňajú $f(n)=n$ má byť konečne veľa. Napríklad $f(n)=n$. V tomto prípade je ich počet 0, teda konečný.

(Ak by bolo treba nejakú ďalšiu diskusiu k tomu to príkladu, asi by bolo lepšie naň založiť samostatné vlákno.)

[FilipJanitor]

Možno iný dôkaz k
2.2.2. Dokážte, že ak $g \circ f$ je injekcia, tak aj f je injekcia.
Sporom, nech $g \circ f$ je injekcia a f nieje injekcia. potom $\exists x_1,x_2 \in X: x_1 \neq x_2 \land f(x_1)=f(x_2)$. Označme $f(x_1) = f(x_2) = y_0 \in Y$ nech $g(y_0)=z_0$. Keďže $g$ je funkcia, toto implikuje $g \circ f(x_1) = z_0 = g \circ f(x_2)$. To je spor s predpokladom, pretože $g \circ f$ má byť (je) injekcia, no našli sme také $x_1$ a $x_2$, ktoré sa nerovnajú, no sú zobrazené na rovnaké $z$. Teda $f$ musí byť injekcia.

JG: OK, 1 bod

[FilipJanitor]

Neviem, či je vhodné zakladať nové vlákno, aby to tu zostalo prehľadné, preto sem prikladám riešenia iných úloh:
3.2.15 Dokážte, že konečná grupa s párnym počtom prvkov obsahuje prvok rôzny od neutrálneho taký, že $a \circ a=e$.
Platí $e \circ e = e$ čiže e je sám sebe inverzný. Pre grupu platí, že pre$ \forall x \in G \exists !x^{-1} : x \circ x^{-1} = e$ (vyplýva to z toho tvrdenia na prednáške, že ak má prvok 2 ľavé inverzné tak nemá pravý a naopak - ak má 2 pravé tak nemá ľavý) Dokopy prvkov v tejto grupe, (keď počet jej prvkov je 2k) rôznych od $e$ je 2k-1 . Teda vieme vytvoriť dvojice typu prvok a k nemu inverzný. JG: prečo nemáme trojice typu $a, a^{-1}, (a^{-1})^{-1}$, štvorice typu $a, a^{-1}, (a^{-1})^{-1}, ((a^{-1})^{-1})^{-1}$,...? Týchto dvojíc bude k-1. JG: asi len za predpokladu, že pre $a\ne e$ je $a^{-1}\ne a$, inak $a, a^{-1}$ nie je "dvojica", ale jeden prvok
Teda prvkov v nich bude 2k-2. Dokopy však je v množine prvkov grupy iných ako e o jeden prvok viac, čiže ak tento patrí do grupy musí mať inverzný a keďže e nemôže byť jeho inverzný lebo $e \circ a \neq a$ ak $a \neq e$ tak musí byť inverzný samému sebe, teda $a \circ a=e$

[FilipJanitor]

3.2.16 Nech $(g, * )$ je grupa a $a \in G$. Potom pre $ \forall n \in \mathbb{N}$ definujeme indukciou prvok $a^n$ nasledovne:
$a^0 = e$
$a^{n+1} = a^n * a$
pre záporné $a^{-n} = (a^{-1})^n$. Dokážte, že pre ľubovoľné $a,b \in G$ a $m,n \in \mathbb{Z}$ platí:
a) $a^{n+m} = a^n * a^m$
$a^{n+m} = e * a * a * ... * a $ kde počet $a$ je $m+n$ keďže $e$ je neutrálny prvok $ a * a * ... * a $ kde počet $a$ je $m+n$, sa to celé rovná $a^{m} * a^{n} = e * a * a * ... * a * e * a * a * ... * a$. Počet $a$ v prvej skupine je $m$ a počet v druhej je $n$. Keďže $e$ je neut. prvok tak sa to rovná $ a * a * ... * a $ kde počet $a$ je $m+n$ Teda tie dve sa rovnajú.

b) $(a^m)^n = a^{mn}$
$(a^m)^n = e*(e*a*a ... *a) * (e*a*a ... *a) * ... * (e*a*a ... *a) $ V každej zátvorke je $m$ krát $a$ a zátvoriek je dokopy $n$. Vďaka asociatívnosti to celé môžeme prezátvorkovať na jednu veľkú zátvorku a keďže e je neutrálny prvok, ktorý vypadne, sa to rovná $ a * a * ... * a $ kde počet $a$ je $m$ $n$-tíc čo je $mn$ teda je to $a^{mn}$

c) ak je $*$ komutatívna operácia, tak potom $ a^n * b^n = (a*b)^n $
$ a^n * b^n = e * a * a ... * a * e * b * b ... * b$ Kde počet $a$ je $n$ a počet $b$ je $n$. Keďže $*$ je komutat. aj asociat a $e$ je neut. prvok, môžeme vytvoriť $n$ zátvoriek $ (a*b) * (a*b) * ... * (a*b) $ čo je $ (a*b)^n $

V každom z týchto príkladov, ak $n$ alebo $m$ by boli záporné čísla, bol by tam len medzikrok, že všetky $a$ na začiatku by sa prepísali na $(a^{-1})$ a na konci úprav by sa dalo znamienko mínus pred exponent a $a^{-1}$ by prepísalo zas na $a$. Postup úprav by bol presne ten istý. Aj v poslednom prípade, pretože podľa tvrdenia 3.2.6 z učebnice $(a * b)^{-1} = b^{-1} * a^{-1}$ a zo zadania vieme, že $*$ je komutatívna operácia.

JG: Toto je samozrejme v podstate dobre, celé je to dosť jasné. Viac menej ale naozaj robíte dôkaz pre prípad $m,n>0$ (a v takom prípade tam vlastne to $e$ (ako e*(e*a*a ... *a)$ nemusiíte písať. Presnejšie by sa mal dôkaz robiť pomocou matematickej indukcie, podobne ako v skriptách spravený dôkaz pre zovšeobecnený asociatívny zákon. 1 bod.