Riešené úlohy zo skrípt

[ZuzanaHromcova]

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.

Opačná implikácia neplatí, stačí nájsť jeden kontrapríklad, teda takú dvojicu funkcií $f: X \to Y, g: Y \to Z$, že g bude surjektívne a $g \circ f$ nebude surjektívne. Napríklad $f: \mathbb{R} \to \mathbb{R}, g: \mathbb{R} \to \mathbb{R}, f(x)=e^x, g(x)=x$. Zobrazenie $g$ je surjekcia, nadobúda všetky hodnoty z $\mathbb{R}$, ale $g \circ f (x) = e^x$ nadobúda len hodnoty z $ \mathbb{R}^+$, teda $g \circ f$ nie je surjekcia.

Musí byť $f$ surjekcia? Nemusí, vezmime napríklad funkcie $f: \mathbb{R} \to \mathbb{R}, g: \mathbb{R} \to \mathbb{R}, f(x)=e^x, g(x)=ln(x)$. Zobrazenie $g \circ f (x) = x$ je surjektívne, ale zobrazenie $f$ nie je, pretože nadobúda len hodnoty z $ \mathbb{R}^+$.

JG: OK, 1 bod

[ZuzanaHromcova]

2.2.2. Dokážte, že ak $g \circ f$ je injekcia, tak aj $f$ je injekcia.

Nech $f: X \to Y, g: Y \to Z$. Nech $g \circ f$ je injekcia, potom $\forall x_1, x_2 \in X: \quad x_1 \neq x_2 \Rightarrow g \circ f (x_1) \neq g \circ f (x_2)$. Keby f nebola injekcia, tak $\exists x_1, x_2 \in X: x_1 \neq x_2 \land f(x_1)=f(x_2)$. To ale znamená, že funkcia $g \circ f$ priradila jednej hodnote $y_1=f(x_1)=f(x_2)=y_2, \quad y_1,y_2 \in Y$ dve rôzne funkčné hodnoty $g(f(x_1))=g(y_1), \quad g(f(x_2))=g(y_2), \quad g(y_1) \neq g(y_2)$. To je spor s predpokladom, že $g \circ f$ je funkcia, preto "$f$ nie je injekcia neplatí", takže $f$ je injekcia platí.

JG: Myšlienka je OK, ale je tam syntaktická chyba. Funkcia $g\circ f$ "typicky" nezobrazuje prvky typu $f(x_1)$ ($f(x_2)$).
Opravené.
JG: Stále je problém s $g\circ f$, prečo si myslíte, že nie to je funkcia? Veď pre argumenty $x_1\ne x_2$ môže platiť $g\circ f (x_1)\ne g\circ f(x_2)$, tam nie je s definíciou funkcie žiadny konflikt. A funkcia $g\circ f$ má ako svoje argumenty $x_1, x_2$ a nie $y_1,y_2$.

[ZuzanaHromcova]

2.2.3. Dokážte: Ak $g \circ f$ je bijekcia, tak $f$ je injekcia a $g$ je surjekcia.

Nech $g \circ f$ je bijekcia, potom $g \circ f$ je injekcia aj surjekcia. Pretože je surjekcia, podľa úlohy 2.2.1. platí, že $g$ je surjekcia. Pretože je injekcia, podľa úlohy 2.2.2. je $f$ injekcia.

JG: OK, 1 bod

[ZuzanaHromcova]

2.2.4. Nech $f: X \to Y$ je zobrazenie a $X \neq \emptyset$. Potom

a) $f$ je injekcia práve vtedy, keď existuje také $g$, že $g \circ f = id_X$

$\Leftarrow$
Nech existuje $g$ také, že $g \circ f = id_X$, potom $\forall x \in X: \quad g(f(x))=x$. Ak $\exists x_1, x_2 \in X: \quad f(x_1)=f(x_2)$, potom $g(f(x_1))=g(f(x_2))$, čo je podľa predošlej (JG: gramatickej) vety ekvivalentné $x_1=x_2$. Teda $f$ musí byť injekcia.
JG: OK. Dá sa použiť aj tvrdenie príkladu 2.2.3. Zobrazenie $id_X$ je bijekcia, $id_X=g \circ f$, preto podľa 2.2.3 je $f$ injekcia.

$\Rightarrow$
Nech $f$ je injekcia. Potom $\forall x_1, x_2 \in X: \quad f(x_1)=f(x_2) \Rightarrow x_1=x_2$. Označme $Y'$ množinu všetkých takých $y \in Y$, pre ktoré $\exists x \in X: \quad f(x)=y$. Pretože $X \neq \emptyset$, existuje nejaký prvok v množine $X$, označme ho $a$. Zobrazenie $g$ potom stačí definovať ako $g: Y \to X$, pre $y \in Y': g(y_x)=x$, kde $y_x=f(x)$ ($f$ f je injekcia, teda je to jednoznačne určené) a pre $y \notin Y' g(x)=a$, teda $g \circ f (x) = g(f(x)) = g(y_x) = x$, teda $g \circ f = id_X$.
JG: OK. Kde je využitý predpoklad $X\ne \emptyset$?
Opravené.

b) $f$ je surjekcia práve vtedy, keď existuje také $h$, že $f \circ h = id_Y$.

$\Leftarrow$
Nech existuje také $h$, že $f \circ h = id_Y$. Potom pre $\forall y \in Y: \quad f(h(y))= y$. To znamená, že pre každé $y\in Y$ musí existovať nejaké také $h(y)$, že $f(h(y))=y$. Teda $f$ je surjekcia.
JG: OK. Podobne ako v a) sa dá využiť tvrdenie 2.2.3

$\Rightarrow$
Nech $f$ je surjekcia. Potom $\forall y \in Y \exists x \in X: \quad f(x)=y$. Keď vezmeme ľubovoľné $y \in Y$, je nadobudnuté pre niektoré $x \in X$. Definujeme množinu $X'$ tak, že pre každú hodnotu $y \in Y$ zvolíme jedno $x \in X$, pre ktoré $f(x)=y$. Zobrazenie $h$ potom definujeme ako $h: Y \to X', h(y)=x$. Potom pre $\forall y \in Y: \quad f \circ h (y) = f(h(y)) = f(x) = y$, teda $f \circ h = id_y$.
JG: Podobne ako v a), tu MUSÍTE zobrazenie $g$ definovať ako zobrazenie $g: Y\to X$, nie $g: Y\to X'$ (dôležité je to samozrejme len vtedy, keď $X'\subsetneq X$). Tu je ten rozdiel ale naozaj len formálny, netreba to opravovať. Je v b) niekde využitý predpoklad $X\ne \emptyset$?
Podľa mňa v časti b) tento predpoklad nepotrebujeme, pretože pokiaľ $X= \emptyset$, tak $f$ je zobrazenie len a len vtedy, ak $Y= \emptyset$, teda zobrazenie $h: Y \to X = h: \emptyset \to \emptyset = \emptyset$, zložením zobrazení $f$ a $h$ bude opäť prázdna množina, teda $f \circ h = id_Y$.

c) K zobrazeniu $f$ existuje inverzné zobrazenie práve vtedy, keď $f$ je bijekcia.

$\Leftarrow$
Ak $f$ je bijekcia, tak je injekcia a surjekcia. Keďže $f$ je injekcia, tak existuje ľavé inverzné zobrazenie (viď a)., keďže $f$ je surjekcia, existuje pravé inverzné zobrazenie (viď b). Keď existuje pravé aj ľavé inverzné zobrazenie, tak sa tieto zobrazenia rovnajú (DEF JG: to nie je definícia, to vyplýva z toho, že skladanie zobrazení sa správa asociatívne.).

$\Rightarrow$
Nech existuje inverzné zobrazenie k $f$, potom existuje ľavé aj pravé inverzné zobrazenie. Keďže existuje ľavé inverzné zobrazenie k $f$, tak $f$ je injekcia, keďže existuje pravé inverzné zobrazenie, $f$ je surjekcia. Keďže $f$ je injekcia aj surjekcia, $f$ je bijekcia (DEF).
JG: OK. 1 bod (i keď v časti c) je pri implikácii $\Leftarrow$ stále drobný problém)

[ZuzanaHromcova]

2.2.5. Nech $f: X \to Y, g: Y \to X, h: Y \to X$ sú zobrazenia. Ak $g$ aj $h$ sú inverzné zobrazenia k $f$, tak $g=h$. JG: Trochu si rýpnem. Nevyužili ste toto tvrdenie bez dôkazu v dôkaze implikácie $\Leftarrow$ prípadu c) v príklade 2.2.4? ($g$ je inverzné ku $f$ a teda aj pravé inverzné ku $f$, $h$ je inverzné ku $f$ a teda aj ľavé inverzné ku $f$. Tam vyššie píšete, že ľavé a pravé inverzné zobrazenia, ak existujú, musia byť rovnaké. )

Platí $g: Y \to X, h: Y \to X$, stačí teda overiť, či sa zobrazenia rovnajú aj vo všetkých funkčných hodnotách, teda či $\forall x \in X: \quad g(x)=h(x)$.

$\forall x \in X: \quad f(x)=y \Rightarrow q(y)=x \land h(y)=x$. JG: Je to potiaľto dostatočný dôkaz a to ďalej uvádzate ako alternatívny dôkaz?

Vieme, že $g$ je inverzné zobrazenie k $f$, teda $g \circ f = id_X$ a $h$ je inverzné zobrazenie k $f$, teda $h \circ f = id_X$. Pravé strany sa rovnajú, musia sa rovnať aj ľavé, takže $g \circ f = h \circ f$. Obe strany môžeme sprava zložiť s $f^{-1}$, čo je inverzné zobrazenie k $f$, dostaneme $(g \circ f) \circ f^{-1} = (h \circ f) \circ f^{-1}$.
Vďaka asociatívnosti operácie skladania zobrazení to môžeme prepísať ako $g \circ (f \circ f^{-1}) = h \circ (f \circ f^{-1})$. Podľa definície $f^{-1}$ platí $f \circ f^{-1} = id_y$, teda rovnosť môžeme prepísať ako $g \circ id_y = h \circ id_y$, po vykonaní operácie skladania funkcií dostávame $g=h$, čo sme chceli dokázať.

JG: Táto druhá časť je určite OK, 1 bod. (ale pozor, príklad 2.2.4 zabezpečuje existenciu inverzného zobrazenia (čo Ste využili) keď sú nejaké množiny neprázdne, tu taký predpoklad nie je, asi by bolo dobre ešte rozobrať nejaké "triviálne" prípady)

Triviálne prípady: ak $f=\emptyset$, inverzné zobrazenie $f^{-1}={(x,y); (y,x)\in f}$ musí byť taktiež prázdna množina, pretože $f$ neobsahuje žiadne také usporiadané dvojice, teda tvrdenie platí.

[ZuzanaHromcova]

2.2.6. Nech $M, N$ sú konečné množiny, $M$ má $m$ prvkov a $N$ má $n$ prvkov. Koľko existuje zobrazení množiny $M$ do množiny $N$?

Zobrazenie každému prvku z množiny $M$ priradí práve jeden prvok z množiny $N$. Keďže ide o zobrazenie "do" množiny a nie "na" množinu, toto zobrazenie nemusí byť surjektívne, teda ľubovoľný prvok $n_0 \in M$\ môže byť priradený ľubovoľný počet krát. Pre každý prvok $m_0 \in M$ máme potom $n$ možností, ako môžeme vybrať prvok $n_0 \in N$ taký, že $f(m_0)=n_0$. Keďže prvkov $M$ je spolu $m$, dokopy máme $n.n. ... .n$, teda $n^m$ zobrazení (variácie s opakovaním $m-tej$ triedy $n$ prvkov s opakovaním).

Špeciálne prípady: ak $M=\emptyset$ a $N=\emptyset$, existuje práve jedno zobrazenie $g: M \to N, g = \emptyset$, teda v tomto prípade definujeme $0^0=1$. Ak $M=\emptyset$ a $N \neq \emptyset$, existuje práve jedno zobrazenie $g: M \to N, g = \emptyset$, čo presne zodpovedá $n^0=1$. Ak naopak $M \neq \emptyset$ a $N=\emptyset$, žiadne zobrazenie neexistuje, pretože $\exists m \in M \nexists y \in Y: \quad g(x)=y$, čo zodpovedá $0^m=0$.

JG: OK, 1 bod.

[ZuzanaHromcova]

2.2.7. Nech $A$ je konečná množina a $f: A \to A$ je zobrazenie. Dokážte:

a) Ak $f$ je injekcia, tak $f$ je bijekcia.

Nech $f$ je injekcia, potom pre $\forall x,y \in A" \quad x \neq y \Rightarrow f(x) \neq f(y)$. Pretože $f$ je zobrazenie, každému prvku z $x \in A$ priradí práve jeden prvok $y \in A$, pretože $f$ je injekcia, prvok $y$ bude pre každé $x$ iný. Pretože $A$ je konečná množina, má konečný počet prvkov, nazvime ho $m$. Každému z $m$ prvkov množiny $A$ priradí zobrazenie $f$ vždy iný prvok $y \in A$, teda obor hodnôt bude tiež $m-$ prvková množina, zároveň má byť ale podmnožinou množiny $A$, ktorá má ale tiež $m$ prvkov. Teda zobrazenie $f$ "využíva" celú množinu $A$, teda je surjektívne. Keďže je injektívne aj surjektívne, tak je bijektívne.

b) Ak $f$ je surjekcia, tak $f$ je bijekcia.

Nech $f$ je surjekcia, potom $\forall y \in A \exists x \in A: \quad f(x)=y$. Nech $A$ má $m$ prvkov (je konečná $\Rightarrow$ má konečný počet prvkov). Pre každý z $m$ prvkov množiny $A$ musí teda existovať nejaký vzor z množiny $A$. Pretože $f$ je zobrazenie, jednému vzoru nemôže byť priradených viacero obrazov, takže za týchto podmienok pre $m$ vzorov potrebujeme presne $m$ obrazov. Lenže $A$ má presne $m$ prvkov, takže každý prvok $x \in A$ sa okrem toho zobrazí vždy na iný prvok $y \in A$, teda $f$ je aj injekcia. Pretože je surjekcia aj injekcia, je to bijekcia.

JG: OK, 1 bod. Inak tento príklad je trochu zložitý v tom zmysle, že nemáte k dispozícii "matematickú" definíciu pojmu "konečná" množina. Tento dôkaz je založený na intuitívnom chápaní tohoto pojmu, ale v skutočnosti sú tieto tvrdenia "blízke" jednej z definícií pojmu konečná množina (Množina $A$ je (dedekindovsky) konečná práve vtedy, keď pre žiadnu (či lepšie každú) vlastnú podmnožinu $X\subsetneq A$ neexistuje bijekcia $f: A\to X$. ). Sú aj iné definície pojmu konečnosti (Tarského definícia, definícia pomocou bijekcie s nejakým prirodzeným číslom - tu ale treba zase poznať istú konkrétnu množinovú konštrukciu prirodzených čísiel a nejaké vlastnosti tej konštrukcie. Dôkazy ekvivalentnosti týchto definícii nie sú "náročné", ale zvyčajne vyžadujú nejakú formu axiómu výberu.)

[ZuzanaHromcova]

2.2.8. Dokážte: Zobrazenie $f: X \to Y$ je surjekcia práve vtedy, keď pre každú množinu $Z$ a všetky zobrazenia $g, h: Y \to Z$ platí $g \circ f = h \circ f \Rightarrow g = h$.

$\Leftarrow$
Nech pre každú množinu $Z$ a všetky zobrazenia $g, h: Y \to Z$ platí $g \circ f = h \circ f \Rightarrow g = h$. Ukážeme, že $f$ je surjekcia.
Triviálne prípady: ak $Y$ je prázdna množina, tak aj zobrazenie $f$ je prázdna množina a surjekcia.
Budeme vychádzať z obmenenej implikácie a dokazovať sporom. Nech $f$ nie je surjekcia, teda existuje také $c \in Y$, že $c \notin f(X)$. Zvoľme množinu $Z$ takú, že má aspoň dva prvky (označme ich $a, b ,a \neq b$) a dve zobrazenia $g, h: Y \to Z$ také, že $\forall y \in Y-\{c\}: \quad g(y)=h(y); g(c) = a, h(c) = b$. Keďže $\nexists x \in X: \quad f(x)=c$, platí $g \circ f = h \circ f$, čo je spor s predpokladom $g \neq h \Rightarrow g \circ f \neq h \circ f$. Teda také $c \in Y$ neexistuje, teda $f$ je surjekcia.
JG: Super, toto je presne "ono".

Chápem, použila som inú myšlienku, malo by to byť v poriadku.

$\Rightarrow$
Nech $f$ je surjekcia. Vezmime ľubovoľné $g, h: Y \to Z$. Ukážeme, že potom $g \circ f = h \circ f \Rightarrow g=h$.
Nech teda $g \circ f = h \circ f$, dokážeme, že pre $y\in Y$ je $g(y)=h(y)$. Keďže $f$ je surjekcia, pre každé $y \in Y \exists x \in X: \quad f(x)=y$. Nech $g \circ f = h \circ f$, potom $g(f(x))=h(f(x))$, t.j. $g(y)=h(y)$. Teda zobrazenia $g, h$ sa rovnajú v definičných oboroch, oboroch hodnôt a ich funkčné hodnoty sa rovnajú vo všetkých bodoch definičného oboru, teda $g=h$.

JG: Druhá časť je OK, trocha som zvýraznil niť dôkazu. 1 bod

[ZuzanaHromcova]

2.2.9. Dokážte: Zobrazenie $f: X \to Y$ je injekcia práve vtedy, keď pre každú množinu $Z$ a všetky zobrazenia $g,h: Z \to X$ platí: $f \circ g = f \circ h \Rightarrow g = h$.

$\Rightarrow$
Nech $f$ je injekcia, teda $\forall x_1, x_2 \in X: \quad f(x_1) = f(x_2) \Rightarrow x_1 = x_2$. Nech $f \circ g = f \circ h$, teda $\forall z \in Z: \quad f(g(z)) = f(h(z))$. Pretože $f$ je injekcia, musí z toho vyplývať $\forall z \in Z: \quad g(z) = h(z)$. Keďže $g: Z \to Y$ aj $h: Z \to Y$ a rovnajú sa vo funkčných hodnotách všetkých prvkov definičného oboru, platí $g=h$.

JG: toto je OK

$\Leftarrow$
Nech pre všetky množiny $Z$ a všetky zobrazenia $g, h: Z \to X$ platí $f \circ g = f \circ h \Rightarrow g=h$, teda $\forall z \in Z: \quad f(g(z)) = f(h(z)) \Rightarrow g(z) = h(z)$, čo je presne definícia injekcie. Teda $f$ je injekcia.

Ako tu vidím, že pre všetky $x,y\in X$ platí, že $f(x)=f(y) \Rightarrow x=y$?

[ZuzanaHromcova]

3.1.4. Na $\mathbb{R}$ definujme operáciu $x \ast y = x + y + x^2y$. Overte, že každé $x \in \mathbb{R}$ má vzhľadom na túto operáciu jediný pravý, ale existujú čísla, ktoré nemajú ľavý inverzný prvok.

Aby malo zmysel hovoriť o inverznom prvku, musíme overiť, či existuje neutrálny prvok vzhľadom na operáciu $\ast$. Hľadáme taký prvok $e \in \mathbb{R}$, pre ktorý platí $\forall x \in \mathbb{R}: \quad e \ast a = x = x \ast e$.

$e \ast x = x \Leftrightarrow e + x + e^2x = x \Leftrightarrow$ (využijeme distributívnosť operácií $+, .$ v $\mathbb{R}$) $e(1+ex) = 0$
$x \ast e = x \Leftrightarrow x + e + x^2e = x \Leftrightarrow$ (distributívnosť) $e(1+x^2) = 0$
Toto platí súčasne vtedy a len vtedy, keď $e=0$.

JG: OK

Neutrálny prvok existuje, teda má zmysel uvažovať o inverznom prvku. Dokážeme, že pre všetky $x \in \mathbb{R}$ existuje pravý inverzný prvok $z_x$:
$x \ast z_x = e \Leftrightarrow x + z_x + x^2z_x = 0 \Leftrightarrow$ (distributívnosť) $z_x(1+x^2) = -x \Leftrightarrow z_x = - \frac{x}{1+x^2}$. Keďže menovateľ tohto zlomku nikdy nenadobúda nulovú hodnotu, existuje pravý inverzný prvok pre každý prvok $x \in \mathbb{R}$. Tento prvok je zároveň jediný, pretože je jednoznačne určený.

JG: OK

Teraz ukážeme, že pre niektoré prvky $x \in \mathbb{R}$ neexistuje ľavý inverzný prvok, označme hľadaný ľavý inverzný prvok $l$. Pre každé $x\in \mathbb{R}$ má platiť $l \ast x = e \Leftrightarrow l + x + l^2x = 0 \Leftrightarrow l^2x + l + x = 0 \Leftrightarrow D = (1+2x)(1-2x) \geq 0$. To ale neplatí napríklad pre $x = -1$, kedy $D=-3$.

JG: Myslíte to dobre, ale niečo tu treba opraviť.
Opravila som zápis toho ľavého inverzného prvku, dúfam, že teraz je to už v poriadku.
JG: asi ešte treba povedať, čo vlastne robíte, čo je $D$ a prečo o ňom vlastne hovoríte. Nie som si istý, že to takto všetci bez vysvetlenia pochopia. 1 bod (verím, že mne by Ste to už vedeli vysvetliť)