Kolik podmnožin má množina o n prvcích?
Dušan Polanský
V žádném případě se nechci pouštět do učeného povídání o množinách. To bych dopadl jako kdysi většina učitelek na základních školách, jež učily žáčky na prvním stupni základům teorie množin a samy o množinách nevěděly skoro nic, natož aby vůbec tušily k čemu mohou být dobré. Pokud čtenáře teorie množin více zajímá, ať si obstará kvalitní učebnici teorie množin a může se vyřádit dle chuti a svého IQ. Můj cíl je prostý, chci ukázat na množinách kapánek abstraktnější matematické uvažování, než na jaké jsme jsme zvyklý při počítání s čísly.
Náš úkol nebude složitý, máme zjistit a pak korektně dokázat kolik podmnožin má množina o n prvcích. Prvky množiny budeme označovat malými písmeny a, b, c, d nebo malými písmeny s indexy a1, a2 atd. Množiny budeme značit velikými písmeny, např.: P, R, S, T. Prvky množiny budeme uzavírat do složených závorek, prázdnou množinu podle tohoto úzusu zapíšeme pomocí dvojice složených závorek bez mezery takto: P = {}. Naše množiny budou neuspořádané, tj. podmnožinu ab množiny, která obsahuje prvky a, b nebudeme považovat za různou od podmnožiny b, a.
Na výpočet půjdeme dvěma způsoby. Prvně vyloženě intuitivně. Náš intuitivní přístup nám dovolí odhadnout výsledek, jenomže odhad není pro matematiku důkaz. O tom, že náš odhad byl přesný, se ujistíme důkazem pomocí matematické indukce. Podruhé si vysvětlíme důkaz pomocí binomického vzorce. Žádné obavy, já jej také neumím z hlavy napsat, to bych musel matematiku učit, což musí být pěkná otrava nebo mít matematické nadání, což nemám, anebo hlavu mít velikou jako velikánský červený meloun z Jižního Slovenska, a takovou ji opravdu nemám, takže vzorec si pro jistotu společně osvěžíme.
Začneme intuitivní úvahou. Takže mějme množinu, která nemá žádný prvek: P = {}. Kolik bude mít podmnožin. Ne žádnou, ale jednu, právě prázdnou podmnožinu, tj. {}! Vezmeme si množinu, která má jeden prvek: Q = {a}. Kolik má podmnožin? Přesně dvě: a, {}. Teď si představme množinu s dvěma prvky: T = {a, b}. Kolik má podmnožin? Přesně čtyři: a, b, ab, {}. Teď budeme uvažovat množinu s třemi prvky: R= {a, b, c}. Kolik má podmnožin? Přesně osm: a, b, c, ab, ac, bc, abc, {}. Pokusme se z našich dílčích výsledků něco rozumného vydedukovat. Naše množiny měly v závislosti na počtu prvků postupně 1, 2, 4, 8 podmnožin. Tahle řada se dá zapsat lehce pomocí mocnin přirozeného čísla 2, opravdu 20 = 1, 21 = 2, 22 = 4, 23 = 8. Zdá se, že množina s n prvky má 2n podmnožin.
Zkusme si náš odhad, že počet podmnožin množiny s n prvky je 2n, dokázat matematickou indukcí. Klasický důkaz matematickou indukcí funguje tak, že se nějaký vzoreček dokáže nejprve pro n = 1, pak z předpokladu, že vzorec platí pro n = k, se šikovně snažíme dokázat, že platí i pro n = k + 1. Když se tyhle dva kroky povedou, tak to, co jsme měli dokázat, platí. U množin musíme udělat malou změnu, nezačneme u n = 1, ale již u n = 0, jelikož uvažujeme i prázdnou množinu, tj. množinu, která nemá žádný prvek. To je malý rozdíl proti přirozeným číslům 1, 2, 3 … k nimž 0 nepatří.
Takže začneme množinou, která nemá žádný prvek, náš vzorec říká že podmnožin je 20 = 1, což je pravda, jelikož množina bez prvků má pouze jednu podmnožinu, a to prázdnou.
Teď uvažujme množinu R s k prvky R = {a1, a2, …… ak}, pro kterou dle našeho předpokladu je počet všech jejích podmnožin 2k a dále množinu s k + 1 prvky S = {a1, a2, …… ak, ak+1}, ta by měla mít podle našeho předpokladu 2k+1 podmnožin. Je jasné, že každá podmnožina množiny R je současně podmnožinou S, protože S má stejné prvky jako R a navíc ještě jeden prvek, a to ak+1. Teď musíme zjistit kolik podmnožin přibylo v množině S přidáním prvku ak+1. Přesně 2k. Proč? Je to prosté, ke každé podmnožině množiny R přidáme prvek ak+1 a navíc ještě musíme uvažovat samotný prvek ak+1, který tvoří jednu podmnožinu. Takže všech podmnožin množiny S bude 2k + 2k = 2(2k) = 2k+1. Tím se z našeho dohadu stala matematická pravda.
Pokud jste se v posledním kroku důkazu nechytli, nic se neděje, vysvětlíme si jej podrobně. Nech R = {a1, a2} a S = {a1, a2, a3}. R má čtyři podmnožiny: a1, a2, a1a2, {}. Teď vygenerujeme všechny nové podmnožiny množiny S výše zmíněným postupem, tj. přidáme ke každé podmnožině množiny R prvek a3 a jednu podmnožinu vytvořenou jenom prvkem a3. Udělejme to: a1a3, a2a3, a1a2a3, a3. Kolik je jich? Ano, čtyři, přesně tolik, kolik je podmnožin množiny R. Kolik má množina S podmnožin? Zjistíme to tím, že k čtyřem podmnožinám množiny R přidáme čtyři nové podmnožiny S, tedy 22 + 22 = 8.
Teď si ukážeme důkaz s využitím binomické věty, viz obrázek níže. Pro malé připomenutí zapomenutých znalostí z kombinatoriky jsem v bodě č.1 uvedl zápis kombinačního čísla a jeho výpočet. Ten pracuje s faktoriálem, ten je definován takto: n! = 1.2. … .(n-1).n, např. 3! = 3.2.1 = 6. C(n,k) nám určuje počet kombinací o k prvcích z n prvků, přičemž n ≥ k. U kombinací nezáleží na pořadí prvků. Kupříkladu C(3,2) = 3, opravdu, jestli n = 3, např. ať jsou to prvky: a, b, c, tak všechny možné kombinace druhé třídy z těchto tří prvků jsou: ab, ac, bc. To, že C(n,n) = 1, je zřejmé; jediná možná kombinace n třídy z n prvků je kombinace, v níž jsou všechny prvky. Podobně C(n,1) = n, jelikož kombinací o jednom prvku je přesně n, postupně všechny samotné prvky. C(n,0) = 1 berme definotoricky, nebo si můžeme říct, že je to prázdná kombinace a ta je právě jedna, podobně jako je počet prázdných množin. Při důkazu se nám tahle analogie bude hodit. V bodě č. 2 je připomenuta binomická věta.
V bodě č. 3 je zapsáno, co to vlastně znamená spočíst počet všech podmnožin množiny o n prvcích. Je to součet všech kombinací nulté třídy, to bude zmíněná prázdná množina, první třídy, druhé atd. až třídy o n prvcích z n prvků. Je vidět, že tento součet dostaneme automaticky z binomické věty, v níž položíme a = 1 a b = 1. No a nemusíme ani nic počítat, viz bod č. 4, jelikož binomická věta nám automaticky dává výsledek 2n. V bodě č. 5 je uveden pro větší názornost konkrétní výpočet pro množinu o čtyřech prvcích. No a to je vše.
V Brně 17. 8. 2014.