Injekcie a skladanie

[Martin Sleziak]

Úloha z písomky:

a) Napíšte definíciu injektívneho zobrazenia.
b) Platí nasledujúce tvrdenie? Ak áno, dokážte ho, ak nie, nájdite kontrapríklad: Ak $f\colon X\to Y$ a $g\colon Y\to Z$ sú zobrazenia také, že $g\circ f$ je injekcia, tak $g$ je injekcia.

Definícia injektívneho zobrazenia

Zobrazenie $f\colon X\to Y$ je injektívne, ak platí
$$(\forall x_{1,2}\in X) f(x_1)=f(x_2) \Rightarrow x_1=x_2.$$
Túto definíciu môžeme ekvivalentne zapísať (obmena implikácie):
$$(\forall x_{1,2}\in X) x_1 \ne x_2 \Rightarrow f(x_1) \ne f(x_2).$$

V niektorých písomkách ste tvrdili, že definícia injekcie je
$$(\forall x_{1,2}\in X) f(x_1) \ne f(x_2) \Rightarrow x_1 \ne x_2.$$
Toto nie je správna definícia. Môžeme si však rozmyslieť, čo táto vlastnosť hovorí. Možno sa oplatí pozrieť na obmenenú implikáciu:
$$(\forall x_{1,2}\in X) x_1=x_2 \Rightarrow f(x_1)=f(x_2).$$
Keď ju máme zapísanú takto, tak vidíme, že táto vlastnosť platí pre každé zobrazenie. Hovorí to presne to, že ku každému prvku z $X$ máme práve jeden obraz. (Jeden prvok sa nemôže zobraziť na dve rozličné veci.)

Kontrapríklad

V druhej časti som sa pýtal na platnosť tvrdenia:

Ak $f\colon X\to Y$ a $g\colon Y\to Z$ sú zobrazenia také, že $g\circ f$ je injekcia, tak $g$ je injekcia.

Toto tvrdenie neplatí. Azda najjednoduchší kontrapríklad vyzerá takto:

Vidíme, že $g\circ f$ je injekcia. Ale zobrazenie $g$ nie je injektívne.

Niekto navrhol takýto kontrapríklad:
$g \colon \mathbb R \to \mathbb R^+$; $g(x)=x^2$
$f \colon \mathbb R^+ \to \mathbb R$; $f(x)=\sqrt{x}$
Symbol $\mathbb R^+$ označuje množinu reálnych čísel.

Toto je tiež správny kontrapríklad.

Ak sa pozrieme na zložené zobrazenie, tak $g\circ f(x)=\sqrt{x^2}=x$, čiže je to identické zobrazenie na množine $\mathbb R^+$, ktoré je skutočne injektívne.
(Pre istotu upozorním, že rovnosť $\sqrt{x^2}=x$ sme mohli napísať vďaka tomu, že $x\ge0$. Vo všeobecnosti pre reálne čísla vieme iba $\sqrt{x^2}=|x|$.)
Zobrazenie $g$ však nie je injektívne, lebo napríklad $g(1)=g(-1)=1$.

[Martin Sleziak]

K definícii injektívneho zobrazenia

Odpíšem niektoré veci, ktoré ste napísali v písomkách ako definíciu injektívneho zobrazenia, aby som ich mohol okomentovať a vysvetliť v čom je problém.

Injektívne (prosté) zobrazenia $A\to B$ = ak máme dve množiny $A$ a $B$, potom každý prvok z množiny $A$ sa zobrazí v množine $B$ práve do jedného prvku a nemôže sa zobraziť do viacerých alebo do žiadneho.
*
Injektívne zobrazenie je zobrazenie, pre ktoré platí, že pre každé $x$ z východiskovej množiny $X$ existuje $y$ z cieľovej množiny $Y$.

Niečo takéto ako ste napísali tu sa skôr podobá na definíciu zobrazenia než na definíciu injekcie.
Definícia zobrazenia hovorí o tom, že ku každému $x\in X$ mám priradené práve jedno $y\in Y$.
Injektívnosť je niečo iné. To je zobrazenie kde pre ľubovoľný prvok $y$ z $Y$ máme najviac jeden vzor. (T.j. môže sa naň zobraziť najviac jeden prvok.)

Ak $f\colon X\to Y$ je injekcia, tak musí platiť $|X|\le|Y|$. (Aspoň pre konečné množiny, pričom $|X|$ označujeme počet prvkov - neskôr na diskrétnej matematike poriadne zadefinujete aký je význam symbolu $|X|$ ak množina $X$ je nekonečné.)
Obrátene to platiť nemusí, t.j. môže to byť tak že počet prvkov $X$ je menší ako počet prvkov $Y$ a zobrazenie z $X$ do $Y$ nie je injektívne. (Spomínam to opäť iba preto, že v niektorých písomkách bolo - pomerne nejasne - napísané niečo čo znelo ako keby toto bola definícia injekcie alebo prinajmenšom súčasť definície.)

Aký kontrapríklad hľadáme

Hľadáme kontrapríklad k tvrdeniu: $g\circ f$ je injektívne $\Rightarrow$ $g$ je injektívne.
Implikácia je nepravdivá iba v tomto prípade: $1\Rightarrow0$.
Teda chceme nájsť príklad zobrazení takých, že $g\circ f$ je injektívne a $g$ nie je injektívne. (Spomínam to preto, že sa našli písomky, kde ste to robili presne naopak.)

Chybné dôkazy

V niektorých písomkách sa vyskytlo niečo, čo vyzeralo zhruba takto.

Vieme, že $g\circ f$ je injektívne, teda že platí (pre ľubovoľné $x_{1,2}\in X$)
$$g(f(x_1))=g(f(x_2)) \Rightarrow x_1 = x_2.\tag{1}$$
Chceme dokázať (pre ľubovoľné $y_{1,2}\in Y$)
$$g(y_1)=g(y_2) \Rightarrow y_1=y_2.\tag{2}$$
Stačí ak položíme $y_1=f(x_1)$, $y_2=f(x_2)$ a dostávame, že platí $(2)$.

Toto nie je správny dôkaz. Dokázali ste takto implikáciu $(2)$ iba pre tie body z $Y$ na ktoré sa niečo zobrazí. Nie však pre všetky $y_{1,2}\in Y$.
Z kontrapríkladu, ktorý sme uviedli vyššie, azda vidno že takéto niečo nemusí platiť.
Ak by sme navyše pridali predpoklad, že $f$ je surjekcia, tak by sme už vedeli takýmto spôsobom dokázať že $g$ musí byť injektívne.