DU1 ZS 2015/16

[Martin Sleziak]

Skúsim sem napísať niečo k riešeniam domácich úloh. (A aj niečo ku chybám, ktoré sa objavovali.)

Ak sa chcete pozrieť na úlohy, ktoré sa objavili na d.ú. v minulosti a boli zamerané na podobné témy, môžete pozrieť tu: https://msleziak.com/forum/viewtopic.php?t=330

Vo všetkých úlohách $\mathbb N$ označuje množinu prirodzených čísel, t.j. $\mathbb N=\{0,1,2,\dots\}$. Označenie $id_{\mathbb N}$ znamená identické zobrazenie na množine $\mathbb N$, t.j. zobrazenie $\newcommand{\Zobr}[3]{#1\colon#2\to#3}\Zobr{id_{\mathbb N}}{\mathbb N}{\mathbb N}$ určené predpisom $id_{\mathbb N}(n)=n$ (pre každé $n\in\mathbb N$).

Ak budete mať nejaké otázky alebo komentáre k tomu, čo som sem dal, tak napíšte do tohoto topicu. (Takisto ak sa chcete pochváliť s nejakým iným elegantným riešením.)

[Martin Sleziak]

1. Nájdite príklad zobrazení $\newcommand{\Zobr}[3]{#1\colon#2\to#3}\Zobr{f,g}{\mathbb N}{\mathbb N}$ takých, že $f\circ g=id_{\mathbb N}$ a súčasne $g\circ f\ne id_{\mathbb N}$, (alebo zdôvodnite, že také zobrazenia neexistujú).

Riešenie:

Jednoduchý príklad je:
$f(n)=\left\lfloor\frac n2\right\rfloor$, $g(n)=2n$
Dostaneme $f(g(n))=\left\lfloor\frac{2n}2\right\rfloor=\lfloor n \rfloor = n$, čo znamená, že $f\circ g$ je skutočne identita.
Máme však $g(f(1))=g(0)=0$, teda $g\circ f$ nie je identita.

Iná možnosť:
$f(n)=
\begin{cases}
n-1 & \text{ak }n\ge1, \\
0 & \text{ak }n=0.
\end{cases}$
a $g(n)=n+1$.
Dostaneme $f(g(n))=f(n+1)=n$, teda $f\circ g$ je identita.
Súčasne $g(f(0))=g(0)=1$.

Oplatí sa skúsiť si nakresliť aj obrázky, aby bolo jasnejšie, čo tieto zobrazenia robia.

Poznámky k riešeniu:
Niekde v cvičeniach môžete nájsť takéto tvrdenia:
$g$ má ľavé inverzné zobrazenie $\Leftrightarrow$ $g$ je injekcia.
$g$ má pravé inverzné zobrazenia $\Leftrightarrow$ $g$ je surjekcia.
(Toto nie je úplne presné, ešte tam niekde treba predpoklad o neprázdnosti, ale keď sa zaoberáme iba funkciami z $\mathbb N$ do $\mathbb N$, tak máme neprázdne množiny.)

Aj ak ste si ich iba prečítali a neriešili, ale ste ochotní im uveriť, tak by vám mohli pomôcť. (Nie že by sa v texte k prednáške nemohli objaviť chyby, ale zvyčajne ak som dal úlohu, kde máte niečo dokázať, tak som sa snažil dať tam niečo, čo naozaj platí.)
Ak teda uveríme týmto dvom tvrdeniam, tak hneď vieme, že ak chceme nájsť príklad takýchto zobrazení tak: $g$ musí byť injekcia ale nesmie byť surjekcia. Na základe tých istých tvrdení prídeme aj na to, že ak chceme takýto kontrapríklad, tak $f$ bude surjekcia ale nie injekcia.

[Martin Sleziak]

2. Nájdite príklad zobrazenia $\newcommand{\Zobr}[3]{#1\colon#2\to#3}\Zobr f{\mathbb N}{\mathbb N}$ takého, že $f\circ f=id_{\mathbb N}$ a súčasne $f\ne id_{\mathbb N}$ (alebo zdôvodnite, že také zobrazenie neexistuje).

Riešenie

Vyskúšajme
$f(n)=
\begin{cases}
n+1 & \text{ak $n$ je párne}, \\
n-1 & \text{ak $n$ je nepárne},
\end{cases}$
(Opäť sa oplatí nakresliť si obrázok, aby bolo jasné, čo takéto zobrazenie robí.)

Tento predpis skutočne definuje zobrazenie: Každé prirodzené číslo je buď párne alebo nepárne, čiže každému číslu sme priradili práve jednu hodnotu. Výsledok je opäť prirodzené číslo. Pre hocijaké prirodzené číslo je $n+1$ opäť prirodzené číslo. Problém nenastane ani v druhej vetve. Ak $n$ je nepárne, tak $n\ge1$, teda $n-1\ge0$. Čiže $f(n)$ bude nezáporné celé číslo, t.j. prirodzené číslo.
(Pripomeniem, že medzi prirodzené čísla na tejto prednáške rátame aj nulu.)

Treba skontrolovať aj či $f\circ f=id_{\mathbb N}$.

Ak $n$ je párne, tak $f(n)=n+1$ je nepárne. Potom dostaneme $f(f(n))=f(n)-1=(n+1)-1=n$.

Ak $n$ je nepárne, tak $f(n)=n-1$ je párne. Potom $f(f(n))=f(n)+1=(n-1)+1=n$.

A ešte by sme mali zdôvodniť, že $f\ne id_{\mathbb N}$. Na to stačí nájsť nejaké prirodzené číslo $n$ také, že $f(n)\ne n$. A dokonca sme si vybrali taký príklad, že to bude platiť pre každé prirodzené číslo $n$.

Poznámky k riešeniu:
Môžeme si všimnúť, že vlastne ide o úlohu nájsť také zobrazenie z $\mathbb N$ od $\mathbb N$, pre ktoré platí $f=f^{-1}$.
Takýmto zobrazeniam sa niekedy hovorí aj involúcie.

[Martin Sleziak]

3. Nájdite príklad zobrazení $\newcommand{\Zobr}[3]{#1\colon#2\to#3}\Zobr{f,g}{\mathbb N}{\mathbb N}$ takých, že zložené zobrazenie $g\circ f$ je injekcia ale $g$ nie je injekcia, (alebo zdôvodnite, že také zobrazenia neexistujú).

4. Nájdite príklad zobrazení $\Zobr{f,g}{\mathbb N}{\mathbb N}$ takých, že zložené zobrazenie $g\circ f$ je surjekcia ale $f$ nie je surjekcia, (alebo zdôvodnite, že také zobrazenia neexistujú).

Tu sa dajú použiť napríklad zobrazenia z úlohy 1. A dá sa vymyslieť veľa ďalších príkladov.

[Martin Sleziak]

Problémy a chyby$\newcommand{\Zobr}[3]{#1\colon#2\to#3}$

Nejaké komentáre k veciam, ktoré sa vyskytli v odovzdaných riešeniach.

Zobrazenie môže byť "skoro čokoľvek"

Bolo by dobré uvedomiť si, že funkcia je čokoľvek, čo spĺňa definíciu funkcie. Nemusí to nutne byť niečo, čo sa dá zapísať jediným predpisom z nejakých základných funkcií.
Napríklad toto
$$f(n)=
\begin{cases}
n+1 & \text{ak $n$ je párne}, \\
n-1 & \text{ak $n$ je nepárne},
\end{cases}
$$
určuje zobrazenie z $\mathbb N$ do $\mathbb N$. (Treba si iba rozmyslieť, či sme naozaj každému prirodzenému číslu priradili práve jednu hodnotu a či výsledok je opäť prirodzené číslo.)

Takže snaha prepísať túto funkciu v nejakom inom tvare, ako napríklad
$$f(n)=(n\bmod 2)+1+2\left\lfloor{\frac{n-1}2}\right\rfloor$$
je pomerne zbytočná. (BTW tento predpis ani nesedí s tým, čo som napísal vyššie. Študent, ktorý mal toto v riešení, bral ako prirodzené čísla iba čísla $1,2,3,\dots$ t.j. nie nulu. Teda tam sú tie prípady pre $n$ párne a nepárne vymenené.)
Prepísať ho iným spôsobom by bolo užitočné vtedy, ak by nám to pomohlo pri kontrole, či $f(f(n))=n$.
Môj názor však je, že toto sa ľahšie skontroluje, ak mám túto funkciu zapísanú tým prvým predpisom (aj keď budem pri kontrole rozobrať pár rôznych prípadov), ako dosadiť $f(n)$ do takéhoto pomerne zložitého výrazu a snažiť sa ho upravovať. T.j. snažiť sa upravovať
$$(f(n)\bmod 2)+1+2\left\lfloor{\frac{f(n)-1}2}\right\rfloor,$$
pričom za $f(n)$ by som mal opäť dosadiť uvedený výraz.

Hlavne to však píšem preto, aby ste si uvedomili, že ten prvý zápis (prípadne s nejakým stručným zdôvodnením), úplne stačí na to, aby som videl, že ide o funkciu z $\mathbb N$ do $\mathbb N$.
T.j. funkcia nemusí byť nutne iba niečo, čo je nejako skombinované z vecí ako sčitovanie, násobenie, logaritmus, trigonometrické funkcie a podobne. (Pojem elementárnej funkcie, ktorý je do istej miery podobný tomu, čo som práve napísal, je v niektorých kontextoch dôležitý. Možno o ňom budete počuť na analýze v súvislosti s integrovaním. Ale tu sa zatiaľ rozprávame o funkciách všeobecne.)

Nie úplne hocičo je zobrazenie

Viacerí ľudia chceli použiť zobrazenie $\Zobr g{\mathbb N}{\mathbb N}$ definované ako $g(n)=\frac{n}2$.
Tento predpis neurčuje zobrazenie z $\mathbb N$ do $\mathbb N$, pretože napríklad $g(1)=\frac12$ nepatrí do $\mathbb N$.
(Potrebovali by sme vymyslieť nejaký predpis, kde výsledok bude vždy nejaké prirodzené číslo.)
Napríklad takáto definícia by bola už v poriadku - išlo by o zobrazenie z $\mathbb N$ do $\mathbb N$:
$g(n)=
\begin{cases}
\dfrac n2 & \text{ak $n$ je párne}, \\
0 & \text{ak $n$ je nepárne}.
\end{cases}
$

Také funkcie sa dajú nájsť
Zopár z vás sa snažilo dokázať, že sa takéto zobrazenia nedajú nájsť. Priznám sa, že v niektorých prípadoch som neporozumel argumentom, ktoré ste tam napísali. Ale azda vás aspoň príklady, ktoré som sem dal, presvedčia, že sa také zobrazenia dajú nájsť.

[Martin Sleziak]

Ešte k úlohe 1

V jednej z odovzdaných domácich úloh as vyskytlo tvrdenie, že zobrazenia také, aby platilo $f\circ g=id$ a $g\circ f\ne id$ neexistujú s takýmto zdôvodnením.

Má platiť $f(g(x))=x$.

Ak $f(g(x))=x$, tak vlastne platí $g(x)=y$ a $f(y)=x$.

Z toho dostaneme $g(f(y))=y$.

Teda $g\circ f=id$.

Problém v tomto argumente je ten, že takto naozaj viete zdôvodniť to, že $g(f(y))=y$; ale nie pre všetky $y$. Iba pre tie, ktoré sú tvaru $y=g(x)$. (Na ktoré sa niečo zobrazí zobrazením $g$.)
Čiže z tohoto naozaj vidno, že sa také zobrazenia nedajú nájsť, ak by sme požadovali aby $g$ bola surjekcia. Ale ak vyskúšame nejaké $g$, ktoré nie je surjektívne, tak už kontrapríklad vcelku ľahko nájdeme.

Niektorí z vás tvrdili, že zo zadania vidíme to, že $g=f^{-1}$. To by sme mohli tvrdiť iba ak by sme mali zadané, že $g\circ f$ aj $f\circ g$ je identita. (Zo zadania vieme iba to, že $g\circ f$ je identita.)

Našli sa riešenie, kde ste chceli skladať také zobrazenia, že jedno z nich bolo $x\mapsto x^2$ a druhé $x\mapsto\sqrt{x}$. (A prípadne ste ešte v konečnom počte bodov hodnoty zmenili.) Tu si treba dať pozor na to, že odmocnina z prirodzeného čísla nemusí byť prirodzené číslo, teda pomocou nej nedostaneme zobrazenie $\mathbb N \to \mathbb N$.

K úlohe 2
Len drobná poznámka k terminológii: Niekto nazval príklad funkcie, ktorý ste našli, permutáciou.
To nie celkom sedí s terminológiou, ktorú sme zaviedli. (My sme sa dohodli, že permutáciami nazývame bijekcie z $M$ do $M$ pre konečnú množinu $M$.)
Aj keď je pravda, že v literatúre sa niekedy termín permutácia vyskytne aj v prípade, že množina $M$ je nekonečná. (Ak by sme sa držali takejto definície, tak by to bolo úplne ok.)

[Martin Sleziak]

V niektorých skupinách ste chceli dostať zobrazenie, ktoré nie je injektívne (resp. nie je surjektívne).
Možno je užitočné vedieť si rozmyslieť, ako vyzerá negácia injektívnosti/surjektívnosti. (V niektorých odovzdaných riešeniach bola napísaná nesprávne.)

Ak negujem výrok s kvantifikátormi, tak sa kvantifikátory menia na opačné a treba ešte znegovať výrok, ktorý je vnútri (pod kvantifikátorom).
Oplatí sa premyslieť si aj to, čo tieto výroky vlastne znamenajú. (Teda nepozerať len na formálny zápis pomocou symbolov.)

Takto môžeme zapísať, že $f\colon X\to Y$ je injekcia:
$$(\forall x_1,x_2\in X) f(x_1)=f(x_2) \Rightarrow x_1=x_2$$
Negácia vyzerá takto:
$$(\exists x_1,x_2\in X) f(x_1)=f(x_2) \land x_1\ne x_2$$

Takto môžeme zapísať že $f\colon X\to Y$ je surjekcia:
$$(\forall y\in Y)(\exists x\in X)f(x)=y$$
Negácia vyzerá takto:
$$(\exists y\in Y)(\forall x\in X)f(x)\ne y$$