Možno si spomeniete, že na cviku venovanom zobrazeniam sme sa pozreli aj na úlohy, ktoré sa dajú nazvať "krátenie" injekciou resp. surjekciou pri skladaní:
https://msleziak.com/forum/viewtopic.php?t=1360
(Tieto veci sú užitočné aj nezávisle od tejto konkrétnej úlohy, ale na prvom cviku som ich spomínal sčasti aj preto, že toto som mal naplánované ako možnú úlohu na odovzdávanie.)
Keď už som prezradil, že takéto tvrdenia by sa tu hodili, tak asi už je pomerne zjavné, ako by sa dali využiť na zdôvodnenie tvrdení o injekcii a surjekcii.
Oplatí sa nad tým zamyslieť samostatne, ale nižšie napíšem riešenie. (Skryl som ho pod spoiler, aby ste mali možnosť sa nad tým zamyslieť samostatne - skôr než si ho prečítate.)
Najprv pripomeniem v nejakej podobe tvrdenia, ktoré tu budeme používať.
Chceli by sme nejako ukázať:
- Nech $M\ne\emptyset$ je množina a $f\colon M\to M$ je zobrazenie. Ak $f$ je surjektívne a platí $f\circ f\circ f=f\circ f$, tak platí aj $f\circ f=f$.
- Nech $M\ne\emptyset$ je množina a $f\colon M\to M$ je zobrazenie. Ak $f$ je surjektívne a platí $f\circ f\circ f=f\circ f$, tak platí aj $f\circ f=f$.
Pomocou spomenutých tvrdení môžeme postupne dostať:
Podobne ako pre bijekciu, aj tu vieme dostať, že zo zadaných predpokladov v~skutočnosti už vyplýva $f=id_M$.
Úloha sa určite dá vyriešiť aj bez toho, aby si človek uvedomil, že takéto tvrdenia sa dajú použiť.
Uviedol som takéto riešenie - väčšina riešení, kde ste to urobili bez odvolávania sa na tieto tvrdenia, bola taká, že sa v riešení (pri troche snahy) dá nájsť niečo podobné na dôkaz $(I)$ alebo $S$ pre špeciálny prípad $h=f\circ f$ a $g=f$.
*****
V jednom z odovzdaných riešení som si prečítal, že:$\newcommand{\inv}[1]{{#1}^{-1}}$
$\inv f$ existuje, lebo $f$ je injekcia
Toto nie je pravda - inverzné zobrazenie k $f$ existuje práve vtedy, keď $f$ je bijekcia.
Stále by sa dalo niečo podobné použiť. V našej situácii (keď $M\ne\emptyset$) totiž platí:
- Ak $f\colon M\to M$ je injekcia, tak existuje $g\colon M\to M$ taká, že $g\circ f=id_M$.
- Ak $f\colon M\to M$ je surjekcia, tak existuje $g\colon M\to M$ taká, že $f\circ g=id_M$.
Takáto vec sa dá sformulovať aj o čosi všeobecnejšie - nepotrebujeme aby obor a koobor bola tá istá množina. Napríklad:
Môžete sa zamyslieť nad tým, prečo takéto tvrdenie platí a aj ako by sa dalo použiť v tejto úlohe.
*****
Napíšem tu jedno z odovzdaných riešení - aj keď som formuláciu trochu pomenil (snáď takto je to napísané jasnejšie).
Je to zo skupiny, ktorá mala zadané, že $f$ je injekcia. Dokážeme tu však priamo to, že $f=id_M$. (Samozrejme, z toho potom vyplýva aj rovnosť $f\circ f=f$.)
Tvrdenie. Nech $f\colon M\to M$ je injektívne zobrazenie také, že $f\circ f\circ f=f\circ f$. Potom platí $f=id_M$.
Označme si
\begin{align*}
F&=\{x\in M; f(x)=x\}\\
G&=\{x\in M; f(x)\ne x\}
\end{align*}
Našim cieľom je ukázať, že $F=M$ resp. (čo je v podstate to isté), že $G=\emptyset$.
Uvedomme si takúto vlastnosť:
Pozorovanie P1. Ak pre nejaké $x\in F$ platí $f(x)\in F$, tak aj $x\in F$.
$$f(x)\in F \Rightarrow x\in F$$
Ak sa teraz pozrieme na ľubovoľné $x\in M$, tak máme rovnosť
$$f(f(f(x)))=f(f(x)),$$
čo vlastne znamená, že $f(f(x))\in F$. Z toho čo sme si rozmysleli vyššie (Pozorovanie 1) dostávame
$$f(f(x))\in F \overset{P1}{\Rightarrow} f(x)\in F \overset{P1}{\Rightarrow} x\in F.$$
Teda sme naozaj zistili, že každý prvok z~$M$ patrí do $F$, čiže $F=M$. Inými slovami, $$(\forall x\in M) f(x)=x,$$ a teda $f=id_M$.
Ešte drobná poznámka k dôkazu sporom.
Ak sa vám taký postup pozdáva viac, môžete miesto toho skúsiť postupovať sporom a ukázať, že $G=\emptyset$. Zhruba tak to bolo v odovzdanej úlohe. Je to ale v tomto konkrétnom prípade podľa mňa viac-menej to isté - a v prípadoch, že priamy dôkaz a dôkaz sporom sú skoro rovnaké je asi lepšie použiť priamy dôkaz. Dôkaz sporom používajme hlavne vtedy, keď nám takýto postup zjednoduší dôkaz oproti tomu, ako keby sme sa ho snažili zapísať v podobe priameho dôkazu.
Dôkaz sporom je veľmi užitočný, ale na druhej strane, nemali by sme si zvyknúť používať ho pričasto. Ak si naň priveľmi privykneme i v situáciách, kde sa mu dá ľahko vyhnúť, tak sa nám môže ľahko stať niečo takéto: Dokazujeme nejaké tvrdenie T1 sporom. V dôkaze prídeme na to, že nám treba zdôvodniť nejaké T2, ktoré dokazujeme tiež sporom. A možno sa podobne dostaneme ešte o úroveň hlbšie - každopádne už aj pri druhej úrovni (dôkaz sporom vnútri iného dôkazu sporom) môžeme trochu stratiť prehľad, pri tretej by to bolo ešte o čosi komplikovanejšie.