„Skatulyaelv” változatai közötti eltérés

nincs szerkesztési összefoglaló
[ellenőrzött változat][ellenőrzött változat]
a (Diszkrét matematikai tételek kategória hozzáadva (a HotCattel))
Nincs szerkesztési összefoglaló
[[Fájl:TooManyPigeons.jpg|thumb|right|A skatulyaelv szemléltetése galambokkal. {{nowrap|''n'' ({{=}} 10)}} galamb {{nowrap|''m'' ({{=}} 9)}} lyukban, ezért lesz lyuk, amibe több galamb jut.]]
 
A '''skatulyaelv''' az a [[Dirichlet]] által megfogalmazott matematikai elvtétel, mely szerint ha ''n'' és ''m'' pozitív egészek és ''n''>''m'', akkor ''n'' elemet ''m'' skatulyába helyezve kell lennie olyan skatulyának, amelyben 1-nél több elem van. Az elv végtelen halmazokra is alkalmazható, csak ilyenkor elemszám helyett számosságot kell használni.
 
Másképpen megfogalmazva: nem létezik olyan [[Halmazelmélet|véges halmazokon]] értelmezett [[injektív függvény]], amelynek az [[értékkészlet]]e kisebb elemszámú, mint az [[értelmezési tartomány]]a.
 
== Bizonyítás ==
A skatulyaelv indirekt módon bizonyítható: ha az elv nem igaz, akkor minden skatulyába legfeljebb egy elem kerül. Ekkor legfeljebb annyi elem van, ahány skatulya. Ellentmondás.