Moc zbioru

teoria mnogości: uogólnienie pojęcia liczebności zbioru na dowolne zbiory (też nieskończone)

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 (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[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 -elementowego jest to liczba naturalna Tym samym moce -elementowych zbiórów liczby naturalnych wraz z zeremskoń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

edytuj

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

edytuj

Zbiory skończone

edytuj

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

edytuj

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

edytuj

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[3] Gerhard Hessenberg udowodnił twierdzenie (nazwane przez Ernsta Zermela twierdzeniem Cantora[4]), 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

edytuj

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], 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

edytuj

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[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

edytuj

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ż

edytuj
  1. Nie istnieje zbiór wszystkich zbiorów, gdyż on sam byłby swoim elementem, co prowadziłoby do sprzeczności – por. paradoks zbioru wszystkich zbiorów.

Przypisy

edytuj
  1. Liczba kardynalna, [w:] Encyklopedia PWN [online], Wydawnictwo Naukowe PWN [dostęp 2021-07-22].
  2. Równoliczność zbiorów, [w:] Encyklopedia PWN [online], Wydawnictwo Naukowe PWN [dostęp 2021-07-22].
  3. Gerhard Hessenberg: Grundbegriffe der Mengenlehre, Abhandlungen der Friesschen Schule I, No. 4, Göttingen (1906) s. 41.
  4. Ernst Zermelo: Untersuchungen über die Grundlagen der Mengenlehre, „Math. Annalen” 65 (1908) s. 276.
  5. Paul J. Cohen. The Independence of the Continuum Hypothesis. „Proceedings of the National Academy of Sciences of the United States of America”. 50 (6), s. 1143–1148, December 15, 1963. DOI: 10.1073/pnas.50.6.1143. PMID: 16578557. 
  6. Paul J. Cohen. The Independence of the Continuum Hypothesis, II. „Proceedings of the National Academy of Sciences of the United States of America”. 51 (1), s. 105–110, January 15, 1964. DOI: 10.1073/pnas.51.1.105. PMID: 16591132. 

Bibliografia

edytuj
  • 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

edytuj