DU9 - LS 2017/18

[Martin Sleziak]

Zadanie

Nech $A$, $B$, $C$ sú množiny, pričom množina $C$ je neprázdna, a $f\colon A\to B$ je zobrazenie.

Potom môžeme definovať zobrazenie $\varphi \colon {C^B}\to {C^A}$ predpisom
$$\varphi(g)=g\circ f.$$



Dokážte, alebo nájdite kontrapríklad:
a) Ak $f$ je surjektívne, tak $\varphi$ je injektívne.
b) Ak $f$ je surjektívne, tak $\varphi$ je surjektívne.
c) Ak $f$ je bijektívne, tak $\varphi$ je bijektívne.
d) Ak $f$ je injektívne, tak $\varphi$ je injektívne.

Toto je asi jedna z ťažších domácich úloh - pracujeme so zobrazeniami medzi množinami zobrazení.
Ale azda nezaškodí vyskúšať aj niečo takéto. (V dôkazoch na prednáške sme s nimi robili viackrát.)

[Martin Sleziak]

Riešenia

Začnime s tvrdeniami, ktoré neplatia - sú do b a d.
Tu teda vlastne nájsť nejaký vhodný kontrapríklad.

Kontrapríklad pre b:
Chceli by sme nájsť taký príklad, že $f$ je surjektívne, ale $\varphi$ nie je surjektívne.
To, že $\varphi$ nie je surjektívne, vlastne znamená to, že nie každé zobrazenie $A\to C$ vieme dostať ako zloženie $g\circ f$.
Ak si vezmeme za $B$ jednoprvkovú množinu, tak $f$ musí byť konštantné zobrazenie.
Potom aj každé zobrazenie tvaru $\varphi(g)=g\circ f$ je konštantné.
Ak si za $A$ a $C$ zvolíme množiny, ktoré majú viac než jeden prvok, tak sa dajú nájsť aj nekonštantné zobrazenia $A\to C$. (Môžeme napríklad zobrať $A=C$ a zobrazenie $id_A$.) Teda nie každý prvok z $C^A$ sa dá dostať ako $\varphi(g).$

Kontrapríklad pre d:
Chceli by sme nájsť príklad, kde $f$ je injektívne, ale $\varphi$ nie je injektívne.
Uvedomme si, že injektívnosť $\varphi$ vlastne znamená platnosť implikácie: $g_1\circ f=g_2\circ f$ $\Rightarrow$ $g_1=g_2$. (K tomuto sa ešte detailnejšie vrátime pri dokazovaní časti a.)

My chceme nájsť príklad, kde táto implikácia neplatí. T.j. chceme aby súčasne platilo $g_1\circ f= g_2\circ f$ a $g_1\ne g_2$.

Ak majú zobrazenia $g_{1,2}$ byť rôzne, musia sa líšiť aspoň v jednom bode definičného oboru.
Vyskúšajme napríklad $B=C=\{0,1\}$ a $g_1(0)=0$, $g_1(1)=1$; $g_2(0)=g_2(1)=0$.
Teraz ešte chceme nejako zvoliť zobrazenie $f$. Pritom určite nesmieme žiaden bod zobraziť zobrazením $f$ do $1$, vtedy by sme dostali rôzne zložené zobrazenia.

Spoiler:

Ak by sme totiž pre nejaké $x$ mali $f(x)=1$, tak by platilo:
$g_1(f(x))=g_1(1)=1$,
$g_2(f(x))=g_2(1)=0$,
a teda $$g_1(f(x)) \ne g_2(f(x)).$$

Musíme teda prvky definičného oboru $f$ zobrazovať iba na nulu. (Prezieravo sme si $g_1$ a $g_2$ zvolili tak, že sa aspoň v jednom bode zhodujú; máme teda kam zobrazovať prvky.)
Ak dodržíme túto podmienku, tak môžeme $A$ zvoliť takmer ľubovoľne. Napríklad $A=\{0\}$ a $f(0)=0$.

Skúste si nakresliť obrázok množín $A$, $B$, $C$ a zobrazení $f$, $g_1$, $g_2$ a presvedčiť sa na obrázku, že $g_1\circ f=g_2\circ f$ ale $g_1\ne g_2$.

Poznámka: Ak sa pozriete na dôkaz časti a, tak môže byť jasnejšie prečo sme $f$ zvolili nesurjektívne zobrazenie a prečo sme $g_{1,2}$ vybrali akurát takýmto spôsobom. Alebo aj obrátene, ak uvažujete o tom ako nájsť vhodný kontrapríklad, môže vám to pomôcť pri hľadaní dôkazu časti a.

Súvis s kardinalitami: Môžeme si tiež všimnúť, že ak by sa nám takéto tvrdenie podarilo dokázať, tak to by bol súčasne dôkaz toho, že $a\le b$ $\Rightarrow$ $c^b\le c^a$.
Vieme, že takáto implikácia neplatí ani v prípade, že $a$, $b$, $c$ sú konečné. (A na prednáške sme vdieli, že z $a\le b$ vyplýva $c^a\le c^b$.)
Takže aj na základe tohto sa dá uhádnuť, že takéto tvrdenie nebude platiť a skôr by sme chceli nájsť kontrapríklad. (A bol by som ochotný aj niečo takéto brať aj ako legitímne riešenie - ak je tam uvedený aj príklad čísel $a$, $b$, $c$, pre ktoré takáto implikácia neplatí.)

[Martin Sleziak]

Zostávajú nám dve časti, ktoré skutočne platia - tam treba vymyslieť nejaký dôkaz. Začnime s tou ľahšou z nich.

Dôkaz časti c. Skúsme na to ísť podobným spôsobom aký sme použili v niektorých dôkazoch o kardinalitách. Ak sa nám podarí nájsť inverzné zobrazenie $\psi$ k zobrazeniu $\varphi$, tak tým súčasne ukážeme, že $\varphi$ je bijektívne.

Chceme teda nájsť vhodné zobrazenie $\psi \colon C^A \to C^B$. Dá sa vcelku ľahko vymyslieť takéto zobrazenie:
$$\psi(h)=h\circ f^{-1}$$
pre ľubovoľné $h\colon A\to C$.
Na tomto mieste sme súčasne využili to, že $f$ je bijektívne a teda existuje inverzné zobrazenie $f^{-1}$.

Spoiler:

Niečo podobné sme robili viackrát. Opäť môže pomôcť obrázok a skúsiť si rozmyslieť aké zobrazenia máme k dispozícii.
Konkrétne máme zadané zobrazenie $h\colon A\to C$.
Chceme dostať nejaké zobrazenie $\phi(h)\colon B\to C$.
Pomohlo by nám, keby sme mali nejaké zobrazenie $B\to A$, potom by ho stačilo zložiť so zobrazením $h$.
Naštastie máme k dispozícii $f^{-1}\colon B\to A$, teda môžeme tieto dve zobrazenia v správnom poradí poskladať
$$\require{AMScd}
\begin{CD}
B @>{f^{-1}}>> A @>{h}>>C
\end{CD}
$$

Teda takéto zobrazenie $\psi$ sa zdá byť vcelku prirodzenou voľbou, ak ho chceme dostať z vecí, ktoré môžeme použiť.

Stačí teraz overiť, že $\psi\circ\varphi$ aj $\varphi\circ\psi$ je identita.
\begin{align*}
\psi(\varphi(g))&=\psi(g\circ f)=(g\circ f)\circ f^{-1} = g\circ (f\circ f^{-1}) = g\\
\varphi(\psi(h))&=\varphi(h\circ f^{-1})=(h\circ f^{-1})\circ f = h\circ (f^{-1}\circ f) = h
\end{align*}

Zistili sme, že ku zobrazenie $\varphi$ existuje inverzné zobrazenie. To znamená, že $\varphi$ je bijekcia.

[Martin Sleziak]

Dôkaz časti a.
Začnime tým, že si poriadne rozmyslíme, čo chceme dokázať.
Pracujeme so zobrazením definovaným ako
$$\varphi(g)=g\circ f.\tag{*}$$
Teda zobrazeniu $g\colon B\to C$ priradíme jeho zloženie $g\circ f$.

Chceme dokázať, že $\varphi$ je injektívne. Ak si spomenieme na definíciu injektívnosti, tak vlastne chceme dokázať
$$\varphi(g_1)=\varphi(g_2) \qquad\Rightarrow\qquad g_1=g_2.$$
Ak toto tvrdenie prepíšeme pomocou definície zobrazenia $\varphi$, t.j. pomocou $(*)$, tak vlastne chceme zdôvodniť, že
$$g_1\circ f=g_2\circ f \qquad\Rightarrow\qquad g_1=g_2.$$
Pritom máme zadané, že $f$ je surjektívne.

Túto úlohu sme týmto vlastne preformulovali na to, že chceme dokázať takúto vec.

Tvrdenie. Nech $f\colon A\to B$ a $g_{1,2}\colon B\to C$ sú zobrazenia, pričom $f$ je surjektívne. Potom z $g_1\circ f=g_2\circ f$ vyplýva $g_1=g_2$; t.j.
$$g_1\circ f=g_2\circ f \qquad\Rightarrow\qquad g_1=g_2.$$

Chceme dokázať rovnosť $g_1=g_2$, čiže vlastne to, že $$g_1(b)=g_2(b)$$ platí pre každé $b\in B$.
Pritom by sme nejako chceli využiť surjektívnosť zobrazenia $f$ a tiež to, že máme rovnosť $g_1\circ f=g_2\circ f$. (T.j. vieme, že $g_1(f(a))=g_2(f(a))$ pre ľubovoľné $a\in A$.)
Kým začnete čítať dôkaz, tak sa skúste sami zamyslieť nad tým, čo viete dostať z vecí, ktoré som doteraz spomenul.

Spoiler:

Dôkaz.
Nech $b\in B$.
Pretože $f$ je surjektívne, vieme že existuje $a\in A$ také, že $f(a)=b$.
Pre ľubovoľné takéto $a$ máme z podmienky $g_1\circ f=g_2\circ f$ rovnosť
$$g_1(f(a))=g_2(f(a)),$$
čo je presne rovnosť
$$g_1(b)=g_2(b).$$

Ukázali sme, že pre každé $b$ patriace do $B$ (t.j. do definičného oboru zobrazení $g_{1,2}$) platí $g_1(b)=g_2(b)$. To znamená, že $g_1=g_2$.

[Martin Sleziak]

Čo to hovorí o kardinalite
Pozrime sa na to, čo by platnosť takýchto tvrdení hovorila o kardinalite. Chceme sa pozrieť najmä na časti b) a d) - či úvahy o počte prvkov by nám pomohli zbadať, že takéto tvrdenia neplatia. (Pri časti d) som takéto niečo stručne spomenul aj vyššie.)
Pre konečné množiny vieme, že platí:

• Ak existuje bijekcia $f\colon X\to Y$, tak $|X|=|Y|$.
• Ak existuje injekcia $f\colon X\to Y$, tak $|X|\le|Y|$.
• Ak existuje surjekcia $f\colon X\to Y$, tak $|X|\ge|Y|$.

Prvé dve tvrdenia poznáme aj pre nekonečné množiny - to pre nás vlastne bola presne definícia rovnosti a nerovnosti pre kardinálne čísla.
Tretím tvrdením sme sa pre nekonečné množiny zatiaľ nezaoberali - spomeniem, že tu nejako do hry vstúpi axióma výberu.
Ale na tomto mieste možno stačí, keď si rozmyslíme, čo sa stane pre konečné množiny.
My sa zaoberáme zobrazeniam $f\colon A\to B$ a $\varphi \colon {C^B}\to {C^A}$; pričom $\varphi$ je definované ako $\varphi(g)=g\circ f.$

Označme si $|A|=a$, $|B|=b$ a $|C|=c$.
A úplne stačí, keď sa pozeráme na prípad, keď ide konečné množiny. T.j. $a$, $b$, $c$ sú prirodzené čísla.

Pozrime sa na to, čo jednotlivé tvrdenia. Najprv na tie dve, ktoré aj platia:
a) Ak $f$ je surjektívne, tak $\varphi$ je injektívne.
Ak platí tvrdenie z časti a) platí, tak to vlastne hovorí, že z $a\ge b$ vyplýva $c^b\le c^a$. Toto je skutočne pravda.
c) Ak $f$ je bijektívne, tak $\varphi$ je bijektívne.
Ak platí tvrdenie z časti c), tak vlastne máme, že z $a=b$ vyplýva $c^b=c^a$.
Asi nás neprekvapí, že sme z týchto tvrdení dostali vlastnosti umocňovania prirodzených čísel (prípadne kardinálnych čísel), ktoré sú naozaj pravdivé.
Pre istotu zdôrazním, že keď sme z a) resp. z c) dostali ako dôsledok pravdivé tvrdenie, to ešte nutne neznamená, že tvrdenia a) a c) naozaj aj platia. Treba ich skutočne aj dokázať. (Aj z nepravdivého tvrdenia môžeme dostať pravdivé; implikácia $1\Rightarrow0$ je pravdivá.)

Zaujímavejšie je pozrieť sa na ostatné dve tvrdenia - už sme videli, že na ne vieme nájsť kontrapríklady. Čo by sme vlastne dostali, ak by tieto tvrdenia boli pravdivé?

b) Ak $f$ je surjektívne, tak $\varphi$ je surjektívne.
Ak by takéto tvrdenie platílo, tak by sme mali $a\ge b\Rightarrow c^b\ge c^a$, resp.
$$b\le a \Rightarrow c^b\ge c^a.$$
Ľahko vidíme, že tvrdenie neplatí. (Dokázali sme, že z $b\le a$ vyplýva $c^b\le c^a$, tu máme presne opačnú nerovnosť. Napríklad $a=c=2$, $b=1$ nám dá kontrapríklad.)
Takže z tohto už vieme prísť na to, že tvrdenie v časti b) neplatí; stačí už nájsť konkrétny príklad zobrazenia $f$.

d) Ak $f$ je injektívne, tak $\varphi$ je injektívne.
Ak by takéto tvdenie platilo, tak by z neho vyplývalo $$a\le b \Rightarrow c^b\le c^a.$$
Opäť, nerovnosť je tu presne naopak "ako má byť". Konkrétne napríklad pre $a=1$ a $b=c=2$ táto implikácia neplatí.
Opäť vidíme, že takéto tvrdenie platiť nemôže. (A keďže to od nás v zadaní chcú pustíme sa do hľadania kontrapríkladu; ale vlastne sme aspoň zistili to, aké veľkosti množín by sa nám pri hľadaní kontrapríkladu mohli hodiť.)

[Martin Sleziak]

Tento semester som zadal ako úlohu iba časť d). Riešenie a aj niečo o tom, ako sa naň dalo prísť, si môžete prečítať vyššie. Sem pridám iba pár komentárov k niektorým odpovediam, ktoré som dostal.
(V princípe to, že bolo viacero nesprávnych riešení nie je až také zlé - aspoň nám to umožňuje ešte raz si uvedomiť, že niekedy pracujeme so zobrazeniami medzi množinami zobrazení. Takéto niečo sme robili pri viacerých dôkazoch týkajúcich umocňovania kardinálov - a táto úloha tiež bola zadaná s úmyslom, že sa pozriete na takýto typ zobrazení.)

Otázka bola, či zobrazenie $\varphi$ je injektívne; nie či $g\circ f$ je injektívne.
Dostal som viacero riešení, kde bol nejaký kontrapríklad ukazujúci, že $g\circ f$ nemusí byť injektívne aj ak $f$ je injektívne.
Takýto príklad sme už videli v staršej úlohe:
viewtopic.php?t=1995
viewtopic.php?t=735
viewtopic.php?t=493
Napríklad je to takáto dvojica zobrazení:


Toto však je riešenie inej úlohy. V zadaní som sa pýtal na to, či zobrazenie $\varphi \colon {C^B}\to {C^A}$ určené predpisom
$$\varphi(g)=g\circ f$$
je injektívne. (Pričom máme dané to, že zobrazenie $f\colon A\to B$ je injektívne.)
Všimnite si, že tento predpis naozaj každému zobrazeniu $g\colon B\to C$ priradí zobrazenie $\varphi(g)\colon A\to C$; teda $\varphi$ je skutočne zobrazenie z $C^B$ do $C^A$ (z množiny všetkých zobrazení $B\to C$ do množiny všetkých zobrazení $A\to C$.)

Za takéto riešenie som dával 2 body - riešili ste o dosť inú úlohu než bola v zadaní, ale z vášho riešenia je jasné aspoň to, že rozumiete pojmu injektívneho zobrazenia.

Prečo nefunguje substitúcia $b=f(a)$
Dostal som viacero riešení, ktoré vyzerali zhruba takto:

Chceme ukázať, že zobrazenie $\varphi$ je injektívne, t.j. vlastne chceme dokázať:
\begin{align*}
\varphi(g_1)&=\varphi(g_2) &\Rightarrow g_1=g_2\\
g_1 \circ f&=g_2 \circ f &\Rightarrow g_1=g_2
\end{align*}
Aby sme dokázali rovnosť dvoch zobrazení $g_{1,2}\colon B\to C$, stačí ukázať, že sa zhodujú v každom bode definičného oboru. T.j. chceme ukázať, že pre ľubovoľné $b\in B$ platí $g_1(b)=g_2(b)$.
Zoberme si nejaké $b\in B$. Tento prvok môžeme vyjadriť ako $b=f(a)$ a potom z predpokladu g_1 \circ f=g_2 \circ f$ dostaneme:
\begin{align*}
g_1 \circ f(a)&=g_2 \circ f(a)\\
g_1(f(a))&=g_2(f(a))\\
g_1(b)&=g_2(b)
\end{align*}
Tým sme ukázali, že $g_1=g_2$.

Toto asi nebude správny dôkaz - keď sme vyššie už ukázali kontrapírklad na toto tvrdenie. Viete si rozmyslieť, kde je v tomto argumente problém?

Spoiler:

Nemáme zaručené, či naozaj existuje $a\in A$ také, že platí $f(a)=b$.
Takéto niečo by sme vedeli dostať, ak by sme mali k dispozícii predpoklad, že $f$ je surjektívne. Takýto argument by bol teda správny dôkaz tvrdenia z časti a) - a keď sa pozriete vyššie, budete vidieť, že v dôkaze tejto časti sú použité skoro rovnaké kroky.

Za takéto riešenie som dával 4 body - opäť je pravda, že ste riešili inú úlohu než bola zadaná, ale tentokrát je to aspoň úloha týkajúca sa skutočne zobrazenia z $C^B$ do $C^A$ a správne ste aj napísali, čo znamená injektívnosť zobrazenia $\varphi$. (A keby sme mali navyše k dispozícii nejaký ďalší predpoklad o zobrazení $f$ - ako je vysvetlené v časti skrytej spoilerom - tak by to bol správny argument.)