Võimsus (hulgateooria)

Võimsus ehk kardinaalsus on hulgateoorias hulga elementide arvu mõistet üldistav mõiste, mis on rakendatav ka lõpmatute hulkade puhul.

Lõplike hulkade puhul samastatakse hulga võimsust tema elementide arvuga, mis on naturaalarv. Lõpmatute hulkade võimsuse määratlemiseks on tarvis pisut eeltööd. Järgmised definitsioonid ja järeldused kehtivad ka lõplike hulkade korral.

Võrdvõimsus ja võimsus

Kõigepealt defineeritakse kahe hulga A ja B võrdvõimsuse ehk ekvivalentsuse mõiste:

hulka A nimetatakse hulgaga B võrdvõimsaks ehk ekvivalentseks, kui leidub bijektsioon
f: A -> B. Sel juhul kirjutatakse: |A| = |B| või A~B.

Kui hulk A on hulgaga B võrdvõimas, siis ka funktsiooni f pöördfunktsioon on bijektsioon, seega on ka hulk B hulgaga A võrdvõimas. Lõplikud hulgad on omavahel võrdvõimsad parajasti siis, kui neil on ühepalju elemente.

Hulka, mis on võrdvõimas naturaalarvude hulgaga $\mathbb {N}$ (see on lõpmatu hulk), nimetatakse loenduvaks hulgaks. Hulka, mis on kas loenduv või lõplik, nimetatakse ülimalt loenduvaks hulgaks.

Kardinaalarvud

 Pikemalt artiklis Kardinaalarv

On lihtne näidata, et võrdvõimsus on ekvivalentsusseos. Seetõttu saab anda järgmise definitsiooni:

Hulkade ekvivalentsusklasse võrdvõimsusseose suhtes nimetatakse kardinaalarvudeks.

Alef ($\aleph$) on heebrea tähestiku esimene täht. See varustatakse indeksiga ja saadakse lõpmatute hulkade kardinaalarvude tähiseid.

Kui hulk A on ekvivalentsusklassi (kardinaalarvu) $\aleph$_i element, siis öeldakse, et hulga A võimsus on $\aleph$_i. Seda märgitakse üles nii:

$|A|=\aleph$_i.

n elemendist koosneva lõpliku hulga võimsus samastatakse naturaalarvuga n.

Võib küsida, kas kõik lõpmatud hulgad on võrdvõimsad. Juhul kui see oleks nii, oleksid kõik lõpmatud hulgad loenduvad. Selgub aga, et on lõpmatuid hulki, mis ei ole omavahel võrdvõimsad. Näiteks ei ole naturaalarvude hulk võrdvõimas reaalarvude hulgaga. Et reaalarvude hulk on mitteloenduv, seda saab tõestada Cantori diagonaaltõestuse abil.

Allpool näitame, et erinevaid kardinaalarve on lõpmata palju.

Täieliku järjestuse teoreemi kohaselt saab iga kardinaalarvu samastada vähima temaga võrdvõimsa ordinaalarvuga, sest iga hulk on võrdvõimas mõne ordinaalarvuga.

Võimsuste võrdlus

Selleks et omavahel mittevõrdvõimsaid hulki siiski võrrelda saaks, määratakse kindlaks, millal hulk B on võimsam kui hulk A:

Kui on olemas bijektsioon f hulgalt A hulga B alamhulgale B, siis öeldakse, et hulk A on hulgaga B võrdvõimas või sellest vähem võimas ehk hulk A ei ole võimsam kui hulk B ehk hulga A võimsus (|A|) ei ole suurem kui hulga B võimsus (|B|). Seda märgitakse üles nii: |A| <= |B|.

Hulk A ei ole võimsam kui hulk B parajasti siis, kui leidub injektsioon hulgast A hulka B. Hulk A ei ole võimsam kui hulk B parajasti siis, kui leidub sürjektsioon hulgast B hulgale A.

Hulgad A ja B on võrdvõimsad parajasti siis, kui A ei ole võimsam kui B ja B ei ole võimsam kui A.

Kui on olemas bijektsioon f hulgalt A hulga B alamhulgale, kuid ei leidu bijektsiooni hulgalt A hulgale B, siis öeldakse, et A on vähem võimas kui B ja B on võimsam kui A. Seda märgitakse üles nii: |A| < |B|.

On ilmne, et |A| < |B| parajasti siis, kui |A| <= |B|, kuid mitte |A| = |B|.

Et naturaalarvude hulk moodustab reaalarvude hulga alamhulga, siis:

$\mathbb {R}$ on võimsam kui $\mathbb {N}$, c := |$\mathbb {R}$| > |$\mathbb {N}$|.

Saab näidata, et $\mathbb {R}$ on võrdvõimas hulga $\mathbb {N}$ potentshulgaga.

Saab näidata, et naturaalarvude hulgast vähem võimas hulk on lõplik. Samuti saab näidata, et igal lõpmatul hulgal on alamhulk, mis on võrdvõimas hulgaga $\mathbb {N}$.

Seega on hulga $\mathbb {N}$ võimsus vähim lõpmatu kardinaalarv. Selle tähis on aleph₀:

$\aleph _{0}:=|\mathbb {N} |$.

Kontiinuumhüpotees (CH) ütleb, et ei leidu hulka, mis oleks võimsam kui $\mathbb {N}$, kuid vähem võimas kui $\mathbb {R}$. Tegemist ei ole teoreemiga. Tavaliste hulgateooria aksiomaatikate (näiteks Zermelo-Fraenkeli aksiomaatika koos valikuaksioomiga) puhul ei saa aksioomidest tuletada ei kontiinuumhüpoteesi ega selle eitust.

Eeldusel, et kontiinuumhüpotees on tõene, defineeritakse $\aleph _{1}$ hulga $\mathbb {R}$ võimsusena. See kardinaalarv on võimsuselt järgmine $\aleph _{0}$ järel.

Sel juhul kehtib:

$c=2^{\aleph _{0}}=\aleph _{1}$.

Vaata ka

• Ordinaalarv