Egy 4 elemű halmaz összes részhalmazának száma 2^4. Miért?

Úgy van, ahogyan a fenti írta, és azt az eljárást teljes indukciónak nevezzük. Ő azt csinálta, hogy mindig az 1-gyel kisebb elemszámú halmaz részhalmazaiból indult ki.

Szemléletesen; vegyük az {1;2;3;4} halmaz részhalmazit. Írjuk fel azokat, amelyekben a 4-es nem szerepel:

{}

{1}

{2}

{3}

{1;2}

{1;3}

{2;3}

{1;2;3}

Ezekből 8 darab van. Mostmár csak a 4-et tartalmazó részhalmazokat kell felírni, azokat pedig nemes egyszerűséggel úgy kapjuk, hogy a fentiekbe beleírjuk a 4-est, így nyilván azok is 8-an lesznek, összesen tehát 16-an.

Az előző ugyanezt írta le, csak ő az üres halmaztól kezdte.

___

Másik megoldás, hogy valami olyasmit számolunk meg, amiből ugyanannyi van, mint a részhalmazokból, de azt könnyebben meg tudjuk számolni.

Minden részhalmaz "dekódolható" egy számsor szerint; a halmaz elemei alá írjunk 1-est vagy 0-t aszerint, hogy a részhalmazba be akarjuk válogatni vagy sem, például az

1234

0110

esetén a {2;3} halmazt kapjuk. Ha alul csak 0 van, akkor az üres halmazt, ha csak 1-es, akkor az {1;2;3;4} halmazt.

Ez szerencsére fordítva is igaz, tehát a halmazból egyértelműen felírható a számsor, például az {1;3;4}-hez az 1011 számsor tartozik, más nem.

Tehát a részhalmazok és a kódok kölcsönösen egyértelmű kapcsolatban állnak egymással.

Ez azért jó, mert a kódszámokat könnyebben össze lehet szedni; összesen 2*2*2*2=16-an vannak. És általánosan is igaz, hogy egy n elemű halmaznál 2*2*2*...*2=2^n darab számsor, így részhalmaz található.