Moc zbioru

Moc zbioru – własność zbioru, która opisuje jego liczebność. Nieformalnie, moc zbioru jest tym większa im większy jest zbiór. Pojęcie mocy zbioru opiera się na pojęciu równoliczności dwóch zbiorów – zbiory A i B są równoliczne, gdy każdy element zbioru A można połączyć w parę z dokładnie jednym elementem zbioru B, innymi słowy istnieje bijekcja (funkcja różnowartościowa i "na") między zbiorami A i B. Zbiory równoliczne mają tę samą moc. Moce zbiorów są konkretnymi obiektami matematycznymi, nazywanymi liczbami kardynalnymi.

Liczba kardynalna jest naturalnym uogólnieniem liczby elementów zbioru skończonego, w szczególności moc zbioru n–elementowego wynosi dokładnie n.

Georg Cantor, twórca teorii mnogości, określał moc zbioru jako tę własność, którą otrzymamy abstrahując od charakteru elementów zbioru i ich wzajemnych relacji takich, jak np. uporządkowanie.

Zapis

Moc zbioru oznacza się parą pionowych kresek: |A| oznacza moc zbioru A. Jest to ten sam symbol, którym oznacza się wartość bezwzględną liczby rzeczywistej lub moduł liczby zespolonej, ale jego znaczenie zazwyczaj jednoznacznie wynika z kontekstu.
Stosuje się również oznaczenia n(A), card(A), $\overline{\overline A}$ lub # A.

Intuicje

Dla sprawdzenia, czy w grupie przedszkolaków jest więcej chłopców, czy dziewczynek, można użyć dwóch metod. Pierwsza polega na policzeniu z osobna liczby chłopców i liczby dziewczynek i porównaniu obu tych liczb; druga sprowadza się do ustawienia dzieci w pary w ten sposób, by chłopcy stali z dziewczynkami i sprawdzenia, czy bez pary zostaną chłopcy, czy dziewczynki.

Druga metoda ma tę zaletę, że pozwala przenieść pojęcie "tyle samo elementów" na dowolne zbiory, również nieskończone. Co więcej, pozwala precyzyjnie zdefiniować tak "naturalne" i "oczywiste" pojęcia jak zbiór skończony i zbiór nieskończony.

Ustawianie dzieci w pary jest niczym innym, jak określaniem funkcji ze zbioru chłopców do zbioru dziewczynek. Jeżeli każdy chłopiec stoi w parze z jedną dziewczynką i na odwrót, to oczywiście dzieci obu płci jest tyle samo.

Powyższa obserwacja prowadzi do możliwości wprowadzenia następującej definicji równoliczności zbiorów

Zbiory A i B są równoliczne wtedy i tylko wtedy, gdy istnieje między nimi funkcja wzajemnie jednoznaczna.

Zbiory przeliczalne

Wprowadzenie powyższej definicji równoliczności prowadzi do zaskakujących konsekwencji – okazuje się, że w przypadku zbiorów nieskończonych zawodzą intuicje nabyte podczas obcowania ze zbiorami skończonymi. Na przykład:

• Zbiór parzystych liczb naturalnych jest równoliczny ze zbiorem wszystkich liczb naturalnych (innymi słowy, zbiór nieskończony może być równoliczny ze swoim właściwym podzbiorem!) – funkcja wzajemnie jednoznaczna może być opisana, na przykład jako ciąg par {(2,1), (4,2), (6,3), (8,4), ... }
  Podobnie zbiór nieparzystych liczb naturalnych jest równoliczny ze zbiorem wszystkich liczb naturalnych.
• Zbiór liczb pierwszych jest równoliczny ze zbiorem liczb naturalnych (argumentacja podobna jak wyżej)
• Zbiór liczb naturalnych jest równoliczny ze zbiorem liczb całkowitych. Funkcja wzajemnie jednoznaczna między tymi zbiorami może być opisana, na przykład, w postaci ciągu: {(1,0), (2,1), (3,−1), (4,2), (5,−2), (6,3), (7,−3)...}

Zbiory skończone lub równoliczne ze zbiorem liczb naturalnych nazywane są zbiorami przeliczalnymi. Można wykazać, że zbiory liczb wymiernych i algebraicznych są przeliczalne (nieskończone). Ponadto, można wykazać, że dla każdego zbioru nieskończonego istnieje funkcja różnowartościowa ze zbioru liczb naturalnych na jego właściwy podzbiór. To oznacza, że moc zbioru liczb naturalnych jest najmniejszą spośród mocy zbiorów nieskończonych. Liczbę kardynalną odpowiadającą mocy zbioru liczb naturalnych oznacza się hebrajską literą alef z indeksem 0: $\aleph_0$.

Zbiory nieprzeliczalne

Zbiorami nieprzeliczalnymi nazywa się zbiory nieskończone, które nie są przeliczalne. Georg Cantor wykazał, że przedział [0,1] jest równoliczny ze zbiorem liczb rzeczywistych, a następnie, używając metody przekątniowej, udowodnił, że moc przedziału [0,1] (równa mocy zbioru liczb rzeczywistych) jest większa od mocy zbioru liczb naturalnych. Liczbę kardynalną określającą moc zbioru liczb rzeczywistych oznacza się symbolem $\mathfrak{c}$ lub $2^{\aleph_0}$. Można wykazać, że liczb rzeczywistych jest dokładnie tyle, ile podzbiorów zbioru liczb naturalnych, to znaczy zbiór potęgowy zbioru liczb naturalnych, oznaczany symbolem $\mathbf{2}^{\mathbb{N}}$ lub $\mathcal{P}(\mathbb{N})$, jest równoliczny ze zbiorem liczb rzeczywistych (uzasadnia to drugi z wprowadzonych symboli).

W pracy z roku 1906 Gerhard Hessenberg udowodnił twierdzenie (nazwane przez Ernsta Zermelo twierdzeniem Cantora), które mówi, że

Jeśli $X$ jest dowolnym zbiorem, a $\mathcal{P}(X)$ jest jego zbiorem potęgowym, to znaczy rodziną wszystkich jego podzbiorów, to nie istnieje funkcja różnowartościowa ze zbioru $\mathcal{P}(X)$ w zbiór $X$.

Innymi słowy, zbiór potęgowy danego zbioru X jest zawsze większy w sensie mocy od samego zbioru X. Powyższe twierdzenie może służyć jako maszyna do produkowania zbiorów coraz większej mocy – wychodząc od zbioru liczb naturalnych $\mathbb{N}$ zbiory $\mathcal{P}(\mathbb{N}), \mathcal{P}(\mathcal{P}(\mathbb{N})), \mathcal{P}(\mathcal{P}(\mathcal{P}(\mathbb{N}))), \ldots$ są coraz większe w sensie mocy. Innym klasycznym twierdzeniem teorii mnogości, które – w pewnym sensie – mówi o tym, że istnieje nieskończenie wiele rodzajów nieskończoności jest twierdzenie Hartogsa.

Definicja liczby kardynalnej

Jeżeli zbiory A i B są równoliczne, to będziemy pisać w skrócie |A|=|B|. Warto zauważyć, że relacja równoliczności zbiorów ma cechy relacji równoważności. Dokładniej, dla każdych zbiorów A, B, C spełnione są następujące warunki:

• $|A|=|A|$ (każdy zbiór jest równoliczny ze sobą; równoliczność wyznacza np funkcja tożsamościowa $f(x)=x$)
• jeśli $|A|=|B|$, to $|B|=|A|$ (jeśli $f\colon A\to B$ jest bijekcją, to $f^{-1}\colon B\to A$ również)
• jeśli $|A|=|B|$ oraz $|B|=|C|$, to $|A|=|C|$ (jeśli $f\colon A\to B$ i $g\colon B\to C$ są bijekcjami, to $g\circ f\colon A \to C$ również).

Biorąc pod uwagę powyższe cechy relacji równoważności, niektórzy definiują liczby kardynalne jako klasy abstrakcji powyższej relacji równoważności. Jest to jednak definicja poglądowa i nie jest poprawna matematycznie, gdyż klasa wszystkich zbiorów $\mathbb{V}$ jest klasą właściwą (nie istnieje zbiór wszystkich zbiorów, gdyż sam byłby swoim elementem, co prowadzi do sprzeczności – por. paradoks zbioru wszystkich zbiorów), a zatem klasy abstrakcji tej relacji nie byłyby zbiorami, co mogłoby prowadzić do wielu niedogodności z formalnego punktu widzenia.

Współczesne definicje liczby kardynalnej i mocy zbioru korzystają z pojęcia liczby porządkowej:

• Liczbę porządkową $\lambda$ nazywamy liczbą kardynalną, gdy nie jest ona równoliczna z liczbą porządkową od siebie mniejszą.
• Mocą zbioru $X$ nazywamy najmniejszą liczbę porządkową równoliczną ze zbiorem $X$. Liczbę tę oznaczamy symbolem $|X|$.

Należy zwrócić uwagę, że teraz symbol |X| może występować samodzielnie, w oderwaniu od zapisu np. "|X|=|Y|". W dalszej części artykułu będzie wynikało z kontekstu, o który zapis chodzi – nie powinno to prowadzić do nieporozumień.

Jeśli $X$ jest zbiorem, to $|X|$ jest najmniejszym elementem klasy

$A=\{\alpha\in \mathbf{On}\colon\, |X|=\alpha\}$,

a zatem jest liczbą kardynalną, gdyż żadna liczba porządkowa $\beta<|X|$ nie jest równoliczna z $|X|$.

Uwaga: Powyższa definicja mocy zbioru wymaga aksjomatu wyboru – niepustość klasy A gwarantuje twierdzenie Zermelo o dobrym uporządkowaniu oraz fakt, iż każdy zbiór dobrze uporządkowany jest porządkowo izomorficzny z pewną liczbą porządkową. Bez aksjomatu wyboru powyższą definicję można stosować jedynie do zbiorów dobrze uporządkowanych.

Hierarchia liczb kardynalnych

Mówi się, że zbiór $X$ jest mocy nie większej niż zbiór $Y$, gdy istnieje funkcja różnowartościowa określona na $X$ o wartościach w $Y$. Zdanie to można zapisać krótko $|X|\leqslant |Y|$. Oczywiście,

$|X|\leqslant |Y| \wedge |Y|\leqslant |X| \iff |X|=|Y|$.

Okazuje się, że możliwość porównywania mocy dowolnych zbiorów jest równoważna aksjomatowi wyboru, to znaczy następujące zdanie (tzw. prawo dychotomii) jest z nim równoważne:

Dla dowolnych zbiorów $X$ i $Y$ prawdziwa jest alternatywa $|X|\leqslant |Y|$ lub $|Y|\leqslant |X|$.

Po odkryciu faktu, iż zbiór liczb rzeczywistych jest większej mocy od zbioru liczb naturalnych, Cantor sfomułował przypuszczenie, że nie istnieje taki podzbiór $X$ zbioru liczb rzeczywistych, że

$\aleph_0<|X|<2^{\aleph_0}$.

Przypuszczenia tego, zwanego dziś hipotezą continuum, nie potrafił jednak dowieść. Problem pozostawał nierozwiązany aż do roku 1963, gdy Paul Cohen udowodnił, że zaprzeczenie hipotezy continuum jest niesprzeczne z aksjomatami teorii mnogości. W połączeniu z opublikowanym w 1940 wynikiem Kurta Gödla, że hipoteza continuum jest niesprzeczna z aksjomatami, wynik Cohena oznacza niezależność hipotezy continuum od aksjomatów teorii mnogości. Można zatem przyjąć hipotezę continuum jako nowy aksjomat, albo – również poprawnie – przyjąć jej zaprzeczenie jako nowy aksjomat. Otrzymuje się wówczas różne, ale w obu przypadkach poprawne, wewnętrznie niesprzeczne teorie (pod założeniem niesprzeczności ZFC).

Arytmetyka liczb kardynalnych

Opierając się na pojęciu równoliczności zbiorów, można zdefiniować działania na liczbach kardynalnych: dodawanie, mnożenie, potęgowanie. Pozwala to zbudować arytmetykę liczb kardynalnych.

Niech $X$ i $Y$ będą dowolnymi zbiorami o liczbach kardynalnych, odpowiednio, $a=|X|$ i $b=|Y|$. Definiuje się następujące liczby kardynalne:

• sumę liczb kardynalnych $a+b$ jako moc zbioru

$(X\times\{0\})\cup (Y\times \{1\})$.

• iloczyn liczb kardynalnych $a$ · $b$ jako moc iloczynu kartezjańskiego $X$ × $Y$.
• potęgę liczb kardynalnych $a^b$ jako moc zbioru wszystkich funkcji ze zbioru $Y$ o wartościach w zbiorze $X$.

W przypadku operowania na liczbach kardynalnych skończonych, tak określone działania są tożsame ze "zwykłymi" działaniami arytmetycznymi na liczbach naturalnych. Własności działań na liczbach kardynalnych nieskończonych różnią się istotnie od własności "zwykłych" działań arytmetycznych. Na przykład, jeśli $b$ jest nieskończona i $a<b$, to $a+b=b$, a jeśli ponadto $a$ jest niezerowa, to

$a\cdot b=b$.

Bibliografia

1. Aleksander Błaszczyk, Sławomir Turek: Teoria Mnogości. Warszawa: PWN, 2007. 
2. Wacław Sierpiński: Cardinal and ordinal numbers. Wyd. drugie poprawione. Warszawa: PWN, 1965. 

Zobacz też

• duże liczby kardynalne,
• regularna liczba kardynalna,
• teoria PCF,
• zbiór skończony.