Úloha 2.2.4. - Injekcia, surjekcia, ľavé, pravé inverzné zobrazenia

[MichaelRuman]

Nech $f: X \to Y$ je zobrazenie a $X \not= \emptyset$ (t.j. $X$ je neprázdna množina). Potom:
a) $f$ je injekcia práve vtedy, keď existuje $g$ také, že $g \circ f = id_X$.
b) $f$ je surjekcia práve vtedy, keď existuje $h$ také, že $f \circ h = id_Y$.
c) K zobrazeniu $f$ existuje inverzné zobrazenie práve vtedy, keď $f$ je bijekcia.

a) $f$ je injekcia práve vtedy, keď existuje $g$ také, že $g \circ f = id_X$.
Dokážeme ekvivalentné tvrdenie:
$(i.)$ Ak $f$ je injekcia, existuje $g$ také, že $g \circ f = id_X$
a zároveň
$(ii.)$ Ak $f$ nie je injekcia, potom pre všetky $g$ platí, $g \circ f \not= id_X$.

$Dôkaz.$
$(i.)$ Ak $f$ je injekcia, existuje $g$ také, že $g \circ f = id_X$.
Nájdeme $g$ také, že $g \circ f = id_X$. Nech $f: X \to Y$ je injekcia a

$(I.)$ ${Z \subseteq Y: Z = \{f(x) | x \in X\}}$.
Teda $Z$ je množina prvkov, na ktoré sa cez $f$ zobrazia prvky $X$.

Definujme

$(II.)$ $g(z) = x$, kde $z = f(x)$ pre všetky $z \in Z$

Z definície injekcie vieme, že do každého $z \in Z$ sa cez $f$ zobrazí práve jedno $x$ a teda $g$ je jednoznačne definované na $Z$.
Ďalej definujme

$g(y) = a$ pre všetky $y \in Y \setminus Z$, kde $a$ je ľubovoľný prvok $X$. Axióma výberu zaručuje, že taký prvok môžeme vybrať.

Teda $g$ je jednoznačne definované aj na $Y \setminus Z$ a teda $g: Y \to X$ je zobrazenie. Zároveň z $(I.)$ a $(II.)$ vyplýva:

$(\forall x \in X, f(x) \in Z)$ čiže $(\forall x \in X, g(f(x)) = x)$

Čiže ak $f$ je injekcia, $g \circ f = id_X$.


$(ii.)$ Ak $f$ nie je injekcia, potom pre všetky $g$ platí, $g \circ f \not= id_X)$. Sporom. Nech $f$ nie je injekcia. Nech $x_1, x_2 \in X$ a $ x_1 \not= x_2$ a $f(x_1) = f(x_2)$. Keďže $f$ nie je injekcia, takéto prvky existujú.
Nech existuje zobrazenie $g: Y \to X$ také, že $g \circ f = id_X$. Teda

$\forall x \in X: g(f(x)) = x$.

Potom

$g(f(x_1)) = x_1$

a zároveň

$g(f(x_1)) = g(f(x_2)) = x_2$,

čo je spor s predpokladom, že $g$ je identické zobrazenie, nakoľko $x_1 \not= x_2$.

Teda ak $f$ je injekcia, neexistuje $g$ také, že $g \circ f = id_X$


b) $f$ je surjekcia práve vtedy, keď existuje $h$ také, že $f \circ h = id_Y$.
Opäť dokážeme ekvivalentné tvrdenie:
$(iii.)$ Ak $f$ je surjekcia, existuje $h$ také, že $f \circ h = id_Y$
a zároveň
$(iv.)$ Ak $f$ nie je surjekcia, potom pre všetky $h$ platí, $f \circ h \not= id_Y)$.

$Dôkaz.$
$(iii.)$ Ak $f$ je surjekcia, existuje $h$ také, že $f \circ h = id_Y$.
Nájdeme $h$ také, že $f \circ h = id_Y$. Nech $f$ je surjekcia. Pre každé $y \in Y$ definujme

$W_y = \{x | f(x) = y\}$.
Teda $W_y$ je množina prvkov $X$, ktoré sa cez $f$ zobrazia do daného $y$. Keďže $f$ je surjekcia, pre každé $y \in Y$ existuje aspoň jedno $x \in X$ také, že $f(x) = y$ a teda pre každé $y \in Y, W_y \not= \emptyset$.

Definujme

$h(y) = b_y$, pre všetky $y \in Y$, kde $b_y$ je ľubovoľný jeden prvok $W_y$ a teda $f(b_y) = y$. Axióma výberu zaručuje, že taký prvok môžeme vybrať.

Keďže $W_y$ je neprázdne pre všetky $y \in Y$, zobrazenie $h: Y \to X$ je jednoznačne definované na $Y$. Zároveň
$\forall y \in Y, f(h(y)) = f(b_y) = y$.

Čiže ak $f$ je surjekcia, $f \circ h = id_Y$.


$(iv.)$ Ak $f$ nie je surjekcia, potom pre všetky $h$ platí, $f \circ h \not= id_Y$.
Nech $f$ nie je surjekcia a $y_1 \in Y$ je také, že $\forall x \in X, f(x) \not= y_1$. Keďže $f$ nie je surjekcia, takéto $y_1$ existuje.

Teda pre ľubovoľné $h: Y \to X$ a $y_1, h(y_1) \in X$, čiže $f(h(y_1)) \not= y_1$.

Čiže ak $f$ nie je surjekcia, tak pre ľubovoľné $h$ platí $f \circ h \not= id_Y$.


c) K zobrazeniu $f$ existuje inverzné zobrazenie práve vtedy, keď $f$ je bijekcia.
$Dôkaz.$
Dokážeme implikácie oboma smermi.
${\Rightarrow}:$
Ak k $f$ existuje inverzné zobrazenie, $f$ je bijekcia.
Nech $f^{-1}: Y \to X$ je inverzné zobrazenie k $f$. Potom $f^{-1} \circ f = id_X$ a teda podľa a) $f$ je injekcia.
Zároveň $f \circ f^{-1} = id_Y$ a teda podľa b) je $f$ surjekcia. Nakoľko $f$ je injekcia aj surjekcia, $f$ je bijekcia,

Čiže ak k $f$ existuje inverzné zobrazenie, $f$ je bijekcia.


$\Leftarrow:$
Nech $f$ je bijekcia a $g$ je zobrazenie definované v $(ii.)$. Nakoľko $f$ je surjektívne, $Z = Y$ a teda pre všetky $x$ platí, $g(f(x)) = x$ a pre všetky $y$ sa dá $f(g(y))$ zapísať ako $f(g(f(x)))$ pre nejaké $x$. Potom z definície $g$, platí $f(g(f(x))) = f(x) = y$. Teda $g \circ f = id_X$ a $f \circ g = id_Y$ čiže $g$ je inverzné zobrazenie k $f$.

Čiže ak $f$ je bijekcia, existuje k nej inverzné zobrazenie.

$Pozn.$ Časť c) bola samostatne dokázaná aj v skriptách a implikácia sprava bola dokázaná prakticky totožným spôsobom.

[makovnik]

Nech $f: X \to Y$ je zobrazenie a $X \not= \emptyset$ (t.j. $X$ je neprázdna množina). Potom:
a) $f$ je injekcia práve vtedy, keď existuje $g$ také, že $g \circ f = id_X$.
b) $f$ je surjekcia práve vtedy, keď existuje $h$ také, že $f \circ h = id_Y$.
c) K zobrazeniu $f$ existuje inverzné zobrazenie práve vtedy, keď $f$ je bijekcia.

a) $f$ je injekcia práve vtedy, keď existuje $g$ také, že $g \circ f = id_X$.
Dokážeme ekvivalentné tvrdenie:
$(i.)$ Ak $f$ je injekcia, existuje $g$ také, že $g \circ f = id_X$
a zároveň
$(ii.)$ Ak $f$ nie je injekcia, potom pre všetky $g$ platí, $g \circ f \not= id_X$.

$Dôkaz.$
$(i.)$ Ak $f$ je injekcia, existuje $g$ také, že $g \circ f = id_X$.
Nájdeme $g$ také, že $g \circ f = id_X$. Nech $f: X \to Y$ je injekcia a

$(I.)$ ${Z \subseteq Y: Z = \{f(x) | x \in X\}}$.
Teda $Z$ je množina prvkov, na ktoré sa cez $f$ zobrazia prvky $X$.

Definujme

$(II.)$ $g(z) = x$, kde $z = f(x)$ pre všetky $z \in Z$

Z definície injekcie vieme, že do každého $z \in Z$ sa cez $f$ zobrazí práve jedno $x$ a teda $g$ je jednoznačne definované na $Z$.
Ďalej definujme

$g(y) = a$ pre všetky $y \in Y \setminus Z$, kde $a$ je ľubovoľný prvok $X$. Axióma výberu zaručuje, že taký prvok môžeme vybrať.

Teda $g$ je jednoznačne definované aj na $Y \setminus Z$ a teda $g: Y \to X$ je zobrazenie. Zároveň z $(I.)$ a $(II.)$ vyplýva:

$(\forall x \in X, f(x) \in Z)$ čiže $(\forall x \in X, g(f(x)) = x)$

Čiže ak $f$ je injekcia, $g \circ f = id_X$.

MM: Toto by bolo asi trochu zrozumiteľnejšie (a asi aj jednoduchšie a bez opakovania) sformulovať nasledovne:
Nech $ g: Y \to X $ je zobrazenie definované tak, že
$ g(z) = x $ pre všetky $ z \in Z $ a
$ g(y) = a $ pre $ y \in Y \setminus Z $ a ľubovoľne zvolené $ a \in X $.
Potom z $ (I) $ a $ (II) $ vyplýva, že pre ľubovoľné $ x \in X $ máme $ g(f(x)) = x $, čo sme potrebovali ukázať.

$(ii.)$ Ak $f$ nie je injekcia, potom pre všetky $g$ platí, $g \circ f \not= id_X)$. Sporom. Nech $f$ nie je injekcia. Nech $x_1, x_2 \in X$ a $ x_1 \not= x_2$ a $f(x_1) = f(x_2)$. Keďže $f$ nie je injekcia, takéto prvky existujú.
Nech existuje zobrazenie $g: Y \to X$ také, že $g \circ f = id_X$. Teda

$\forall x \in X: g(f(x)) = x$.

Potom

$g(f(x_1)) = x_1$

a zároveň

$g(f(x_1)) = g(f(x_2)) = x_2$,

čo je spor s predpokladom, že $g$ je identické zobrazenie, nakoľko $x_1 \not= x_2$.
MM: čo je spor s predpokladom, že $g$ je zobrazenie, nakoľko $x_1 \not= x_2$.
$g$ nie je identita.

Teda ak $f$ je injekcia, neexistuje $g$ také, že $g \circ f = id_X$

MM: Opäť, možno to preformulovať o čosi zreteľnejšie:
Platnosť tejto časti ukážeme sporom. Predpokladajme teda, že $ f $ nie je injekcia a existuje zobrazenie $ g: Y \to X $ také, že $g \circ f = id_X$.
Z prvého predpokladu máme zabezpečené, že existujú $ x_1, x_2 \in X $ také, že $ x_1 \neq x_2 $ a $ f(x_1) = f(x_2) $ (A).
Druhý predpoklad nám dáva, že $g(f(x_1)) = x_1$ a $g(f(x_2)) = x_2 $ (B).
Avšak, z (A) dostávame, že $g(f(x_1)) = g(f(x_2)) $, čo spolu s (B) implikuje, že $ x_1 = x_2 $, čo je spor s predpokladom, že $ x_1 \neq x_2 $.


b) $f$ je surjekcia práve vtedy, keď existuje $h$ také, že $f \circ h = id_Y$.
Opäť dokážeme ekvivalentné tvrdenie:
$(iii.)$ Ak $f$ je surjekcia, existuje $h$ také, že $f \circ h = id_Y$
a zároveň
$(iv.)$ Ak $f$ nie je surjekcia, potom pre všetky $h$ platí, $f \circ h \not= id_Y)$.

$Dôkaz.$
$(iii.)$ Ak $f$ je surjekcia, existuje $h$ také, že $f \circ h = id_Y$.
Nájdeme $h$ také, že $f \circ h = id_Y$. Nech $f$ je surjekcia. Pre každé $y \in Y$ definujme
MM: Predpokladajme, že $f$ je surjekcia. Pre každé $y \in Y$ definujme ...

$W_y = \{x | f(x) = y\}$.
Teda $W_y$ je množina prvkov $X$, ktoré sa cez $f$ zobrazia do daného $y$. Keďže $f$ je surjekcia, pre každé $y \in Y$ existuje aspoň jedno $x \in X$ také, že $f(x) = y$ a teda pre každé $y \in Y, W_y \not= \emptyset$.

Definujme

$h(y) = b_y$, pre všetky $y \in Y$, kde $b_y$ je ľubovoľný jeden prvok $W_y$ a teda $f(b_y) = y$. Axióma výberu zaručuje, že taký prvok môžeme vybrať.
MM: Definujme zobrazenie $ h: Y \to X $ tak, že $h(y) = b_y$, kde $ b_y \in W_y $.

Keďže $W_y$ je neprázdne pre všetky $y \in Y$, zobrazenie $h: Y \to X$ je jednoznačne definované na $Y$. Zároveň
$\forall y \in Y, f(h(y)) = f(b_y) = y$.

Čiže ak $f$ je surjekcia, $f \circ h = id_Y$.




$(iv.)$ Ak $f$ nie je surjekcia, potom pre všetky $h$ platí, $f \circ h \not= id_Y$.

Nech $f$ nie je surjekcia a $y_1 \in Y$ je také, že $\forall x \in X, f(x) \not= y_1$. Keďže $f$ nie je surjekcia, takéto $y_1$ existuje.

Teda pre ľubovoľné $h: Y \to X$ a $y_1, h(y_1) \in X$, čiže $f(h(y_1)) \not= y_1$.

MM: Nech $f$ nie je surjekcia. Potom, existuje $y_1 \in Y$ je také, že $\forall x \in X, f(x) \not= y_1$.
Následne pre ľubovoľné zobrazenie $h: Y \to X$ je zrejme $h(y_1) \in X$, a teda $f(h(y_1)) \not= y_1$.

Čiže ak $f$ nie je surjekcia, tak pre ľubovoľné $h$ platí $f \circ h \not= id_Y$.


c) K zobrazeniu $f$ existuje inverzné zobrazenie práve vtedy, keď $f$ je bijekcia.
$Dôkaz.$
Dokážeme implikácie oboma smermi.
${\Rightarrow}:$
Ak k $f$ existuje inverzné zobrazenie, $f$ je bijekcia.
Nech $f^{-1}: Y \to X$ je inverzné zobrazenie k $f$. Potom $f^{-1} \circ f = id_X$ a teda podľa a) $f$ je injekcia.
Zároveň $f \circ f^{-1} = id_Y$ a teda podľa b) je $f$ surjekcia. Nakoľko $f$ je injekcia aj surjekcia, $f$ je bijekcia,

Čiže ak k $f$ existuje inverzné zobrazenie, $f$ je bijekcia.


$\Leftarrow:$
Nech $f$ je bijekcia a $g$ je zobrazenie definované v $(ii.)$. Nakoľko $f$ je surjektívne, $Z = Y$ a teda pre všetky $x$ platí, $g(f(x)) = x$ a pre všetky $y$ sa dá $f(g(y))$ zapísať ako $f(g(f(x)))$ pre nejaké $x$. Potom z definície $g$, platí $f(g(f(x))) = f(x) = y$. Teda $g \circ f = id_X$ a $f \circ g = id_Y$ čiže $g$ je inverzné zobrazenie k $f$.

Čiže ak $f$ je bijekcia, existuje k nej inverzné zobrazenie.

$Pozn.$ Časť c) bola samostatne dokázaná aj v skriptách a implikácia sprava bola dokázaná prakticky totožným spôsobom.
MM: K tejto časti nemám v zásade výhrady (ak nerátam pravopis).

MM: Celkovo asi hlavný problém tohto riešenia bolo, že ste opakovali predpoklady, alebo jednotlivé kroky niekedy aj v dvoch vetách za sebou. To poznateľne sťažuje čítanie dôkazu. Taktiež, dokazovať nejakú implikáciu tak, že sporom dokážete jej obmenu, je síce korektné, ale nie úplne elegantné Každopádne jedná sa o chyby, ktoré sa dajú eliminovať praxou, a preto za riešenie udeľujem 2 body.