Hatványhalmaz

Az {x, y, z} halmaz hatványhalmazának az elemei Hasse-diagrammal ábrázolva

A halmazelméletben egy halmaz hatványhalmazának nevezzük az adott halmaz összes részhalmazainak a halmazát. A halmazok halmazát Ernst Zermelo és Gerhard Hessenberg is vizsgálta. A hatványhalmaz elnevezés későbbi.

Definíció

Ha $H$ halmaz, akkor $𝒫(H)$-val jelöljük és a $H$ halmaz hatványhalmazának nevezzük a $H$ összes részhalmazainak halmazát. Vagy másképpen: $𝒫(H):=\{x\mid x\subseteq H\}$ ahol a $\subseteq$ szimbólum a részhalmaz-reláció jele.

A hatványhalmaz halmazrendszer, azaz egy olyan halmaz, melynek elemei halmazok. A $𝒫(H)$ rendszer elemei közé tartoznak a nem valódi részhalmazok, így az üres halmaz és $H$ is. További jelölései: $𝔭(X),2^X,\mathrm{P}\mathrm{o}\mathrm{t}(X),\mathrm{\Pi }(X),\mathrm{\wp }(X)$ és $𝔓(X)$.

Példa

Ha $H$ az $\{a,b,c\}$ háromelemű halmaz, akkor részhalmazai a következők:

• nullaelemű részhalmaza az $\mathrm{\varnothing }$ üres halmaz
• egyelemű részhalmazai az $\{a\}$, a $\{b\}$ és a $\{c\}$
• kételemű részhalmazai: $\{a,b\}$, $\{a,c\}$ és $\{b,c\}$
• egyetlen háromelemű részhalmaza saját maga: $\{a,b,c\}$

Tehát $𝒫(H)=\{\mathrm{\varnothing },\{a\},\{b\},\{c\},\{a,b\},\{a,c\},\{b,c\},\{a,b,c\}\}$

További példák:

• $𝒫(\mathrm{\varnothing })=\{\mathrm{\varnothing }\}$
• $𝒫(\{a\})=\{\mathrm{\varnothing },\{a\}\}$
• $𝒫(\{a,b\})=\{\mathrm{\varnothing },\{a\},\{b\},\{a,b\}\}$
• $𝒫(𝒫(\mathrm{\varnothing }))=\{\mathrm{\varnothing },\{\mathrm{\varnothing }\}\}$
• $𝒫(𝒫(\{a\}))=\{\mathrm{\varnothing },\{\mathrm{\varnothing }\},\{\{a\}\},\{\mathrm{\varnothing },\{a\}\}\}$

Egy halmazrendszer, például egy topológia vagy σ-algebra az alapjukul szolgáló $X$ tér, mint ponthalmaz $𝒫(X)$ hatványhalmazának részhalmaza, azaz $𝒫(𝒫(X))$ eleme.

Tételek a hatványhalmazról

• Tétel – Ha H véges halmaz és elemszáma az n természetes szám, akkor H hatványhalmazának számossága $|𝒫(H)|=2^n$.

Megjegyzés: Ez a tétel magyarázza a hatványhalmaz elnevezést, és az irodalomban néhol előforduló $2^H:=𝒫(H)$ hatványozásra utaló jelölést.

• Tétel – (Cantor-tétel) – Bármely H halmaz esetén $𝒫(H)$ számossága nagyobb H számosságánál.

Jelben: $|𝒫(H)|>|H|$.

• Tétel – A természetes számok hatványhalmazának számossága megegyezik a valós számok halmazának számosságával, azaz kontinuum-számosságú. Tömören: $|𝒫(\mathbb{N})|=|ℝ|$.

Egy hatványhalmaz több algebrai és relációs struktúra alaphalmaza is lehet.

• Állítás – Ha H halmaz, akkor a
• $(𝒫(H),\cup )$ és $(𝒫(H),\cap )$ (azaz rendre az unióval és a metszettel, mint műveletekkel ellátva) egységelemes, zéróelemes félcsoportok
• $𝒫(H)$ a $\cup$-val és $\cap$-val mint műveletekkel ellátva Boole-algebrát alkot
• $𝒫(H)$ a $\subseteq$ relációval ellátva Boole-hálót alkot.

Továbbá a mértékelmélet számára fontos tény, hogy a $𝒫(H)$ hatványhalmaz halmazgyűrű, sőt $\sigma$-algebra (szigma-algebra).

Struktúrája

A $\subseteq$ tartalmazás reláció részben rendezés a hatványhalmazon, de nem teljes rendezés, ha a teljes halmaz legalább kételemű. A legkisebb elem az $\mathrm{\varnothing }$, a legnagyobb a teljes halmaz.

A $(𝒫(X),\subseteq )$ részben rendezés teljes háló. Ez azt jelenti, hogy $𝒫(X)$ minden részhalmazának van közös legnagyobb alsó korlátja és legkisebb felső korlátja. Konkrétan ez a metszet, illetve az unió. Jelben, ha $T\subseteq 𝒫(X)$, akkor:

$\inf (T)=\bigcap _{M\in T}M\text{ és }\mathrm{s}\mathrm{u}\mathrm{p}(T)=\bigcup _{M\in T}M.$

A legnagyobb, illetve legkisebb elemek legnagyobb alsó korlátja, illetve legkisebb felső korlátja:

$\inf (\mathrm{\varnothing })=X\text{ és }\sup (\mathrm{\varnothing })=\mathrm{\varnothing }.$

Ha hozzávesszük a komplementerképzést, mint ${}^{\mathrm{c}}:𝒫(X)\to 𝒫(X)$, akkor $(𝒫(X),\cap ,\cup {,}^{\mathrm{c}},\mathrm{\varnothing },X)$ Boole-háló, azaz distributív és komplementeres háló.

Minden Boole-háló indukál egy egyértelmű kommutatív gyűrűszerkezetet, ez az úgynevezett Boole-gyűrű. Műveletei az $𝒫(X)$ halmazon a szimmetrikus differencia, mint összeadás, és a metszet, mint szorzás. Az összeadás semleges eleme az üres halmaz, és a szorzás semleges eleme a teljes halmaz.

Karakterisztikus függvény

Ha az alaphalmaz $X$, akkor minden $T\subseteq X$ részhalmazhoz hozzárendelhető egy ${\chi }_T:X\to \{0,1\}$ karakterisztikus függvény, amelyre:

${\chi }_T(x):=\{\begin{array}{cc}1,& x\in T\\ 0,& x\in ̸T\end{array}$

Ez bijekció $𝒫(X)$ és $\{0,1{\}}^X$ között. Ez motiválja a $𝒫(X)$ és a $2^X$ jelöléseket, mivel a természetes számok Neumann-modelljében $2=\{0,1\}$ (általában: $n=\{0,...,n-1\}$)

Az $𝒫(X)\cong \{0,1{\}}^X$ megfeleltetés tisztán bijekció, azonban megfelelő műveleteket definiálva izomorfizmussá tehető.

Számossága

A következőkben $|H|$ jelöli egy $H$ halmaz számosságát.

• Ha $X$ véges, akkor $|𝒫(X)|=2^{|X|}$.
• Minden halmazra teljesül Cantor tétele: $|X|<|𝒫(X)|$.

Végtelen $X$ halmaz esetén is jelölik $2^{|X|}$-nel a $|𝒫(X)|=\left|2^X\right|$ hatványhalmaz számosságát. Az általánosított kontinuumhipotézis szerint, ha az $X$ halmaz végtelen, akkor az $|X|$ számosság után az $|𝒫(X)|$ a közvetlenül következő számosság: $\mathrm{G}\mathrm{C}\mathrm{H}⟹(|X|<|Y|⟹|𝒫(X)|\le |Y|).$

Az axiomatikus elméletek hatványhalmaz-fogalmai

Cantor elméletében, a naiv halmazelméletben egyáltalán nem kétséges, hogy minden H halmaz esetén a $x\subseteq H$ kijelentésből képezett $\{x\mid x\subseteq H\}$ halmaz létezik. Az axiomatikus elméletekben ezzel szemben ezt a tényállást axiómában kell rögzíteni. Az ilyen axiómát hatványhalmaz-axiómának nevezzük.

Zermelo–Fraenkel-axiómarendszer

ZF-ben (és bővítéseiben) hatványhalmaz-axiómának nevezzük a következő formulát: $(\mathrm{\forall }x)(\mathrm{\exists }y)(\mathrm{\forall }z)((z\in y)\iff (z\subseteq x))$

ahol $z\subseteq x$ jelöli az $(\mathrm{\forall }u)((u\in z)\Rightarrow (u\in x))$ formulát.

Neumann–Bernays–Gödel-halmazelmélet

Az NBG-ben (lényegében) szabad képezni minden formalizálható T(x) tulajdonságra az {x|T(x)} kifejezést, csak ezt nem minden esetben nevezhetjük halmaznak, hanem csak osztálynak. Azt NBG esetén azt mondjuk, hogy a H kifejezés halmaz, ha levezethető az $(\mathrm{\exists }y)(H\in y)$ formula. Ezt a formulát Set(H)-val jelöljük és jelentése: „H halmaz”. Rövidítsük az $\{x|x\subseteq H\}$-t $𝒫(H)$-val. Ekkor a hatványhalmaz-axióma a következő formula:

$(\mathrm{\forall }x)(𝒮et(x)\Rightarrow 𝒮et(𝒫(x)))$

Bourbaki-halmazelmélet

A francia matematikuscsoport által kidolgozott formális-axiomatikus halmazelméletben minden A formula (itt szintén formalizálható tulajdonságra kell gondolnunk) és x változó esetén $𝒞ol{l}_x(A)$ jelöli az $(\mathrm{\exists }y)((x\in y)\iff A(x))$ formulát, melynek jelentése: „az A(x) tulajdonságból halmaz képezhető (éspedig az {x|A(x)} halmaz)”. Ha $𝒞ol{l}_x(A)$ tétel, akkor azt mondjuk, hogy az A formula kollektivizáló az x változóban. A hatványhalmaz-axióma ekkor a következő formula:

$(\mathrm{\forall }x)(𝒞ol{l}_y(y\subseteq x))$

ahol $y\subseteq x$ jelöli az $(\mathrm{\forall }u)((u\in y)\Rightarrow (u\in x))$ formulát.

Hasonló konstrukciók

Ha $X$ egy halmaz, akkor ${𝒫}_{\kappa }(X)=\{U\subseteq X:|U|<\kappa \}$ azt a halmazrendszert jelöli, mely az $X$ halmaz $\kappa$-nál kevesebb elemet tartalmazó részhalmazaiból áll. Például ${𝒫}_3(\{a,b,c\})=\{\mathrm{\varnothing },\{a\},\{b\},\{c\},\{a,b\},\{a,c\},\{b,c\}\}$. A teljes $\{a,b,c\}$ halmaz hiányzik, hiszen nem tartalmaz kevesebb, mint három elemet.

A hatványképzés kiterjeszthető osztályokra is. Itt arra kell vigyázni, hogy valódi osztályok nem állhatnak az $\in$ reláció bal oldalán. Egy K osztály hatványa az az osztály, melynek elemei azok a halmazok, amelyek elemei mind K-beliek. Tehát a hatványhalmaz az osztály részhalmazaiból áll. Valódi osztály hatványhalmaza valódi osztály, mivel egyenként elemei a K elemeiből alkotott egyelemű halmazok, de nem eleme a teljes K osztály. Viszont az üres halmaz eleme.

Történeti adalékok

Georg Cantor, halmazelméletének ellentmondásosságát Russelltől függetlenül saját maga is felismerte. Az általa talált Cantor-antinómia a Cantor-tételből következik. Legyen U az összes halmazok halmaza, azaz bármely H halmazra $H\in U$. A naiv halmazelmélet szerint bármely halmaznak van hatványhalmaza, így U-nak is. Ekkor a Cantor-tétel szerint fennáll a következő egyenlőtlenség: $|U|<|𝒫(U)|\le |U|$, ami ellentmondás.

Az ellentmondás feloldását az NBG szemléletű osztálykalkulusban tehetjük meg. Eszerint, ugyan lehet képezni a $𝒫(U)$ összességet, de mivel Set(U) cáfolható, azaz U nem halmaz így a Cantor-tétel, mely csak halmazokra vonatkozik nem használható fel.

További információk

• Alice és Bob - 19. rész: Alice és Bob ideáljai

Források

• Oliver Deiser: Einführung in die Mengenlehre. Die Mengenlehre Georg Cantors und ihre Axiomatisierung durch Ernst Zermelo. 2., verbesserte und erweiterte Auflage. Springer, Berlin u. a. 2004, Sablon:ISBN.

Bourbaki halmazelméletéről

• Kristóf János, Az analízis logikai alapjai, ELTE jegyzet, 1998.

(A matematika logikai megalapozása Bourbaki szerint, Kristóf János kitűnő tolmácsolásában. A teljes szöveg elektronikus formában itt. Sablon:Wayback)

• Kristóf János, Az analízis elemei I., ELTE jegyzet, 1996.

(A halmazelmélet és az analízis megalapozása Bourbaki szerint. A teljes szöveg elektronikus formában itt. Sablon:Wayback)

• Nikolas Bourbaki, Théorie des Ensembles, de la collection éléments de Mathématique, Hermann, Paris 1970. (gyakran orosz kiadásban: Tyeorija mnozsensztvo)
• Cikk a Bourbaki-csoportról Sablon:Wayback