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

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

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

A fenti lemma további értelmezése: Ha f:H-> H' párbaállító leképzés/bijekció, akkor létezik g:P(H)->P(H') párbaállító leképzés/bijekció.

A fenti lemma bizonyítása: Legyen g:P(A)->P(B) azon leképezés, amely A egy részhalmazához B azon részhalmazát rendeli, amelyet az A-beli elemek f-nél vett képei (A elemeinek párjai) alkotják. Könnyen belátható, hogy g bijekció P(A) és P(B) között.

Egy p párbaállító leképezésnek/bijekciónak van egy inverze is. q a p párbaállító leképezés/bijekció inverz leképzése, ha B minden b eleméhez rendeli A-beli párját, azaz azt az a elemet, amely párja b. q is egy párbaállító leképezés/bijekció. A (p,q) pár tulajdonsága p o q=id_B és q o p=id_A, azaz egy elem párjának párja a kiinduló elem. Ezen két tulajdonság karakterizálja is azon bijekciópárokat, amelyek elemei egymás inverzei. Így egy függvény bijekció volta belátható úgy, hogy megadjuk inverzét és igazoljuk a fenti két tulajdonságot. p-nek fenti q inverzére a p^-1 jelölést is használjuk.

Az elõzõ esetben g inverze az a leképzés lesz, amely P(B) egy eleméhez A azon részhalmazát rendeli, amely a B-beli elemek f^-1 melletti párjait tartalmazza.

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 (szinte az egész szemeszteren végighúzódóan) is jellemzõ a fenti gondolat, amelyet azonban nem mindig fogunk részletezni.

Tétel: Egy n elemû halmaz részhalmazainak száma 2ⁿ, azaz r_n=2ⁿ.

Bizonyítás: Néhány fogalommal kezdünk.

Definíció: Egy H halmaz R részhalmazának karakterisztikus függvénye k_R:H->{0,1}, amely egy h elemhez 1-et rendel, ha h az R halmaz eleme és 0-t rendel, ha h nem eleme az R halmaznak.

Egy karaktersztikus függvény egy véges halmazon vett függvény, amit egy véges táblázattal írhatunk le.

Definíció: Legyen H={h₁,h₂,..., h_n}. H egy R részhalmazának karakterisztikus vektora k_R=(k₁,k₂,...,k_n), ahol k_i értéke 1 ha h_i az R halmaz eleme és 0, ha h_i nem eleme az R halmaznak.

Legyen Q={0,1}×{0,1}×...×{0,1} az n hosszú 0-1 sorozatok halmaza. Definiálunk egy bijekciót P(A) és Q között: H egy R részhalmazához rendeljük hozzá k_R karakterisztikus vektorát.

A fenti leképzés bijektív mivoltát be kell látni. Ezt megtehetjük inverzének megadásával (és annak ellenõrzésével, hogyvalóban inverze leképzésünknek): Egy Q={0,1}×{0,1}×...×{0,1}-beli (k₁,k₂,k₃,...,k_n) vektor párja R={h_i:k_i=1} részhalmaza H-nak.

Q számossága 2ⁿ a következõ alapelv alapján:

II. Alapelv: |A₁×A₂×...× A_n|= |A₁|.|A₂|...|A_n|.

Ez az alapelv ismét rendkívül elemi: a szorzás fogalmát megalapozó alapelv.

Ebbõl adódik a tétel.

A fenti bizonyítás arra is jó, hogy rámutasson a hatványhalmaz elnevezésre. P(H) azonosítható {0,1}×{0,1}×...×{0,1} halmazzal, ahol a tényezõk H elemeivel azonosítottak (a karakterisztikus vektorokon keresztül), azaz a {0,1} (halmazelméletben 2-nek nevezett halmaz) önmagával vett többszörös Descartes-szorzatával. Halmazelméletben értelmezzük halmazok hatványát is. A^B (vagy bizonyos értelmezési okok miatt ^BA) az f: B->A függvények halmazát jelöli. P(H) azonosítható (a karakterisztikus függvényen keresztül) {0,1}^H-val, amit a halmazelméletben 2^H-val is jelölünk. Gyakran P(H), {0,1}×{0,1}×...×{0,1} és 2^H között nem teszünk megkülönböztetést.

Tétel: r_n=2r_n-1.

Bizonyítás: Legyen H=H'U{s} egy n elemû halmaz egy speciális s elemmel, H'=H-{s}, azaz H' egy n-1 elemû halmaz. P(A) elemei két osztályba sorolhatók aszerint, hogy s eleme-e egy részhalmaznak vagy nem. A két osztály diszjunkt. Továbbá az egyik osztály (az s-et nem tartalmazó elemek) elemei H' összes részhalmazát adják, azaz P(H'). Továbbá a másik osztály (az s-et tartalmazó elemek) elemei H' összes részhalmazaival párbállíthatók: egy R részhalmaz párja R-{s} (inverze H' egy részhalmazához azt a párt rendeli, amit az s elem hozzáadásával kapunk). Így osztályozásunk mindkét osztályának elemszáma r_n-1. A bizonyítás befejezése a következõ alapelvbõl adódik.

III. Alapelv: A₁, A₂, ..., A_n páronként diszjunkt halmazok esetén |A₁ U A₂ U ... U A_n|= |A₁|+|A₂|+...+|A_n|.

Ez az alapelv ismét rendkívül elemi: az összeadás fogalmát megalapzó alapelv.

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

Megjegyzés: A részhalmazok számára már belátott formula a rekurzió alapján, teljes indukcióval is belátható.