Sbírka matematických úloh

Porovnání konečných množin

Úloha číslo: 3359

• Varianta

  Existuje-li prosté zobrazení z \(X\) do množiny \(Y\), potom \(|X|\leq |Y|\).

• Řešení

  Matematickou indukcí podle \(n=|X|\).

  I. Pro \(n=1\), je-li \(f:X\to Y\) zobrazení, potom \(Y\) musí mít alespoň jeden prvek, jinak by \(f\) nebylo zobrazení. Tím dostaneme požadovaný důsledek \(|X|=1\leq |Y|\).

  II. Nechť \(X=n+1\) a tvrzení platí pro zobrazení ze všech \(n\)-prvkových množin. Zvolíme libovolný prvek \(x\in X\) a položíme \(X'=X\setminus x\) a \(Y'=Y\setminus f(x)\).

  Protože \(f\) je prosté, není \(f(x)\) obrazem jiného prvku než \(x\). Tedy \(f'=f\setminus (x,f(x))\) je zobrazení mezi \(X'\) a \(Y'\).

  Zobrazení \(f'\) je prosté, protože kdyby nebylo, t.j. existovaly by různé prvky \(z,z'\in X'\) takové, že \(f'(z)=f'(z')\) a pak by i \(f(z)=f'(z)=f'(z')=f(z')\), což je spor s tím, že \(f\) je prosté.

  Protože \(|X'|=n\), můžeme uplatnit indukční předpoklad na \(f'\) a získat \(|X'|\leq|Y'|\). Odtud pak \(|X|=|X'|+1\leq|Y'|+1=|Y|\).

   

  Pozn.: Všimněte si, že uvedená nerovnost ve skutečnosti vyplývá z faktu, že je-li \(f\) prosté, potom \(Y\) musí mít alespoň tolik prvků co \(f\) (bráno jako relace), protože se v relaci nemohou prvky na druhé souřadnici opakovat.

• Varianta

  Existuje-li zobrazení množiny \(X\) na \(Y\), potom \(|X|\geq |Y|\).

• Řešení

  Matematickou indukcí podle \(n=|Y|\).

  I. Pro \(n=1\), je-li \(f:X\to Y\) zobrazení na a \(Y\) je neprázdná, potom \(X\) musí mít alespoň jeden prvek, jinak by \(f\) bylo prázdné zobrazení a to není na. Tím dostaneme požadovaný důsledek \(|X|\geq 1=|Y|\).

  II. Nechť \(Y=n+1\) a tvrzení platí pro zobrazení na všechny \(n\)-prvkové množiny. Zvolíme libovolný prvek \(y\in Y\) a položíme \(Y'=Y\setminus y\). V množině \(X\) určíme neprázdnou množinu prvků, které se zobrazí na \(y\) a ty odebereme z \(X\), formálně\(X'=X\setminus \{x: f(x)=y\}\).

  Zúžením \(f\) na \(X'\) dostaneme opět zobrazení \(f'=f\setminus \{(x,y):f(x)=y\}\) mezi \(X'\) a \(Y'\).

  Zobrazení \(f'\) je na, protože kdyby nebylo, t.j. pokud by existoval prvek \(z\in Y'\) takový, že \(\forall x\in X': z\ne f(x)\), pak by existence \(z\) byla ve sporu s tím, že zobrazení \(f\) je na, protože \(\forall x\in X\setminus X': f(x)=y\ne z\).

  Protože \(|Y'|=n\), můžeme uplatnit indukční předpoklad na \(f'\) a získat \(|X'|\geq|Y'|\). Odtud pak \(|X|>|X'|\geq|Y'|=|Y|-1\) neboli \(|X|\geq |Y|\).

   

  Pozn.: Všimněte si, že uvedená nerovnost ve skutečnosti vyplývá z faktu, že je-li \(f\) na, potom \(f\) musí mít alespoň tolik prvků co \(Y\), protože každý prvek \(Y\) se vyskytně na druhé souřadnici nějaké dvojice z \(f\).