Potenssijoukko

Kolmen alkion potenssijoukko sisältää $2^3$ alkiota

Potenssijoukko on joukon kaikkien osajoukkojen joukko. Joukon $A$ potenssijoukkoa merkitään tyypillisesti symboleilla $\mathcal{P}(A)$ tai $2^A$ tai $\operatorname{pot}A$.

Johdanto

Tarkastellaan ensin nelialkioista äärellistä joukkoa $S = \{ a, b, c, d \}$. Joukko-opin mukaan tyhjä joukko $\varnothing$ on yksi osajoukko. Myös yksialkioiset osajoukot

$\{a\}, \{b\}, \{c\} \text{ ja } \{d\}$

ovat joukon $S$ osajoukkoja. Sitten voidaan muodostaa kuusi kaksialkioista osajoukkoa

$\{a,b\}, \{a,c\}, \{a,d\}, \{b,c\}, \{b,d\} \text{ ja } \{c,d\}$

ja neljä kolmialkioista osajoukkoa

$\{a,b,c\}, \{a,b,d\}, \{a,c,d\} \text{ ja } \{b,c,d\}.$

Viimeinen osajoukko on joukko $S = \{ a, b, c, d \}$ itse, sillä joukko-opin mukaan joukko on aina itsensä osajoukko.

Helposti nähdään, että neljän alkion joukosta voidaan muodostaa $16 = 2^4$ osajoukkoa. Muodostettu osajoukkojen joukko koostuu näistä 16 luetelluista osajoukoista ja sitä kutsutaan joukon $S$ potenssijoukoksi. Potenssijoukon koko eli mahtavuus on 16.

Määritelmä

Muodollinen määritelmä: jos $A$ on mielivaltainen joukko, niin on $\mathcal{P}(A) = \{ B \, | \, B \subseteq A \}$.

Mahtavuus

Joukon $S$ mahtavuus voidaan merkitä $card(S)$ tai $|S|$.

Äärellisen joukon potenssijoukon mahtavuus voidaan laskea seuraavasti. Yleisesti voidaan merkitä, montako $k \text{- }$ jäsenistä osajoukkoa voidaan ottaa mahtavuudeltaan $n$ olevasta joukosta:

$\binom{n}{k}=\frac{n!}{k!(n-k)!}.$

Kun lasketaan yhteen tyhjän joukon, kaikki yksialkioiset osajoukot, kaksialkioiset, ..., (n-1)-alkioiset ja joukko itse, saadaan

$\sum_{k=0}^n \binom{n}{k} = \binom{n}{0} + \binom{n}{1} + ... + \binom{n}{n}= (1+1)^n = 2^n.$

Jos äärellisen joukon mahtavuus on $|A|$, niin sen potenssijoukon mahtavuus on kahden potenssi eli $|\mathcal{P}(A)| = 2^{|A|}$ .

Tyhjän joukon potenssijoukko sisältää määritelmän mukaan tyhjän joukon, mutta myös itsensä. Koksa tyhjiä joukkoja on olemassa vain yksi, ei sitä voi esiintyä osajoukkojen joukossa kahdesti. Tyhjässä joukossa ei ole alkioita, joista voidaan muodostaa osajoukkoja. Tällöin on $\mathcal{P}(\varnothing) = \{ \varnothing \}$. Tyhjän joukon mahtavuus on $|\varnothing| = 0$, niin sen potenssijoukon mahtavuus on $|\mathcal{P}(\varnothing)| = 2^{|0|} = 1$.

Numeroituvasti äärettömän joukon potenssijoukon mahtavuus on siten $\mathcal{P}(\N)=2^{\aleph_0}$, jos numeroituvasti ääretömän joukon mahtavuus on $\aleph_0$. Voidaan osoittaa, että $2^{\aleph_0} = |\R|$ eli sama kuin reaalilukujen mahtavuus. Se on suurempi kuin luonnollisten lukujen mahtavuus ja se merkitään $|\R| = \beth_1$. Tällaisen potenssijoukon mahatvuus on ylinumeroituvasti ääretön.

Voidaan todistaa, ettei joukon $S$ ja sen potenssijoukon välillä ei ole bijektiota. Silloin ei joukon $S$ numeroituvuudesta voida päätellä potenssijoukon numeroituvuutta.

Ylinumeroituvien joukkojen potenssijoukot ovat entistä mahtavampia, jolloin esimerkiksi $|\mathcal{P}(\mathcal{P}(\N))| = 2^{\beth_1} = \beth_2$. Potenssijoukosta muodostettu potenssijoukko on edellisiä mahtavampi. Niiden mahtavuutta on ollut tapana merkitä kardinaaleilla $\beth_i$. Nilläkin on suuruusjärjestys

$\beth_1, \beth_2, \beth_3, ...$

Katso myös

• Tyhjä joukko
• Mahtavuus
• Numeroituva joukko
• Ylinumeroituva joukko

Lähteet

• Fuchs, Walter R.: Matematiikka. Suom. Mattila, Pekka. Länsi-Saksa: Kirjayhtymä, 1968.
• Barrow John D.: Lukujen taivas. Suom. Vilikko, Risto. Smedjebacken, Ruotsi: Art House, 1999. ISBN 951-884-231-0.