Hatványhalmaz

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 ${\displaystyle H}$ halmaz, akkor ${\displaystyle {\mathcal {P}}(H)}$-val jelöljük és a ${\displaystyle H}$ halmaz hatványhalmazának nevezzük a ${\displaystyle H}$ összes részhalmazainak halmazát. Vagy másképpen: ${\displaystyle {\mathcal {P}}(H):=\{x\mid x\subseteq H\}}$ ahol a ${\displaystyle \subseteq }$ szimbólum a részhalmaz-reláció jele.

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

Példa

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

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

Tehát ${\displaystyle {\mathcal {P}}(H)={\big \{}\emptyset ,\{a\},\{b\},\{c\},\{a,b\},\{a,c\},\{b,c\},\{a,b,c\}{\big \}}}$

További példák:

• ${\displaystyle {\mathcal {P}}(\emptyset )=\{\emptyset \}}$
• ${\displaystyle {\mathcal {P}}(\{a\})={\bigl \{}\emptyset ,\{a\}{\bigr \}}}$
• ${\displaystyle {\mathcal {P}}(\{a,b\})={\bigl \{}\emptyset ,\{a\},\{b\},\{a,b\}{\bigr \}}}$
• ${\displaystyle {\mathcal {P}}({\mathcal {P}}(\emptyset ))={\bigl \{}\emptyset ,\{\emptyset \}{\bigr \}}}$
• ${\displaystyle {\mathcal {P}}({\mathcal {P}}(\{a\}))={\bigl \{}\emptyset ,\{\emptyset \},\{\{a\}\},\{\emptyset ,\{a\}\}{\bigr \}}}$

Egy halmazrendszer, például egy topológia vagy σ-algebra az alapjukul szolgáló ${\displaystyle X}$ tér, mint ponthalmaz ${\displaystyle {\mathcal {P}}(X)}$ hatványhalmazának részhalmaza, azaz ${\displaystyle {\mathcal {P}}({\mathcal {P}}(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 ${\displaystyle |{\mathcal {P}}(H)|=2^{n}}$.

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

• Tétel – (Cantor-tétel) – Bármely H halmaz esetén ${\displaystyle {\mathcal {P}}(H)}$ számossága nagyobb H számosságánál.

Jelben: ${\displaystyle |{\mathcal {P}}(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: ${\displaystyle |{\mathcal {P}}(\mathbb {N} )|=|\mathbb {R} |}$.

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

• Állítás – Ha H halmaz, akkor a
• ${\displaystyle ({\mathcal {P}}(H),\cup )}$ és ${\displaystyle ({\mathcal {P}}(H),\cap )}$ (azaz rendre az unióval és a metszettel, mint műveletekkel ellátva) egységelemes, zéróelemes félcsoportok
• ${\displaystyle {\mathcal {P}}(H)}$ a ${\displaystyle \cup }$-val és ${\displaystyle \cap }$-val mint műveletekkel ellátva Boole-algebrát alkot
• ${\displaystyle {\mathcal {P}}(H)}$ a ${\displaystyle \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 ${\displaystyle {\mathcal {P}}(H)}$ hatványhalmaz halmazgyűrű, sőt ${\displaystyle \sigma }$-algebra (szigma-algebra).

Struktúrája

A ${\displaystyle \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 ${\displaystyle \emptyset }$, a legnagyobb a teljes halmaz.

A ${\displaystyle ({\mathcal {P}}(X),\subseteq )}$ részben rendezés teljes háló. Ez azt jelenti, hogy ${\displaystyle {\mathcal {P}}(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 ${\displaystyle T\subseteq {\mathcal {P}}(X)}$, akkor:

${\displaystyle \inf(T)=\bigcap _{M\in T}M\quad {\text{ és }}\quad \mathrm {sup} (T)=\bigcup _{M\in T}M.}$

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

${\displaystyle \inf(\emptyset )=X\quad {\text{ és }}\quad \sup(\emptyset )=\emptyset .}$

Ha hozzávesszük a komplementerképzést, mint ${\displaystyle {}^{\mathrm {c} }:{\mathcal {P}}(X)\rightarrow {\mathcal {P}}(X)}$, akkor ${\displaystyle ({\mathcal {P}}(X),\cap ,\cup ,^{\mathrm {c} },\emptyset ,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 ${\displaystyle {\mathcal {P}}(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 ${\displaystyle X}$, akkor minden ${\displaystyle T\subseteq X}$ részhalmazhoz hozzárendelhető egy ${\displaystyle \chi _{T}\colon X\to \{0,1\}}$ karakterisztikus függvény, amelyre:

${\displaystyle \chi _{T}(x):={\begin{cases}1,&x\in T\\0,&x\not \in T\end{cases}}}$

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

Az ${\displaystyle {\mathcal {P}}(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 ${\displaystyle |H|}$ jelöli egy ${\displaystyle H}$ halmaz számosságát.

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

Végtelen ${\displaystyle X}$ halmaz esetén is jelölik ${\displaystyle 2^{|X|}}$-nel a ${\displaystyle |{\mathcal {P}}(X)|=\left|2^{X}\right|}$ hatványhalmaz számosságát. Az általánosított kontinuumhipotézis szerint, ha az ${\displaystyle X}$ halmaz végtelen, akkor az ${\displaystyle |X|}$ számosság után az ${\displaystyle |{\mathcal {P}}(X)|}$ a közvetlenül következő számosság: ${\displaystyle \mathrm {GCH} \implies (|X|<|Y|\implies |{\mathcal {P}}(X)|\leq |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 ${\displaystyle x\subseteq H}$ kijelentésből képezett ${\displaystyle \{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: ${\displaystyle (\forall x)(\exists y)(\forall z)((z\in y)\Leftrightarrow (z\subseteq x))}$

ahol ${\displaystyle z\subseteq x}$ jelöli az ${\displaystyle (\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 ${\displaystyle (\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 ${\displaystyle \{x|x\subseteq H\}}$-t ${\displaystyle {\mathcal {P}}(H)}$-val. Ekkor a hatványhalmaz-axióma a következő formula:

${\displaystyle (\forall x)({\mathcal {S}}et(x)\Rightarrow {\mathcal {S}}et({\mathcal {P}}(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 ${\displaystyle {\mathcal {C}}oll_{x}(A)}$ jelöli az ${\displaystyle (\exists y)((x\in y)\Leftrightarrow A(x))}$ formulát, melynek jelentése: „az A(x) tulajdonságból halmaz képezhető (éspedig az {x|A(x)} halmaz)”. Ha ${\displaystyle {\mathcal {C}}oll_{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:

${\displaystyle (\forall x)({\mathcal {C}}oll_{y}(y\subseteq x))}$

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

Hasonló konstrukciók

Ha ${\displaystyle X}$ egy halmaz, akkor ${\displaystyle {\mathcal {P}}_{\kappa }(X)=\{U\subseteq X:|U|<\kappa \}}$ azt a halmazrendszert jelöli, mely az ${\displaystyle X}$ halmaz ${\displaystyle \kappa }$-nál kevesebb elemet tartalmazó részhalmazaiból áll. Például ${\displaystyle {\mathcal {P}}_{3}(\{a,b,c\})=\{\emptyset ,\{a\},\{b\},\{c\},\{a,b\},\{a,c\},\{b,c\}\}}$. A teljes ${\displaystyle \{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 ${\displaystyle \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 ${\displaystyle 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: ${\displaystyle |U|<|{\mathcal {P}}(U)|\leq |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 ${\displaystyle {\mathcal {P}}(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, ISBN 3-540-20401-6.

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. Archiválva 2005. február 4-i dátummal a Wayback Machine-ben)

• 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. Archiválva 2005. február 4-i dátummal a Wayback Machine-ben)

• 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 Archiválva 2004. december 7-i dátummal a Wayback Machine-ben

Fordítás

Ez a szócikk részben vagy egészben a Potenzmenge című német Wikipédia-szócikk fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.