Definice bijekce
Úloha číslo: 3361
Ukažte, že pro zobrazení \(f:X\to X\) na konečné množině \(X\) platí, že \(f\) je prosté právě když \(f\) je na.
Platí totéž i pro nekonečné množiny \(X\)?
Řešení
Nejprve ukážeme sporem, že je-li \(f\) prosté, potom je na.
Pokud bychom měli nějaké zobrazení \(f:X\to Y\) mezi konečnými \(X\) a \(Y\), které je prosté, ale které není na, potom \(|X|=|\{x:(x,y)\in f\}|=|\{y:(x,y)\in f\}|<|Y|\).
V první rovnosti jsme využili vlastnost zobrazení, ve druhé, že \(f\) je prosté a ve třetí, že \(f\) není na, tedy existuje \(y\in Y\setminus \{y:(x,y)\in f\}\) s tím, že přidáním prvku do konečné množiny vzroste její mohutnost.
Pokud bychom položili \(Y=X\), dostaneme \(|X|<|X|\), což je spor.
Obrácená implikace také sporem.
Pokud je nějaké zobrazení \(f:X\to Y\) mezi konečnými \(X\) a \(Y\) na, ale nikoli prosté, potom \(|X|=|\{x:(x,y)\in f\}|>|\{y:(x,y)\in f\}|=|Y|\)
Opět, v první rovnosti jsme využili vlastnost zobrazení, ve druhé, že \(f\) není prosté a ve třetí, že \(f\) je na.
Pokud bychom položili \(Y=X\), dostaneme \(|X|>|X|\), což je spor.
Pro nekonečné množiny tvrzení neplatí, protože \(f(x)=x+1\) je na \(\mathbb N\) prosté, ale nikoliv na.