Moc zbioru

Moc zbioru, liczba kardynalna – uogólnienie pojęcia liczebności zbioru na dowolne zbiory, także nieskończone. 
Moc zbioru liczb naturalnych oznacza się symbolem  (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  i  są równoliczne, gdy istnieje bijekcja (funkcja różnowartościowa i „na”) między zbiorami  i  Obrazowo mówiąc, gdy każdy element zbioru  można połączyć w parę z dokładnie jednym elementem zbioru  i odwrotnie. Łą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 -elementowego jest to liczba naturalna  Tym samym moce -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  oznacza się symbolem  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    lub

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 
 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  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ą  mają dodatnią i zarazem ułamek  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:  (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  lub  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  lub  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 Zermela twierdzeniem Cantora), które mówi, że
 Jeśli  jest dowolnym zbiorem, a  jest jego zbiorem potęgowym, to znaczy rodziną wszystkich jego podzbiorów, to nie istnieje funkcja różnowartościowa ze zbioru  w zbiór 
Innymi słowy, zbiór potęgowy danego zbioru  jest zawsze większy w sensie mocy od samego zbioru  Powyższe twierdzenie może służyć jako maszyna do produkowania zbiorów coraz większej mocy – wychodząc od zbioru liczb naturalnych  zbiory  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  i  zapisuje się  Relacja równoliczności zbiorów ma cechy relacji równoważności, tzn. dla każdych zbiorów  zachodzą warunki:
  (każdy zbiór jest równoliczny ze sobą; równoliczność wyznacza np. funkcja tożsamościowa )
 jeśli  to  (jeśli  jest bijekcją, to  również)
 jeśli  oraz  to  (jeśli  i  są bijekcjami, to  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  jest klasą właściwą, 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ą  nazywamy liczbą kardynalną, gdy nie jest ona równoliczna z liczbą porządkową od siebie mniejszą.
 Mocą zbioru  nazywamy najmniejszą liczbę porządkową równoliczną ze zbiorem  Liczbę tę oznaczamy symbolem 

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

a zatem jest liczbą kardynalną, gdyż żadna liczba porządkowa  nie jest równoliczna z 

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

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  i  prawdziwa jest alternatywa  lub 

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  zbioru liczb rzeczywistych, że
 

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 (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  i  będą dowolnymi zbiorami o liczbach kardynalnych, odpowiednio,  i  Definiuje się następujące liczby kardynalne:
 sumę liczb kardynalnych  jako moc zbioru
 
 iloczyn liczb kardynalnych   jako moc iloczynu kartezjańskiego 
 potęgę liczb kardynalnych  jako moc zbioru wszystkich funkcji ze zbioru  o wartościach w zbiorze 

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  jest nieskończona i  to  a jeśli ponadto  jest niezerowa, to

Zobacz też 
 duże liczby kardynalne
 regularna liczba kardynalna
 teoria PCF

Uwagi

Przypisy

Bibliografia

Linki zewnętrzne