Úloha 1.3: Ak $g\circ f$ je injekcia, tak $f$ je injekcia - Riešenie

[FilipJurcak]

Úloha 1.3 Dokážte: Ak $g \circ f$ je injekcia, tak $f$ je injekcia. Platí aj opačná implikácia? Musí $g$ byť injekcia?

Ak $g \circ f$ je injekcia, tak $f$ je injekcia.
Nech $f: X \to Y, g: Y \to Z$. Z definície injekcie ak $g(f(x_1)) = g(f(x_2))$ potom $x_1 = x_2$. Ak $f(x_1) = f(x_2)$, potom platí aj $g(f(x_1)) = g(f(x_2))$, pretože $g$ je zobrazenie a teda jednému vzoru priradí práve jeden obraz. A keďže vieme že $g(f(x_1)) = g(f(x_2)) \Rightarrow x_1 = x_2$ a $f(x_1) = f(x_2) \Rightarrow g(f(x_1)) = g(f(x_2))$, musí byť $f$ injekcia.

Kontrapríklad ($f$ je injekcia, $g$ nemusí byť injekcia, a $g \circ f$ je aj tak injekcia):
$$f: X \to \mathbb{N}, f(x) = x + 1, X = \{x \mid x \in \mathbb{N} \wedge x < 100\}$$
$$g: \mathbb{N} \to \mathbb{N}, g(x) = \begin{cases} x + 1& \quad \text{ ak x < 102, } \\ 103 \quad \text {inak.} \end{cases}$$
Teda $g$ nie je injekcia, $f$ je injekcia, a $g \circ f$ je injekcia, pretože $\forall x,y \in X, x \neq y \Rightarrow g(f(x)) \neq g(f(y))$.

Platí aj opačná implikácia?
Opačná implikácia v obecnom prípade neplatí, čo môžme vidieť ak vyberieme za $f = id_\mathbb{N}$ a za $g = x^2$, pretože ak by to bola injekcia, muselo by platiť že ak $g(f(x_1)) = g(f(x_2))$ tak potom $x_1 = x_2$, čo v tomto prípade neplatí, pretože síce sa $g(f(x_1)) = g(f(x_2))$, napr. pre -1 a 1, ale -1 $\neq$ 1.

Musí $g$ byť injekcia?
Ak by ale $g$ bola injekcia, opačná implikácia by platila, pretože zloženie dvoch injekcií je injekcia, čo môžeme ľahko dokázať- ak $g: Y \to Z, f: X \to Y$ sú injekcie a $x,y \in X$ majú tú vlastnosť, že $(g \circ f)(x) = (g \circ f)(y)$. Poslednú rovnosť vieme prepísať na $g(f(x)) = g(f(y))$. Pretože $g$ je injekcia, musí platiť že $f(x) = f(y)$, a pretože je f tiež injekcia, musí platiť že $x = y$.

[Martin Sleziak]

Azda až tak veľa neprezradím, keď poviem, že $g$ vo všeobecnosti nemusí byť injekcia.
Čiže možno sa oplatí zamyslieť nad tým čo ste napísali (keďže vy tvrdíte že to bude injekcia) prečo váš argument nebude fungovať.
Prípadne by vám mohlo pomôcť ak skúsite nájsť kontrapríklad.

V podstate toto (možno trochu jasnejšie napísané) by stačilo ako argument prečo $f$ je injekcia:

No a podobne budeme argumentovať pri $f$, teda aby platilo že ak $g(f(x_1)) = g(f(x_2))$ potom $x_1 = x_2$ musí platiť aj $x_1 = x_2$ ak $f(x_1) = f(x_2)$, čiže $f$ je injekcia.

Ak mám $f(x_1)=f(x_2)$, tak platí aj $g(f(x_1))=g(f(x_2))$. A teraz už z toho, že $g\circ f$ je injekcia vidím, že platí aj $x_1=x_2$.
(Tu sme nijako nevyužívali či $g$ je alebo nie je injekcia. Stačilo nám, že $g$ je zobrazenie - to sme využili vo forme implikácie $f(x_1)=f(x_2)$ $\Rightarrow$ $g(f(x_1))=g(f(x_2))$)

Kontrapríklad na implikáciu opačným smerom je v poriadku.

Skúste sa teda ešte zamyslieť nad tým, že $g$ injekcia nemusí byť.
A ak na kontrapríklad nebudete vedieť prísť, tak sem explicitne napíšte, že necháte úlohu doriešiť vašim kolegom. (S tým, že body by som nejako medzi vás rozdelil.)

[FilipJurcak]

Opravil som a doplnil kontrapríklad

[Martin Sleziak]

V podstate ok - dá sa z tohoto už vyčítať celé riešenie a značím si 1 bod.

Stále mám nejaké pripomienky/komentáre:

Platí aj opačná implikácia?
Opačná implikácia v obecnom prípade neplatí, čo môžme vidieť ak vyberieme za $f = id_\mathbb{N}$ a za $g = x^2$, pretože ak by to bola injekcia, muselo by platiť že ak $g(f(x_1)) = g(f(x_2))$ tak potom $x_1 = x_2$, čo v tomto prípade neplatí, pretože síce sa $g(f(x_1)) = g(f(x_2))$, napr. pre -1 a 1, ale -1 $\neq$ 1.

Možno s kontextu je to trochu aj zrejmé, ale bolo by treba povedať aj odkiaľ kam idú zobrazenia $f$ a $g$.

Tu vlastne robíte niečo čo ste už predtým spravili.

Musí $g$ byť injekcia?
Ak by ale $g$ bola injekcia, opačná implikácia by platila, pretože zloženie dvoch injekcií je injekcia, čo môžeme ľahko dokázať- ak $g: Y \to Z, f: X \to Y$ sú injekcie a $x,y \in X$ majú tú vlastnosť, že $(g \circ f)(x) = (g \circ f)(y)$. Poslednú rovnosť vieme prepísať na $g(f(x)) = g(f(y))$. Pretože $g$ je injekcia, musí platiť že $f(x) = f(y)$, a pretože je f tiež injekcia, musí platiť že $x = y$.

Ale stále je to užitočné pozorovanie - ak by takáto implikácia platila, tak platí aj implikácia na ktorú už máte kontrapíklad.
Čiže inač povedané, spravili ste vlastne na obe veci po dva kontrapríklady.

Linky na staršie posty s podobnou témou:
viewtopic.php?t=493
viewtopic.php?t=306
viewtopic.php?t=717
viewtopic.php?t=1146

[Martin Sleziak]

Tento príklad sa objavil na písomke (presnejšie prvá časť), takže využijem tento topic na to, aby som spomenul aké chyby sa objavili v odovzdaných písomkách.

Riešenie
Pretože táto úloha mala viac častí, ešte raz zosumarizujem len dôkaz, že z injektívnosti $g\circ f$ vyplýva injektívnosť $f$. (To je tá časť ktorá bola na písomke.)

Pripomeniem, že definícia injektívnosti je
$$f(x_1)=f(x_2) \Rightarrow x_1=x_2$$
alebo ekvivalentne
$$x_1\ne x_2 \Rightarrow f(x)_1\ne f(x_2).$$

Stručne zhrnutý dôkaz: $f(x_1)=f(x_2)$ $\overset{(1)}\Rightarrow$ $g(f(x_1))=g(f(x_2))$ $\overset{(2)}\Rightarrow$ $x_1=x_2$
Alebo obmenou: $x_1\ne x_2$ $\overset{(2)}\Rightarrow$ $g(f(x_1))\ne g(f(x_2))$ $\overset{(1)}\Rightarrow$ $f(x_1)\ne f(x_2)$
V oboch prípadoch implikácie označené $(1)$ sú miesta, kde sme využili, že $g$ je zobrazenie a na miestach označených $(2)$ sme využili, že $g\circ f$ je injekcia.

Časté chyby
Vo viacerých písomkách ste za definíciu injektívnosti prehlásili niečo, čo v skutočnosti vyplýva z toho, že ide o zobrazenie. Tu je pár príkladov, sú to v podstate citáty z písomiek:

• $g\circ f$ je injektívne, teda pre ľubovoľné $x_1,x_2\in X$ platí $x_1=x_2$ $\Rightarrow$ $g(f(x_1))=g(f(x_2))$;
• $g\circ f$ je injektívne $\Rightarrow$ pre všetky prvky množiny $X$ existuje najviac jeden prvok množiny $Z$;

Oba hovoria presne to, že $g\circ f$ je zobrazenie. (Odhliadnuc od toho, že druhý z nich je veľmi nejasne sformulovaný.)

Podľa tvrdenia zo skrípt vieme, že ak $g\circ f$ je injekcia, tak potom aj $g$ a $f$ sú injekcie.

Toto nie je pravda. (A kontrapríklad sa dá pozrieť priamo v tomto vlákne.) Pravdepodobne ste si to poplietli s tvrdením, že zloženie dvoch injekcií je injekcia. (To je presne opačná implikácia.)