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.

Obtížnost: Snadná úloha (řešená úvahou nebo přímo z definic)
Úloha na dokazování, ověřování
En translation
	Zaslat komentář k úloze