Moc zbioru

Moc zbioru, liczba kardynalna – uogólnienie pojęcia liczebności zbioru na dowolne zbiory, także nieskończone^[1]. Moc zbioru liczb naturalnych oznacza się symbolem ${\displaystyle \aleph _{0}}$ (czytanym alef zero z hebrajską literą alef i indeksem).

Pojęcie mocy zbioru opiera się na pojęciu równoliczności dwóch zbiorów: zbiory ${\displaystyle A}$ i ${\displaystyle B}$ są równoliczne, gdy istnieje bijekcja (funkcja różnowartościowa i „na”) między zbiorami ${\displaystyle A}$ i ${\displaystyle B.}$ Obrazowo mówiąc, gdy każdy element zbioru ${\displaystyle A}$ można połączyć w parę z dokładnie jednym elementem zbioru ${\displaystyle B}$ i odwrotnie^[2]. Łączenie elementów w pary jest jedynym sposobem „porównania” zbiorów nieskończonych, nie można – tak jak dla zbiorów skończonych – policzyć elementów obu zbiorów.

Zbiory mają tę samą moc wtedy i tylko wtedy, gdy są równoliczne.

Mocą zbioru skończonego jest liczba jego elementów: dla zbioru ${\displaystyle n}$-elementowego jest to liczba naturalna ${\displaystyle n.}$ Tym samym moce ${\displaystyle n}$-elementowych zbiórów liczby naturalnych wraz z zerem są skończonymi liczbami kardynalnymi. Moce zbiorów nieskończonych są nieskończonymi liczbami kardynalnymi.

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.

Oznaczenia

Moc zbioru ${\displaystyle A}$ oznacza się symbolem ${\displaystyle |A|.}$ Wprawdzie tym samym symbolem oznacza się wartość bezwzględną liczby rzeczywistej i moduł liczby zespolonej, ale jego znaczenie zazwyczaj jednoznacznie wynika z kontekstu.

Stosuje się również oznaczenia ${\displaystyle n(A),}$ ${\displaystyle \mathrm {card} (A),}$ ${\displaystyle {\overset {\mbox{=}}{A}}}$ lub ${\displaystyle \#A.}$

Przykłady

Zbiory skończone

Dla zbioru skończonego, to znaczy niebędącego równolicznym z żadnym swoim podzbiorem właściwym, jego liczbą kardynalną jest liczba elementów należących do tego zbioru.

Zbiory nieskończone przeliczalne

Zbiory nieskończone przeliczalne, tj. takie, które są równoliczne ze zbiorem liczb naturalnych ${\displaystyle \mathbb {N} {:}}$

• Zbiór parzystych liczb naturalnych jest równoliczny ze zbiorem wszystkich liczb naturalnych – 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)...}
• Zbiór liczb wymiernych jest równoliczny ze zbiorem liczb naturalnych. Niech każdemu ułamkowi ${\displaystyle x/y}$ odpowiada punkt o współrzędnych (x, y) w kartezjańskim układzie współrzędnych na płaszczyźnie, gdzie x i y są całkowite. Funkcję wzajemnie jednoznaczną można skonstruować numerując „spiralnie” punkty o współrzędnych całkowitych kolejnymi liczbami naturalnymi: (0, 0), (1, 0), (1, −1), (0, −1), (−1, −1), (−1, 0), (−1, 1), (0, 1), (1, 1), (2, 1), (2, 0), (2, −1)..., przy czym numerujemy tylko te punkty (x,y), które współrzędną ${\displaystyle y}$ mają dodatnią i zarazem ułamek ${\displaystyle x/y}$ jest nieskracalny.
• Zbiór liczb algebraicznych także jest przeliczalny (nieskończony).

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: ${\displaystyle \aleph _{0}}$ (alef zero).

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 ${\displaystyle {\mathfrak {c}}}$ lub ${\displaystyle 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 ${\displaystyle \mathbf {2} ^{\mathbb {N} }}$ lub ${\displaystyle {\mathcal {P}}(\mathbb {N} ),}$ jest równoliczny ze zbiorem liczb rzeczywistych (uzasadnia to drugi z wprowadzonych symboli).

W pracy z roku 1906^[3] Gerhard Hessenberg udowodnił twierdzenie (nazwane przez Ernsta Zermela twierdzeniem Cantora^[4]), które mówi, że

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

Innymi słowy, zbiór potęgowy danego zbioru ${\displaystyle X}$ jest zawsze większy w sensie mocy od samego zbioru ${\displaystyle 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 ${\displaystyle \mathbb {N} }$ zbiory ${\displaystyle {\mathcal {P}}(\mathbb {N} ),{\mathcal {P}}({\mathcal {P}}(\mathbb {N} )),{\mathcal {P}}({\mathcal {P}}({\mathcal {P}}(\mathbb {N} ))),\dots }$ 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

Równoliczność zbiorów ${\displaystyle A}$ i ${\displaystyle B}$ zapisuje się ${\displaystyle |A|=|B|.}$ Relacja równoliczności zbiorów ma cechy relacji równoważności, tzn. dla każdych zbiorów ${\displaystyle A,B,C}$ zachodzą warunki:

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

Z uwagi na powyższe własności, niekiedy definiuje się liczby kardynalne jako klasy abstrakcji powyższej relacji równoważności. Ściśle biorąc, ta poglądowa definicja nie jest jednak poprawna matematycznie, gdyż klasa wszystkich zbiorów ${\displaystyle \mathbb {V} }$ jest klasą właściwą^[a], a zatem klasy abstrakcji tej relacji nie są zbiorami – traktowanie ich jako zbiory 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ą ${\displaystyle \lambda }$ nazywamy liczbą kardynalną, gdy nie jest ona równoliczna z liczbą porządkową od siebie mniejszą.
• Mocą zbioru ${\displaystyle X}$ nazywamy najmniejszą liczbę porządkową równoliczną ze zbiorem ${\displaystyle X.}$ Liczbę tę oznaczamy symbolem ${\displaystyle |X|.}$

Należy zwrócić uwagę, że teraz symbol ${\displaystyle |X|}$ może występować samodzielnie, w oderwaniu od zapisu np. „${\displaystyle |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 ${\displaystyle X}$ jest zbiorem, to ${\displaystyle |X|}$ jest najmniejszym elementem klasy

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

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

Uwaga: Powyższa definicja mocy zbioru wymaga aksjomatu wyboru – niepustość klasy ${\displaystyle A}$ gwarantuje twierdzenie Zermela 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 ${\displaystyle X}$ jest mocy nie większej niż zbiór ${\displaystyle Y,}$ gdy istnieje funkcja różnowartościowa określona na ${\displaystyle X}$ o wartościach w ${\displaystyle Y.}$ Zdanie to można zapisać krótko ${\displaystyle |X|\leqslant |Y|.}$ Przy tym,

${\displaystyle |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 ${\displaystyle X}$ i ${\displaystyle Y}$ prawdziwa jest alternatywa ${\displaystyle |X|\leqslant |Y|}$ lub ${\displaystyle |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 ${\displaystyle X}$ zbioru liczb rzeczywistych, że

${\displaystyle \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^[5][6]. 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 (o ile niesprzeczna jest sama teoria ZF).

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 ${\displaystyle X}$ i ${\displaystyle Y}$ będą dowolnymi zbiorami o liczbach kardynalnych, odpowiednio, ${\displaystyle a=|X|}$ i ${\displaystyle b=|Y|.}$ Definiuje się następujące liczby kardynalne:

• sumę liczb kardynalnych ${\displaystyle a+b}$ jako moc zbioru

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

• iloczyn liczb kardynalnych ${\displaystyle a\cdot b}$ jako moc iloczynu kartezjańskiego ${\displaystyle X\times Y.}$
• potęgę liczb kardynalnych ${\displaystyle a^{b}}$ jako moc zbioru wszystkich funkcji ze zbioru ${\displaystyle Y}$ o wartościach w zbiorze ${\displaystyle 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 ${\displaystyle b}$ jest nieskończona i ${\displaystyle a<b,}$ to ${\displaystyle a+b=b,}$ a jeśli ponadto ${\displaystyle a}$ jest niezerowa, to

${\displaystyle a\cdot b=b.}$

Zobacz też

• duże liczby kardynalne
• regularna liczba kardynalna
• teoria PCF

Uwagi

Przypisy

Bibliografia

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

Linki zewnętrzne

• TomaszT. Miller TomaszT., Liczby kardynalne | Zacznijmy od zera #7, [w:] Copernicus Center for Interdisciplinary Studies [online], YouTube, 14 grudnia 2021  (pol.).