Naïeve verzamelingenleer: Functies
Het ladenprincipe / duiventilprincipe
Als je vier objecten in drie laden opbergt, dan weet je zeker dat er ten minste één lade is met ten minste twee objecten. Immers, als elke lade hoogstens één object bevat, dan zouden er in totaal maar ten hoogste drie objecten in gezeten hebben, hetgeen in tegenspraak is met het gegeven dat er vier objecten opgeborgen zijn. Dit is een voorbeeld van het ladenprincipe.
Het wordt ook wel het duiventilprincipe genoemd: Als een aantal duiven in hokken in een duiventil moeten,
en er zijn meer duiven dan hokken, dan moeten er in minstens één hok twee duiven.
Iets algemener kan het ladenkast/duiventilprincipe kan als volgt iets algemener geformuleerd worden het volgende
Het veralgemeende ladenprincipe/duiventilprincipe Als \(m\) objecten in \(n\) dozen gestopt moeten worden met \(m\ge 1\) en \(n\ge 1\), dan is er ten minste één doos met ten minste \(\lceil m/n\rceil\) objecten, waarbij \(\lceil x\rceil\) het kleinste gehele getal is dat groter dan of gelijk aan \(x\) is.
Consequentie van bovenstaand principe voor verzamelingenleer:
Stel dat \(f:\; X\rightarrow Y\) een functie is van een niet-lege eindige verzameling \(X\) met \(m\) elementen naar een niet-lege eindige verzameling \(X\) met \(n\) elementen. Dan:
- als \(m>n\), dan is \(f\) niet injectief;
- als \(m<n\), dan is \(f\) niet surjectief.
Er bestaat een nog sterker ladenprincipe/duiventilprincipe:
Sterke vorm van het ladenprincipe/duiventilprincipe. Stel \(q_1,q_2,\ldots, q_n\) zijn \(n\) natuurlijke getallen groter dan \(0\) zijn. Als \(q_1+q_2+\cdots + q_n-n+1 \) objecten in \(n\) dozen gestopt moeten worden, dan doet zich minstens één van de volgende mogelijkheden voor
- er zitten ten minste \(q_1\) objecten in de eerst doos;
- er zitten ten minste \(q_2\) objecten in de tweede doos;
\(\vdots\) - er zitten ten minste \(q_n\) objecten in de \(n\)-de doos.
