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 ${\mathcal {P}}(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: ${\mathcal {P}}(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 ${\mathcal {P}}(H)$ rendszer elemei közé tartoznak a nem valódi részhalmazok, így az üres halmaz, és $H$ is. További jelölései: ${\mathfrak {p}}(X),\ 2^{X},\ \mathrm {Pot} (X),\ \Pi (X),\ \wp (X)$ és ${\mathfrak {P}}(X)$.

Példa

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

• nullaelemű részhalmaza az $\emptyset$ ü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 ${\mathcal {P}}(H)={\big \{}\emptyset ,\{a\},\{b\},\{c\},\{a,b\},\{a,c\},\{b,c\},\{a,b,c\}{\big \}}$

További példák:

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

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

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

$\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:

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

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

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

Ez bijekció ${\mathcal {P}}(X)$ és $\{0,1\}^{X}$ között. Ez motiválja a ${\mathcal {P}}(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 ${\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 $|H|$ jelöli egy $H$ halmaz számosságát.

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

Végtelen $X$ halmaz esetén is jelölik $2^{|X|}$-nel a $|{\mathcal {P}}(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 $|{\mathcal {P}}(X)|$ a közvetlenül következő számosság: $\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 $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: $(\forall x)(\exists y)(\forall z)((z\in y)\Leftrightarrow (z\subseteq x))$

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

$(\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 ${\mathcal {C}}oll_{x}(A)$ jelöli az $(\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 ${\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:

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

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

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 $|{\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ó $2^{H}:={\mathcal {P}}(H)$ hatványozásra utaló jelölést.

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

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

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|<|{\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 ${\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

Felhasznált irodalom

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.)

• 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.)

• 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