] >
We geven enkele toepassingen die vaak gebruikt worden.
3.35 Stelling (Het principe van Dirichlet). Laten en eindige verzamelingen zijn met . Zij een afbeelding van naar . Dan is niet injectief. (Of anders geformuleerd: er is een zodat meer dan één element heeft.)
Bewijs. We schrijven en . Gegeven is dat . Er zijn bijecties en .
Stel is injectief. Dan is ook injectief. Echter . Tegenspraak.
Dus is niet injectief. □
Het principe van Dirichlet staat ook bekend als het ‘pigeonhole principle’ en het ‘ladenprincipe’: als je voorwerpen in laden opbergt en er zijn meer voorwerpen dan laden, dan is er een lade met meer dan één voorwerp.
We hebben natuurlijk ook:
3.36 Stelling. Laten en eindige verzamelingen zijn met . Zij een afbeelding van naar . Dan is niet surjectief. (Of anders geformuleerd: er is een zodat leeg is.)
Bewijs. In: ”Getallen”, Epsilon deel 65, uitgegeven door Epsilon-Uitgaven. □
Bewijs.
Is een oneindige verzameling, dan is de situatie geheel anders. Zo is injectief, maar niet surjectief: de injectiviteit is een axioma en dat niet in het beeld zit is ook een axioma. Omdat hebben we dus een bijectie van naar . Dus . Laat je uit het element weg, dan houd je er dus nog evenveel over! In latere hoofdstukken zullen we ook naar andere oneindige verzamelingen kijken.
Aftelbare verzamelingen zijn oneindig. Is aftelbaar, dan is er een bijectie . In is dus een rij te vormen waarin geen herhalingen optreden en waar alle elementen in voorkomen. Er zijn ook andere (grotere) oneindige verzamelingen. Die noemt men overaftelbaar. In hoofdstuk 15 gaan we daar dieper op in.