20. Feladat: Injektív függvények száma

Feladat:

Az előző feladat (19) halmazai esetén (\( |X| = 4, |Y| = 3 \)) létezik-e injektív (kölcsönösen egyértelmű) függvény \( X \)-ből \( Y \)-ba? Válaszát indokolja (skatulya-elv)!

Megoldás:

Nem létezik.

Egy függvény pontosan akkor injektív, ha az értelmezési tartomány különböző elemeihez a képhalmaz különböző elemeit rendeli.

Mivel \( |X| = 4 \) elemünk van, de csak \( |Y| = 3 \) különböző értéket tudunk felvenni, a skatulya-elv (skatulya-elv / Dirichlet-elv) alapján legalább két \( X \)-beli elemhez ugyanazt az \( Y \)-beli értéket kell rendelnünk.

Általánosan: injektív függvény \( A \to B \) csak akkor létezik, ha \( |A| \le |B| \).