Cesko.wiki Dirichletův princip
Author
Albert FloresUkázkový případ s holubníkem Dirichletův princip (někdy také označovaný jako zásuvkový princip, přihrádkový princip, princip králíků a kotců nebo princip holubníku) je matematické tvrzení z teorie množin, případně nekonečné kombinatoriky.
Nejjednodušší, „populární“ znění principu se dá formulovat například, že pokud umístíme m předmětů do n přihrádek (m, n jsou přirozená čísla), kde m > n, pak bude existovat alespoň jedna přihrádka ve které budou alespoň dva předměty. Umístíme-li tedy například deset holubů (m = 10) do devíti přihrádek v holubníku (n = 9), pak v alespoň jedné přihrádce musí být alespoň dva holubi. +more V jeho obecnější verzi pak lze říct, že pokud umístíme kn+1 předmětů do n přihrádek, pak v alespoň jedné přihrádce bude alespoň k+1 předmětů (pro 19 holubů a devět přihrádek bude existovat alespoň jedna, v které budou alespoň 3 holubi). Tato jednoduchá tvrzení jsou poté dále zobecněna a formálněji definována - viz níže.
Ačkoliv tento samozřejmý princip byl používán již dříve, za prvního, kdo ho užíval vědomě k dokazování složitějších tvrzení, je považován německý matematik Johann Peter Gustav Lejeune Dirichlet (1805-1859). Ten jej jako první výslovně uvedl v roce 1834 pod názvem Schubfachprinzip (zásuvkový princip). +more Pod označením zásuvkový princip (principio dei cassetti) je dodnes používán např. v italštině. V angličtině se používá zejména označení pigeonhole principle (princip holubníku), v dalších jazycích (např. v ruštině) pak Dirichletův princip. Princip holubníku není úplně přesný překlad, protože slovo pigeonhole se v angličtině používá prakticky už jen v přeneseném významu, kdy znamená buď přihrádku, typicky v nějakém třídicím regálu na poštu, nebo i sloveso zaškatulkovat, zařadit do kategorie. Přesto se tento překlad používá (podobně i do němčiny zpětně pronikl pojem Taubenschlagprinzip) a holubi jsou oblíbeným příkladem, na kterém se tento princip ilustruje.
Příklady
Několik jednoduchých příkladů pro ilustraci principu: # Mějme koš s 8 černými a s 10 bílými ponožkami. Poslepu z něj budeme vytahovat po jedné ponožce. +more Otázka zní, kolik budeme muset vytáhnout nejméně ponožek, abychom měli jistotu, že budeme mít alespoň jeden pár stejné barvy. Odpověď je tři, neboť máme dvě skupiny (přihrádky) - černé a bílé a po vytáhnutí třetí ponožky tak v jedné z těchto skupin již musí být dvě ponožky. # Ačkoliv zní princip jednoduše, může být použit k dokázání na první pohled nečekaných výsledků. Můžeme např. dokázat, že v Praze žijí dva lidé, kteří mají přesně stejný počet vlasů. Uvážíme-li, že počet vlasů jednoho člověka nikdy nepřesahuje 1 000 000 a v Praze žije více než 1 000 000 lidí - pak musí být alespoň dva, kteří mají stejný počet vlasů. # Máme-li skupinu n lidí, kde se někteří navzájem znají, pak vždycky existují dva takoví, kteří v této skupině znají stejný počet lidí. Rozdělovali bychom jednotlivé lidi do skupin podle toho, kolik znají ostatních, pak těchto skupin bude n - 1, neboť nemůže zároveň existovat skupina, kde by byl někdo, kdo zná všechny ostatní a skupina, kde by byl někdo, kdo nezná nikoho. Když by někdo totiž znal všechny ostatní, musel by znát i tohoto člověka, a jelikož se dle zadání musí lidé znát navzájem, musel by ho znát i on. Máme tedy n lidí a n-1 skupin, což znamená, že alespoň v jedné z nich musí být alespoň 2 lidé - ti tedy znají stejný počet lidí. (Místo toho, že se lidé znají, se dá příklad formulovat např. i tak, že si podávají ruce, hrají proti sobě zápasy atp. ) # Měli bychom dokázat, že na konvexním šestnáctistěnu s 9 vrcholy existuje vrchol, z kterého vychází alespoň 6 hran. Díky Eulerovu vztahu pro počet vrcholů (v), hran (h) a stěn (s) vypuklého mnohostěnu v - h + s = 2 spočítáme počet hran: 23. Rozdělíme každou na půl a vznikne nám 46 polohran. Rozřadíme je do devíti skupin podle toho, z kterého z 9 vrcholů vycházejí. Jelikož 5 \times 9 = 45 , musí alespoň v jedné skupině být 6 polohran, tudíž z jednoho vrcholu musí alespoň 6 polohran, tedy i hran, vycházet.
Formulace principu a jeho zobecňování
Dirichletův princip tvrdí, že pokud nekonečná množina vznikla jako sjednocení konečně mnoha množin, pak alespoň jedna z nich byla nekonečná.
Obdobný princip lze vyslovit i pro nespočetné množiny:
Pokud nespočetná množina vznikla jako sjednocení konečně mnoha množin, pak alespoň jedna z nich byla nespočetná.
Uveďme ještě třetí zajímavý princip podobného typu:
Pokud rozložíme množinu všech racionálních čísel na konečně mnoho částí, pak alespoň jedna z těchto částí obsahuje podmnožinu izomorfní s celou množinou racionálních čísel.
Při snaze o zobecňování Dirichletova principu především směrem k nekonečným systémům nekonečných množin se lze setkat hned se dvěma problémy: buď se nelze obejít bez axiomu výběru, nebo se zobecnění v některých případech provést vůbec nedá - viz následující kapitola.
Možné problémy
Nelze se obejít bez axiomu výběru
Následující verze Dirichletova principu je dokazatelná pouze připustíme-li axiom výběru. Tuto verzi lze vyjádřit třemi ekvivalentními způsoby: * Je-li sjednocení spočetně mnoha množin nespočetné, pak alespoň jedna z těchto množin je nespočetná. +more * Je-li sjednocení souboru spočetných množin nespočetné, pak tento soubor je nespočetný. * Sjednocení spočetně mnoha spočetných množin je spočetné.
Nedokazatelnost tohoto tvrzení v ZF lze ověřit užitím Fraenkel-Mostowského permutačních modelů.
Zobecnění nelze provést vůbec
Velice oblíbená je úvaha typu:
Nekonečnou množinu X nikdy nemohu získat jako sjednocení méně než |X| množin, z nichž každá má mohutnost menší než |X|.
Hodně se to podobá Dirichletovu principu v jeho nejjednodušší verzi… jenže to bohužel není pravda.
Uvažujme o kardinálním číslu \aleph_{\omega} \,\! .
Takové číslo lze poskládat jako sjednocení spočetně mnoha (tedy méně než \aleph_{\omega} \,\. ) disjunktních množin: \aleph_{\omega} = \bigcup \{ a_i : i \isin \omega \} \,\. +more , z nichž každá má mohutnost menší než \aleph_{\omega} \,\. .
Stačí definovat konečnou rekurzí: * a_0 = \aleph_0 \,\! * a_i = \aleph_{i} - \bigcup \{ a_j : j
Množiny, které takto „porušují“ možné zobecnění tohoto principu, se nazývají singulární kardinály.
Použití principu
Nejužitečnější je i přes svou jednoduchost základní verze Dirichletova principu. V důkazu mnoha vět z matematické analýzy narazíme na formulace typu „až na konečný počet hodnot“, v jejichž pozadí obvykle stojí nějaká forma Dirichletova principu, často vnímaného jako něco samozřejmého.