Existencia surjekcie vs. existencia injekcie

[Martin Sleziak]

Pre konečné množiny poznáme takúto vec: $\newcommand{\abs}[1]{\lvert{#1}\rvert}\abs X \le \abs Y$ $\Longleftrightarrow$ existuje injekcia $X\to Y$ $\Longleftrightarrow$ existuje surjekcia $Y\to X$. (Prinajmenšom pre neprázdne množiny - ale prázdnu množinu dajme na chvíľu bokom.)

Pre nekonečné množiny bola existencia injekcie $X\to Y$ pre nás priamo definíciou toho, že $\abs X\le\abs Y$. Azda je teda prirodzená otázka, či to je ekvivalentné s existenciou surjekcie opačným smerom.

Odpoveď je áno - pre neprázdne množiny. A ešte sa asi patrí spomenúť aj to, že to nejako súvisí s axiómou výberu.

[Martin Sleziak]

Čo vyplýva zo surjektívnosti resp. injektívnosti zloženia$\newcommand{\emps}{\emptyset}\newcommand{\Zobr}[3]{{#1}\colon{#2}\to{#3}}\newcommand{\abs}[1]{\lvert{#1}\rvert}$

Nech $\Zobr fXY$ a $\Zobr gYZ$ sú zobrazenia. Potom platí:

• Ak $g\circ f$ je injektívne, tak aj $f$ je injektívne.
• Ak $g\circ f$ je surjektívne, tak aj $g$ je surjektívne.

Časť o injektívnosti bola tento semester ako jedna z domácich úloh - nebudem k nej sem teda písať detailnejší komentár.

Dôkaz časti o surjekciách je tiež pomerne ľahký.

Spoiler:

Nech $z\in Z$. Pretože $g\circ f$ je surjektívne, existuje $x\in X$ také, že $g(f(x))=z$.
Ak si označíme $y=f(x)$, tak máme $g(y)=z$.
Ukázali sme, že pre každé $z\in X$ existuje nejaký vzor v zobrazení $g$; teda toto zobrazenie je surjektívne.

Z uvedených dvoch tvrdení ľahko dostaneme takéto pozorovanie - úmyselne sformulované v podobe, v akej sa nám bude o chvíľu hodiť:

Fakt 1. Nech $\Zobr fXY$ a $\Zobr gYZ$ sú zobrazenia. Ak $g\circ f$ je bijektívne zobrazenie, tak $g$ je surjekcia a $f$ je injekcia.

Existencia jednostranného inverzného zobrazenia

Vieme, že k zobrazenie $\Zobr fXY$ existuje inverzné zobrazenie práve vtedy, keď $f$ je bijektívne.
Inverzné zobrazenie je zobrazenie $\Zobr gYX$ také, že
\begin{align*}
g\circ f&=id_X\\
f\circ g&=id_Y
\end{align*}

Skúsme sa pozrieť tieto dve rovnosti tak, že si budeme všímať každú zvlášť. Sú podobné - iba sa vymenili úlohy zobrazení $f$ a $g$ - takže si skúsme napríklad všímať podmienku
$$g\circ f=id_X.$$
Z toho, čo sme si povedali vyššie (Fakt 1), je jasné, že ak platí takáto rovnosť, tak $g$ musí byť surjektívne a $f$ musí byť injektívne.

Môžete sa stretnúť s terminológiou, že ak platí $g\circ f=id_X$, tak hovoríme, že $g$ je ľavé inverzné zobrazenia k $f$ a obrátene, zobrazenie $f$ je pravé inverzné ku $g$.

Chceme sa pozrieť na tvrdenia, ktoré sú v istom zmysle obrátené:
Ak o zobrazení $f$ vieme, že je injektívne, bude existovať $g$ s takouto vlastnosťou?
Ak o zobrazení $g$ vieme, že je surjektívne, bude existovať $f$ s takouto vlastnosťou?

Začnime s injektívnosťou.

Fakt 2. Ak $X\ne\emps$ a $\Zobr fXY$ je injektívne zobrazenie, tak existuje $\Zobr gYX$ také, že $g\circ f=id_X$.

Predpoklad, že $X\ne\emps$ skutočne potrebujeme. Konkrétne v prípade, že $Y\ne\emps$ máme prázdne zobrazenie $\emps\to Y$ a nemáme žiadne zobrazenie $Y\to\emps$.

Chceme zobrazenie $\Zobr gYX$ také, že $g\circ f=id_X$, t.j. ak sme sa z nejakého prvku $x$ dostali po "$f$-šípke" do $y$, tak "$g$-šípka" by mala tento prvok poslať späť na $x$. To nám dáva v podstate návod, ako má $g$ vyzerať; treba si ale ešte rozmyslieť, čo spravíme s prvkami v $Y$, na ktoré sa nič nezobrazilo.

Dôkaz. Predpokladáme, že $X\ne\emps$, zoberme si teda jeden konkrétny prvok $x_0\in X$. Definujme teraz $\Zobr gYX$ predpisom:
$$g(y)=
\begin{cases}
x_0 & \text{ak }y\notin f[X], \\
x & \text{také, že }y=f(x)\text{ ak }y\in f[X].
\end{cases}
$$
Tento predpis skutočne definuje zobrazenie. Každému prvku z $y$ sme niečo priradili. A vďaka injektívnosti zobrazenia $f$ sme žiadnemu prvku z~$Y$ nepriradili viacero prvkov.

Súčasne priamo z definície zobrazenia $g$ vidíme, že pre všetky $x\in X$ platí $g(x)=x$, teda platí aj rovnosť $g\circ f=id_X$. Tým sme teda dokázali Fakt 2.$\square$

Fakt 3. Ak zobrazenie $\Zobr gYX$ je surjektívne, tak existuje zobrazenie $\Zobr fXY$ také, že $g\circ f=id_X$.

Dôkaz. Pretože $g$ je surjektívne, pre každé $y\in Y$ je množina
$$f^{-1}[\{y\}]=\{x\in X; f(x)=y\}$$
neprázdna.

Vyberme z tejto množiny jeden prvok a ten označme ako $g(y)$. Takto definované zobrazenie $g$ skutočne spĺňa $(\forall x\in X)g(f(x))=x$. Tým je tvrdenie dokázané.$\square$

Súvis s axiómou výberu

Zdôrazním, že v predošlom dôkaze sme robili naraz nekonečne veľa výberov - na tomto mieste sme použili axiómu výberu.

Dokonca platí, že Fakt 3 je ekvivalentný s axiómou výberu.

Pridám ešte aj linku na dôkazy týchto vecí v inom topicu (k inému predmetu): viewtopic.php?t=68

[Martin Sleziak]

Existencia surjekcie vs. existencia injekcie$\newcommand{\emps}{\emptyset}\newcommand{\Zobr}[3]{{#1}\colon{#2}\to{#3}}\newcommand{\abs}[1]{\lvert{#1}\rvert}$

Vlastne keď poskladáme dokopy veci uvedené vyššie, vieme dostať (s použitím axiómy výberu) takýto výsledok:

Veta. Nech $X$, $Y$ sú nejaké množiny $X\ne\emps$. Nasledujúce podmienky sú ekvivalentné:

• Existuje injekcia $X\to Y$.
• Existuje surjekcia $Y\to X$.