msleziak.com

Zadanie sa vo všetkých skupinách týkalo takej situácie, že sme mali zobrazenie $f\colon M\to M$ a pýtali sme sa, či platí implikácia
$$f\circ f\circ f=f\circ f \qquad\implies\qquad f\circ f=f.$$
Pričom v jednotlivých skupinách sme ešte mali k dispozícii nejakú informáciu o zobrazení $f$. (Konkrétne to, že $f$ je injektívne, surjektívne, bijektívne.)

Môžeme si všimnúť, že už vo formulácii zadania sme nenápadne využili asociatívnosť skladania zobrazení - nemusel som písať, či $f\circ f\circ f$ znamená $(f\circ f)\circ f$ alebo $f\circ (f\circ f)$; vieme, že tieto dve uzátvorkovania dávajú to isté zobrazenie.

Spomeniem tiež, že sa pomerne bežne používa označenie $f^2=f\circ f$ a $f^3=f\circ f\circ f$. (A podobne v grupách zvykneme písať aj $x^2=x*x$, $x^3=x*x*x$, atď.)

Skúsim sem napísať niečo k tomu, ako sa tieto úlohy dali riešiť - a tiež okomentovať nejaké veci z odovzdaných riešení.

Možno ako prvé spomeniem nejaké príklady funkcií, ktoré nám napadnú skoro hneď a ktoré spĺňajú rovnosť $f\circ f\circ f=f\circ f$:

• Uvedená rovnosť platí pre $f=id_M$.
• Uvedená rovnosť platí pre každú konštantnú funkciu. T.j. ak si zvolíme $c\in M$ a definujeme $f(x)=c$ (pre všetky $x\in M$), tak tiež máme takúto funkciu.

V oboch prípadoch ale platí aj $f\circ f=f$, čiže kontrapríklad sme nenašli.

Vlastnosti $f\circ f=f$ (resp. $x*x=x$ pre binárnu operáciu $*$) sa hovorí idempotentnosť.
Wikipédia: Idempotence § Idempotent functions

Tu sa budem zaoberať skupinami, kde sme mali o $f$ zadanú ďalšiu informáciu. Skupinu, v ktorej bolo zadané iba to, že $f$ je zobrazenie - a bolo treba nájsť kontrapríklad - som dal ako samostatný topic: https://msleziak.com/forum/viewtopic.php?t=1724

Nech $M\ne\emptyset$ je množina a $f\colon M\to M$ je zobrazenie. Ak $f$ je bijektívne a platí $f\circ f\circ f=f\circ f$, tak platí aj $f\circ f=f$.

Poznámka: Zo zadaných predpokladov vieme dokonca dostať $f=id_M$.$\newcommand{\inv}[1]{{#1}^{-1}}$

Táto úloha sa dá riešiť mnohými spôsobmi. Ako uvidíme nižšie, stačí nám vedieť, že $f$ je injekcia. Alebo to, že $f$ je surjekcia.
Ak vieme, že $f$ je bijekcia, tak to už je veľmi silná informácia, ktorá nám môže pomôcť nájsť veľmi priamočiare riešenie.

Hint: Ak vieme, že $f$ je bijekcia, tak existuje $\inv f$. Dalo by sa to nejako využiť?
Takýto postup som ukázal okrem iného aj preto, že je podobný na túto úlohu: Nech $(G,*)$ je grupa a $x\in G$. Ukážte, že ak $x*x*x=x*x$, tak $x*x=x$. (A z toho by sme vedeli dostať aj to, že $x=1_G$.)

Vedeli by ste zdôvodniť takéto tvrdenie?
Je tvrdenie o bijekciách špeciálny prípad pre tohoto tvrdenia pre vhodnú grupu $G$? Poznámky k odovzdaným riešeniam

Toto platí všeobecne pre úlohy, kde treba niečo dokázať.
Ak som vyskúšal, že tvrdenie platí pre nejakú jednu konkrétnu bijekciu $f$ (alebo aj pre viacero príkladov), tak to nestačí ako argument, že tvrdenie platí vždy.
(Skúšanie príkladov je užitočné - môžeme pri ňom prísť na to, prečo tvrdenie platí. Ale ak chceme nejako zdôvodniť jeho všeobecnú platnosť, tak už musíme naozaj vymyslieť niečo, čo platí pre ľubovoľné $f$ spĺňajúce zadané predpoklady.)

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:

• Úloha 3.4 v 01zobrazenia.pdf.
• Dá sa nájsť aj tu na fóre: https://msleziak.com/forum/viewtopic.php?t=68
• Wikipédia: Left inverse function
• Takéto tvrdenie môžete nájsť na veľa ďalších miestach. Rôzne náhodné ukážky: Google, Google Books, Google Images, YouTube

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.

Martin Sleziak wrote: ↑Sun Oct 10, 2021 4:08 pm 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.)

A azda by som mohol napísať aj riešenie bez odvolávanie sa na tieto tvrdenia - už nechám na váš vkus, či sa vám to zdá prehľadnejšie jedným alebo druhým spôsobom. (A tiež si môžete všimnúť, že argument sa veľmi podobá na argument použitý pri dôkaze "krátenia".)

Ak $f$ je injekcia
Ak mám rovnosť $f(f(f(x)))=f(f(x))$ tak dostávam (priamo z definície injektívnosti), že aj
$$f(f(x))=f(x).$$
Pretože to platí pre ľubovoľné $x$, tak máme $f\circ f=f$. (A ak túto úvahu zopakujeme ešte raz, dostaneme $f=id$.)

Ak $f$ je surjekcia
Pre ľubovoľné $y\in M$ existuje nejaké $x$ také, že $f(x)=y$. Potom máme
$$f(f(y))=f(f(f(x)))=f(f(x))=f(y).$$
Máme rovnosť $f(f(y))=f(y)$ pre všetky $y\in M$. To znamená, že $f\circ f=f$. (Opäť, aj v tomto prípade by sme vedeli odvodiť aj to, že $f=id$; ešte raz by sme zopakovali veľmi podobnú úvahu, ako sme urobili teraz.)