Ak $g\circ f$ je injekcia, musí byť aj $g$ injekcia?

[Martin Sleziak]

Príklad z písomky na výberovom cviku bol:

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.

Odpoveď je, že tvrdenie neplatí. Kontrapríklad nie je príliš ťažké nájsť. Uvedomme si najprv čo vlastne hľadáme. Pýtame sa, či vieme nájsť kontrapríklad k implikácii: $g\circ f$ je injekcia $\Rightarrow$ $g$ je injekcia.
Teda chceme nájsť príklad zobrazení takých, že $g$ je injekcia, ale $g\circ f$ nie je injekcia. (Implikácia je nepravdivá iba v prípade $1\Rightarrow0$, t.j. ak predpoklady implikácie sú splnené, ale neplatí tvrdenie na pravej strane implikácie.)

Chceme teda, aby $g$ nebolo injektívne, čiže potrebujeme, aby $g$ zobrazovalo dva rôzne prvky na ten istý prvok. Najjednoduchšie také zobrazenie dostaneme tak, že zobrazíme dvojprvkovú množinu na jednoprvkovú.
Teraz chceme vymyslieť $f$ tak, aby zloženie $g\circ f$ bolo injektívne. Opäť, keď skúsime čo najjednoduchší možný prípad, tak to vyjde.

Teda náš kontrapríklad môžeme zapísať takto:
$X=\{0\}$, $Y=\{0,1\}$, $Z=\{0\}$;
$f\colon X\to Y$ je definované ako $f(0)=0$;
$g\colon Y\to Z$ je definované ako $g(0)=g(1)=0$.

[Martin Sleziak]

Skúsim sem napísať niečo k chybám a problémom, ktoré sa vyskytovali v odovzdaných riešeniach. (Niektoré častejšie, niektoré menej často.)

Bodovanie

Úlohu som bodoval pomerne benevolentne. 2 body som dával za správnu definíciu injekcie. 3 body boli za druhú časť. (T.j. za nájdenie kontrapríkladu.) Aj ak ste druhú časť nemali správne, ale boli tam aspoň nejaké zmysluplné veci, dal som nejaké body.

Obmenená implikácia

Pod obmenou implikácie sa myslí to, že výrok $P\Rightarrow Q$ nahradíme ekvivalentným výrokom $\neg Q \Rightarrow \neg P$.

Teda podmienku z definície injekcie
$f(x_1)=f(x_2)$ $\Rightarrow$ $x_1=x_2$
môžeme ekvivalentne prepísať ako
$x_1 \ne x_2$ $\Rightarrow$ $f(x_1)\ne f(x_2)$
Nie je to (ako ste niektorí tvrdili) ekvivalentné podmienke:
$f(x_1) \ne f(x_2)$ $\Rightarrow$ $x_1 \ne x_2$
Ak si to rozmyslíte, zistíte, že táto podmienka je splnená pre každé zobrazenie. (Ekvivalentne ju môžeme prepísať ako: $x_1 = x_2$ $\Rightarrow$ $f(x_1) = f(x_2)$.)

Negácia implikácie
Platí $\neg(P\Rightarrow Q) \Leftrightarrow P \land \neg Q$.
(Implikácia $P\Rightarrow Q$ je nepravdivá iba v prípade, že $P$ je pravdivé a $Q$ je nepravdivé.)
Čo teda dostaneme, keď chceme zapísať, že $f$ nie je injekcia?
T.j. chceme znegovať výrok $(\forall x_1, x_2\in X) f(x_1)=f(x_2) \Rightarrow x_1=x_2$.
Pri negáciu výroku sa zmení $\forall$ na $\exists$ a potom ešte treba znegovať výrok pod kvantifikátorom. Dostaneme teda
$(\exists x_1, x_2 \in X) f(x_1)=f(x_2) \land x_1 \ne x_2$.
(To je presne to, čo by sme očakávali; $f$ nie je injekcia znamená presne existenciu dvoch rôznych bodov $x_1\ne x_2$, ktoré sa zobrazia na ten istý prvok $f(x_1)=f(x_2)$.)

Zobrazenie nemusí byť vždy buď injekcia alebo surjekcia
V jednej písomke sa objavilo:

Tvrdenie neplatí, $g$ môže byť aj surjekcia.

To, že $g$ je surjekcia nijako nevylučuje, že to nemôže byť injekcia.
Existujú zobrazenia, ktoré sú surjekcie aj injekcie. (To sú presne bijektívne zobrazenia.)
Existujú zobrazenia, ktoré sú surjekcie ale nie sú injekcie.
Existujú zobrazenia, ktoré sú injekcie ale nie sú surjekcie.
Existujú zobrazenia, ktoré sú ani surjekcie ani injekcie.
(Ak máte stále problémy s pojmami surjektívne a injektívne zobrazenie, tak sa oplatí skúsiť sa zamyslieť, či by ste vedeli nájsť príklady takých zobrazení.)

K zápisom
Okrem toho, že by ste mali porozumieť veciam, ktoré sa učíte, by bolo dobré naučiť sa aj správnym spôsobom ich zapisovať.
Symbol $\circ$ označuje skladanie zobrazení, môžeme ho zapísať medzi dve zobrazenia.
Teda napríklad zápisy $g(f(x))$ alebo $g\circ f(x)$ majú zmysel. (V druhom prípade môžeme ešte pridať zátvorku $(g\circ f)(x)$, ak chceme zdôrazniť, že $g\circ f$ je zobrazenie, do ktorého dosadzujeme $x$.)
Zápis $g(x)\circ f(x)$ je nesprávny. (S výnimkou prípadu, že by $g(x)$ aj $f(x)$ boli zobrazenia, teda $g$ a $f$ by museli byť zobrazenia do nejakej množiny zobrazení. Občas sa také prípady vyskytnú, ale toto nebol taký prípad.)

Iné zadanie: Viacero ľudí uviedlo dôkaz toho, že ak $g\circ f$ je injekcia, tak $f$ je injekcia. Toto tvrdenie je pravdivé a som rád, že ste zvládli jeho dôkaz, ale to nie je to, na čo som sa v zadaní pýtal.

Prečo nefunguje takýto argument?
Vo viacerých písomkách sa objavil nejaký zhruba takýto zápis:
$g(\underset{y_1}{\underbrace{f(x_1)}})=g(\underset{y_2}{\underbrace{f(x_2)}}) \Rightarrow x_1=x_2 \Rightarrow f(x_1)=f(x_2)$
$g(y_1)=g(y_2) \Rightarrow y_1=y_2$
Čo mal byť zrejme pokus o dôkaz, že zadané tvrdenie platí. Už sme videli kontrapríklad, takže tvrdenie asi neplatí. V čom je problém s uvedeným pokusom o dôkaz?
Prvý riadok skutočne platí: Prvá časť je iba zápis toho, že $g\circ f$ je injekcia. A ak $x_1=x_2$, tak naozaj aj $f(x_1)=f(x_2)$. (To vyplýva z definície zobrazenia.)
Takisto nie je nič zlé na tom, aby sme si označili $f(x_1)$ ako $y_1$ a $f(x_2)$ ako $y_2$.
Problém je v tom, že tým sme zdôvodnili implikáciu $g(y_1)=g(y_2) \Rightarrow y_1=y_2$ iba pre tie $y_{1,2}$, ktoré sa dajú dostať ako obrazy prvkov z $X$. (Lebo sme použili $y_i=f(x_i)$.) Ak by sme chceli dokázať, že $g$ je injektívne, musíme to overiť pre všetky $y_{1,2}$,

Teda takýmto spôsobom by sa dalo dokázať, že $g$ je injekcia, ak by sme navyše v zadaní mali, že $f$ je aj surjekcia.
(V takom prípade by sme to vedeli dokázať aj inak - s použitím vecí, ktoré sme dokazovali už predtým. Ak by sme vedeli, že $f$ je injekcia aj surjekcia, tak $f$ je bijekcia a existuje k nemu inverzné zobrazenie. Potom $g=(g\circ f)\circ f^{-1}$ je zloženie dvoch injekcií a je to injekcia.)