Részhalmazok
 

Jelölések: Egy S halmaz részhalmazainak halmazát P(S)-sel jelöljük és S hatványhalmazának nevezzük.

Lemma: P(S) elemszáma csak S elemszámától függ.

A fenti lemma értelmezése: Ha A és B elemszáma ugyanaz, akkor P(A) és P(B) elemszáma is ugyanaz.

A fenti lemma bizonyítása: Legyen A és B két azonos számú halmaz. Legyen f egy A és B közötti bijekció.

``Azonos elemszámúság'' egy olyan fogalom, amely nagyon természetes. Ennek azonossága a két halmaz közötti bijekcióval definícióként, vagy alapelvként fogadható el:

|A|=|B| akkor és csak akkor, ha létezik A és B közötti bijekció.

Ekkor legyen f' a P(A) és P(B) kozötti azon leképezés, amely A egy részhalmazához B azon részhalmazát rendeli, amelyet az A-beli elmek f-nél vett képei alkotják. Könnyen belátható, hogy f' bijekció P(A) és P(B) között.

A fentiek után értelmes a következõ kérdés: Hány részhalmaza van egy n elemû halmaznak? Legyen r(n) a kérdésre a válasz.

A továbbiakra is jellemzõ a fenti gondolat, amelyet azonban nem fogunk részletezni.

Formula:

Tétel: Egy n elemû halmaz részhalmazainak száma 2^n, azaz r(n)=2^n.

Bizonyítás: Legyen A={a(1),a(2),...,a(n)}. Legyen Q={0,1}x{0,1}x...x{0,1} az n hosszú 0-1 sorozatok halmaza. Definiálunk egy bijekciót P(A) és Q között: A egy K részhalmazához rendeljük hozzá K karakterisztikus vektorát, azaz azt a vektort, amely i-edik komponense 1, ha a(i) elem K-nak, és 0, ha a(i) nem eleme K-nak. Q számossága 2^n a következõ alapelv alapján:

|A(1)xA(2)x...xA(n)|=|A(1)|.|A(2)|...|A(n)|.

Ebbõl adódik a tétel.

A fenti bizonyítás arra is jó, hogy rámutasson a hatványhalmaz elnevzésre. P(A) azonosítható a {0,1} (halmazelméletben 2-nek nevezett halmaz) önmagával vett többszörös szorzatával, azaz hatványával.

Megjegyzés: A fenti két alapelvhez hozzáadhatunk egy újat.

A(1), A(2), ..., A(n) páronként diszjunkt halmazok esetén
|A(1) U A(2) U ... U A(n)|=|A(1)|+|A(2)|+...+|A(n)|.

A fenti három alapelven alapuló bizonyításokat kombinatorikus vagy bijektív bizonyításoknak nevezzük.

Rekurzió:

Tétel: r(n)=2r(n-1).

Bizonyítás: Legyen A={a(1),...,a(n)} egy n elemû halmaz. P(A) két osztályba sorolható aszerint, hogy a(n) eleme-e egy részhalmaznak vagy nem. A két osztály diszjunkt, továbbá mindkettõ osztály esetén bijekció létesíthetó Á={a(1),...,a(n-1)} részhalmazaival, azaz elemszámuk r(n-1).

Megjegyzés: A kapott formula a rekurzió alapján is belátható

Aszimptotika:

Aszimptotikára nincs szükség

Generátorfüggvény:

Tétel: +{r(n)x^n: n természetes szám}=1/(1-2x)