Injektívnosť a involúcie

[Martin Sleziak]

$\newcommand{\inv}[1]{#1^{-1}}\newcommand{\Zobr}[3]{#1\colon #2\to #3}$

a) Dokážte, alebo nájdite kontrapríklad: Ak $\Zobr fXX$ je zobrazenie a platí $f\circ f=id_X$, tak $f$ je injektívne.
b) Dokážte, alebo nájdite kontrapríklad: Ak $\Zobr fXX$ je injektívne zobrazenie, tak platí $f\circ f=id_X$.
(Pri riešení sa môžete odvolať na tvrdenia, ktoré boli dokázané na prednáške alebo na cviku -- bez toho, že by bolo treba písať znovu ich dôkaz. Ak sa však nejaké tvrdenie budete chcieť použiť, jasne sformulujte, čo presne používate.)

Ak sa chcete pozrieť na nejaké staršie úlohy týkajúce sa skladania, injektívnosti, zobrazení:
viewtopic.php?t=1595
viewtopic.php?t=1467
viewtopic.php?t=1325
viewtopic.php?t=1153
viewtopic.php?t=735
viewtopic.php?t=493

Kontrapríklad k časti b)

Zobrazenia také, že $f\circ f=id_X$ sa volajú involúcie. (A táto podmienka vlastne hovorí to, že $f$ je inverzné samé ku sebe.)
Vlastne sa iba pýtame, či každé injektívne zobrazenie $X\to X$ je involúcia. Nie je ťažké nájsť nejaké kontrapríklady.

Môžeme zobrať trojprvkovú množinu a cyklus dĺžky tri.
T.j. zoberme napríklad $X=\{0,1,2\}$ a zobrazenie dané ako $f(0)=1$, $f(1)=2$, $f(2)=0$.
Potom zobrazenie $g=f\circ f$ nie je identita, konkrétne je to trojcyklus v opačnom smere: $g(0)=2$, $g(1)=0$, $g(2)=1$.
(Oplatí sa nakresliť si obrázok.)

Ale vieme vymyslieť aj veľa iných príkladov, vyskúšajme nejaké pre $X=\mathbb R$.
Napríklad $f(x)=x$ aj $f(x)=-x$ sú involúcie.
Ale keď vyskúšame $f(x)=2x$, tak to už je vhodný kontrapríklad. Je to injektívne zobrazenie, ale neplatí $f\circ f=id_{\mathbb R}$.

Dôkaz časti a)
Zadanie som dal o injektívnosti - v skutočnosti vieme nie moc ťažko dokázať, že toto zobrazenie je bijektívne. Takže napíšem niečo aj k tomu.

Skúsme najprv napísať dôkaz z definície a potom sa pozrieť na to, že sa stačilo odvolať na nejaké tvrdenia, ktoré poznámte.

Ak $f\circ f=id_X$, tak $f$ je injektívne.
Dôkaz.
Nech $f(x_1)=f(x_2)$ pre nejaké $x_{1,2}\in X$. Potom máme:
\begin{align*}
f(x_1)&=f(x_2)\\
f(f(x_1))&=f(f(x_2))\\
id_X(x_1)&=id_X(x_2)\\
x_1&=x_2
\end{align*}
Teda sme dostali, že z $f(x_1)=f(x_2)$ vyplýva $x_1=x_2$.

Pozrime sa aj na to, či vieme dokázať bijektívnosť.

Ak $f\circ f=id_X$, tak $f$ je surjektívne.
Dôkaz.
Pre ľubovoľné $y\in X$ môžeme zobrať $x=f(y)$. Pre tento prvok platí
$$f(x)=f(f(y))=y.$$
Vidíme, že každý prvok $y\in X$ má vzor, a teda $f$ je surjektívne.

Časť a) vyplýva z iných tvrdení.
Spomeniem niektoré veci, z ktorých sme túto vec mohli odvodiť "zadarmo" - viaceré z nich sme už niekde videli.

• Ak $g\circ f$ je injektívne, tak $f$ je injektívne. (Podobná vec pre surjektívnosť: Ak $g\circ f$ je surjektívne, tak $g$ je surjektívne.)
• Zobrazenie $\Zobr fXY$ je bijekcia práve vtedy keď existuje inverzné zobrazenie $\Zobr{\inv f}YX$.
• Ak $g\circ f=id_X$, tak $g$ je surjekcia a $f$ je injekcia.

Prvé tvrdenie bolo ako úloha na prvom cviku. (Pre túto úlohu je podstatná časť pre injekcie.)
Nejaké linky (nájdete to aj na veľa iných miestach): Composite functions and one to one a Show that if $g \circ f$ is injective, then so is $f$.

K časti pre surjekcie tiež pridám nejaké linky: Proving a function is surjective given the composition is surjective a Show that if $g \circ f$ is injective, then so is $f$. (Tá druhá linka sa týka vlastne oboch častí.)1

Druhé tvrdenie je Veta 1.5 v zelenej knihe, Dôsledok 1.1.16 v bielej knihe. (Ak ho chceme použiť v tejto úlohe, treba si ešte uvedomiť, že podmienka $f\circ f=id_X$ hovorí to isté ako $\inv f=f$.)

Tretie tvrdenie som na tomto mieste spomenul, aj keď na cviku som sa k nemu nedostal. Pridám k nemu túto linku: viewtopic.php?t=99
Je to Veta 1.4 v zelenej knihe, Veta 1.1.15 v bielej knihe.

[Martin Sleziak]

Komentáre k odovzdaným riešeniam

Počty prvkov

V jednom z riešení bol pokus využiť nejako to, že ak $f\colon X\to X$ nie je injektívne, tak vieme niečo povedať o vzťahu medzi počtom prvkov $f[X]$ a $X$.
Je pravda, že pre konečné množiny by sme vedeli niečo o počte prvkov v takomto prípade povedať. (Aj keď som si nie istý, či pri tejto úlohe nám to nejako veľmi pomôže.)
Každopádne pri nekonečných množinách by sme mali s argumentom podobného typu problém. Napríklad ak si vezmeme $X=\mathbb R$ a zobrazenie $f\colon X\to X$ definované ako $f(x)=x^3-x$, tak dostaneme zobrazenie, ktoré nie je injektívne; ale súčasne platí $f[X]=X$.

Negácia injektívnosti

Vo viacerých riešeniach sa vám z nejakého dôvodu hodilo použiť predpoklad, že $f$ nie je injektívne. (Napríklad ak ste dokazovali obmenenú implikáciu alebo robili dôkaz sporom.)
Prečítal som si v jednom riešení, že v takom prípade:

Existujú $x_{1,2}\in X$ také, že $x_1=x_2$ a $f(x_1)\ne f(x_2)$.

Toto nie je správne znegovaná definícia injektívnosti. (Vlastne takéto niečo znamená, že $f$ ne je zobrazenie; ten istý bod sa zobrazil na dve rôzne hodnoty.

V skutočnosti znegovaním injektívnosti dostaneme:
Existujú $x_{1,2}\in X$ také, že $x_1\ne x_2$ a $f(x_1)=f(x_2)$.

\begin{gather*}
f\colon X\to X\text{ je injektívne } \Leftrightarrow (\forall x_{1,2} \in X) f(x_1)=f(x_2) \Rightarrow x_1=x_2\\
f\colon X\to X\text{ nie je injektívne } \Leftrightarrow (\exists x_{1,2} \in X) f(x_1)=f(x_2) \land x_1\ne x_2
\end{gather*}