Tekst źródłowy strony Moc zbioru

{{Spis treści}}{{Dopracować|więcej przypisów=2024-12}}
'''Moc zbioru, liczba kardynalna''' – uogólnienie pojęcia liczebności [[Zbiór|zbioru]] na dowolne zbiory, także nieskończone<ref>{{Encyklopedia PWN | tytuł = Liczba kardynalna | id = 3932354 | data dostępu = 2021-07-22 }}</ref>.  

Pojęcie mocy zbioru opiera się na pojęciu '''równoliczności''' dwóch zbiorów: zbiory <math>A</math> i <math>B</math> są równoliczne, gdy istnieje [[Funkcja wzajemnie jednoznaczna|bijekcja]] ([[funkcja różnowartościowa]] i [[Funkcja „na”|„na”]]) między zbiorami <math>A</math> i <math>B.</math> Obrazowo mówiąc, gdy każdy element zbioru <math>A</math> można połączyć w parę z dokładnie jednym elementem zbioru <math>B</math> i odwrotnie<ref>{{Encyklopedia PWN | tytuł = Równoliczność zbiorów | id = 3969531 | data dostępu = 2021-07-22 }}</ref>. Łą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. 

<!--[[Klasa (matematyka)|klasy]] zbiorów wzajemnie równolicznych. -->
Mocą [[Zbiór skończony|zbioru skończonego]] jest liczba jego elementów: dla zbioru <math>n</math>-elementowego jest to liczba naturalna <math>n.</math> Tym samym moce <math>n</math>-elementowych zbiorów [[liczby naturalne|liczby naturalnych]] wraz z [[zero|zerem]] są ''skończonymi liczbami kardynalnymi''. Moce zbiorów nieskończonych są ''nieskończonymi liczbami kardynalnymi''.

[[Georg Cantor]], twórca [[Teoria mnogości|teorii mnogości]], określał moc zbioru jako tę własność, którą otrzymamy abstrahując od charakteru elementów zbioru i ich wzajemnych [[Relacja (matematyka)|relacji]] takich, jak np. [[częściowy porządek|uporządkowanie]].

== Oznaczenia ==
Moc zbioru <math>A</math> oznacza się symbolem <math>|A|.</math> Wprawdzie tym samym symbolem oznacza się [[Wartość bezwzględna|wartość bezwzględną]] [[liczby rzeczywiste]]j i [[Liczby zespolone#Moduł|moduł liczby zespolonej]], ale jego znaczenie zazwyczaj jednoznacznie wynika z kontekstu.

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

== Przykłady ==
=== Zbiory skończone ===
Dla [[Zbiór skończony|zbioru skończonego]], to znaczy niebędącego równolicznym z żadnym swoim [[Podzbiór|podzbiorem właściwym]], jego liczbą kardynalną jest liczba elementów należących do tego zbioru.

=== Zbiory nieskończone przeliczalne ===
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ą [[Alef|literą alef]] z indeksem 0: <math>\aleph_0</math> ([[Skala alefów|alef zero]]).

Zbiory nieskończone '''[[zbiór przeliczalny|przeliczalne]]''' to takie, które są równoliczne ze zbiorem [[liczby naturalne|liczb naturalnych]] <math>\mathbb{N},</math> czyli są mocy <math>\aleph_0{:}</math>
* 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), ...}<br />Podobnie zbiór nieparzystych liczb naturalnych jest równoliczny ze zbiorem wszystkich liczb naturalnych.
* Zbiór [[Liczby pierwsze|liczb pierwszych]] jest równoliczny ze zbiorem liczb naturalnych (argumentacja podobna jak wyżej)
* Zbiór liczb naturalnych jest równoliczny ze zbiorem [[liczby całkowite|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 [[liczby wymierne|liczb wymiernych]] jest równoliczny ze zbiorem liczb naturalnych. Niech każdemu ułamkowi <math>x/y</math> odpowiada punkt o współrzędnych (x, y) w [[Układ współrzędnych kartezjańskich|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ą <math>y</math> mają dodatnią i zarazem ułamek <math>x/y</math> jest nieskracalny.
* Zbiór [[liczby algebraiczne|liczb algebraicznych]] także jest przeliczalny (nieskończony).

=== Zbiory nieprzeliczalne ===
[[Zbiór nieprzeliczalny|Zbiorami nieprzeliczalnymi]] nazywa się zbiory nieskończone, które nie są przeliczalne. [[Georg Cantor]] wykazał, że przedział [0,1] jest równoliczny ze zbiorem [[liczby rzeczywiste|liczb rzeczywistych]], a następnie, używając [[metoda przekątniowa|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 ([[Continuum (teoria mnogości)|continuum]]) oznacza się symbolem <math>\mathfrak{c}</math> lub <math>2^{\aleph_0}.</math> 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 <math>\mathbf{2}^{\mathbb{N}}</math> lub <math>\mathcal{P}(\mathbb{N}),</math> jest równoliczny ze zbiorem liczb rzeczywistych (uzasadnia to drugi z wprowadzonych symboli).

W pracy z roku 1906<ref>Gerhard Hessenberg: ''Grundbegriffe der Mengenlehre, Abhandlungen der Friesschen Schule I'', No. 4, Göttingen (1906) s. 41.</ref> [[Gerhard Hessenberg]] udowodnił twierdzenie (nazwane przez [[Ernst Zermelo|Ernsta Zermela]] ''[[twierdzenie Cantora|twierdzeniem Cantora]]''<ref>Ernst Zermelo: ''Untersuchungen über die Grundlagen der Mengenlehre'', „Math. Annalen” 65 (1908) s. 276.</ref>), które mówi, że
: Jeśli <math>X</math> jest dowolnym zbiorem, a <math>\mathcal{P}(X)</math> jest jego [[zbiór potęgowy|zbiorem potęgowym]], to znaczy rodziną wszystkich jego podzbiorów, to '''nie istnieje''' funkcja różnowartościowa ze zbioru <math>\mathcal{P}(X)</math> w zbiór <math>X.</math>
Innymi słowy, zbiór potęgowy danego zbioru <math>X</math> jest zawsze większy w sensie mocy od samego zbioru <math>X.</math> Powyższe twierdzenie może służyć jako maszyna do ''produkowania'' zbiorów coraz większej mocy – wychodząc od zbioru liczb naturalnych <math>\mathbb{N}</math> zbiory <math>\mathcal{P}(\mathbb{N}), \mathcal{P}(\mathcal{P}(\mathbb{N})), \mathcal{P}(\mathcal{P}(\mathcal{P}(\mathbb{N}))), \dots</math> 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 (teoria mnogości)|twierdzenie Hartogsa]].

== Definicja liczby kardynalnej ==
Równoliczność zbiorów <math>A</math> i <math>B</math> zapisuje się <math>|A|=|B|.</math> Relacja równoliczności zbiorów ma cechy [[relacja równoważności|relacji równoważności]], tzn. dla każdych zbiorów <math>A, B, C</math> zachodzą warunki:
* <math>|A|=|A|</math> (każdy zbiór jest równoliczny ze sobą; równoliczność wyznacza np. funkcja tożsamościowa <math>f(x)=x</math>)
* jeśli <math>|A|=|B|,</math> to <math>|B|=|A|</math> (jeśli <math>f\colon A\to B</math> jest bijekcją, to <math>f^{-1}\colon B\to A</math> również)
* jeśli <math>|A|=|B|</math> oraz <math>|B|=|C|,</math> to <math>|A|=|C|</math> (jeśli <math>f\colon A\to B</math> i <math>g\colon B\to C</math> są bijekcjami, to <math>g\circ f\colon A \to C</math> również).

Z uwagi na powyższe własności, niekiedy definiuje się liczby kardynalne jako [[Relacja równoważności#Klasy abstrakcji|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 <math>\mathbb{V}</math> jest [[Klasa (matematyka)#Teoria klas Kelleya-Morse'a|klasą właściwą]]<ref group="uwaga">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]].</ref>, 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ądkowe]]j:
* Liczbę porządkową <math>\lambda</math> nazywamy '''liczbą kardynalną''', gdy nie jest ona równoliczna z liczbą porządkową od siebie mniejszą.
* Mocą zbioru <math>X</math> nazywamy najmniejszą liczbę porządkową równoliczną ze zbiorem <math>X.</math> Liczbę tę oznaczamy symbolem <math>|X|.</math>

Należy zwrócić uwagę, że teraz symbol <math>|X|</math> może występować samodzielnie, w oderwaniu od zapisu np. „<math>|X|=|Y|</math>”. 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 <math>X</math> jest zbiorem, to <math>|X|</math> jest najmniejszym elementem klasy
: <math>A=\{\alpha\in \mathbf{On}\colon\, |X|=\alpha\},</math>

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

'''Uwaga''': Powyższa definicja mocy zbioru wymaga [[aksjomat wyboru|aksjomatu wyboru]] – niepustość klasy <math>A</math> gwarantuje [[twierdzenie Zermela]] o dobrym uporządkowaniu oraz fakt, iż każdy [[dobry porządek|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 ==
{{Zobacz też|skala alefów|skala betów|hipoteza continuum|twierdzenie Hartogsa (teoria mnogości)}}
Mówi się, że zbiór <math>X</math> jest mocy nie większej niż zbiór <math>Y,</math> gdy istnieje funkcja różnowartościowa określona na <math>X</math> o wartościach w <math>Y.</math> Zdanie to można zapisać krótko <math>|X|\leqslant |Y|.</math>
Przy tym,
: <math>|X|\leqslant |Y| \wedge |Y|\leqslant |X| \iff |X|=|Y|.</math>

Okazuje się, że możliwość porównywania mocy dowolnych zbiorów jest równoważna [[aksjomat wyboru|aksjomatowi wyboru]], to znaczy następujące zdanie (tzw. [[prawo dychotomii]]) jest z nim równoważne:
: Dla dowolnych zbiorów <math>X</math> i <math>Y</math> prawdziwa jest alternatywa <math>|X|\leqslant |Y|</math> lub <math>|Y|\leqslant |X|.</math>

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 <math>X</math> zbioru liczb rzeczywistych, że
: <math>\aleph_0<|X|<2^{\aleph_0}.</math>

Przypuszczenia tego, zwanego dziś [[hipoteza continuum|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<ref>{{cytuj pismo |nazwisko = Cohen |imię = Paul J. |tytuł = The Independence of the Continuum Hypothesis |url = https://www.jstor.org/stable/71858 |czasopismo = Proceedings of the National Academy of Sciences of the United States of America |wolumin = 50 |wydanie = 6 |data = December 15, 1963 |strony = 1143–1148 |doi = 10.1073/pnas.50.6.1143 |pmid = 16578557}}</ref><ref>{{cytuj pismo |nazwisko = Cohen |imię = Paul J. |tytuł = The Independence of the Continuum Hypothesis, II |url = https://www.jstor.org/stable/72252 |czasopismo = Proceedings of the National Academy of Sciences of the United States of America |wolumin = 51 |wydanie = 1 |data = January 15, 1964 |strony = 105–110 |doi = 10.1073/pnas.51.1.105 |pmid = 16591132}}</ref>. W połączeniu z opublikowanym w 1940 wynikiem [[Kurt Gödel|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 [[aksjomaty Zermela-Fraenkla|teoria ZF]]).

=== Arytmetyka liczb kardynalnych ===
{{Osobny artykuł|Arytmetyka liczb kardynalnych}}
Opierając się na pojęciu równoliczności zbiorów, można zdefiniować [[działanie dwuargumentowe|działania]] na liczbach kardynalnych: dodawanie, [[mnożenie]], potęgowanie. Pozwala to zbudować [[arytmetyka liczb kardynalnych|arytmetykę liczb kardynalnych]].

Niech <math>X</math> i <math>Y</math> będą dowolnymi zbiorami o liczbach kardynalnych, odpowiednio, <math>a=|X|</math> i <math>b=|Y|.</math> Definiuje się następujące liczby kardynalne:
* '''sumę liczb kardynalnych''' <math>a+b</math> jako moc zbioru
: <math>(X\times\{0\})\cup (Y\times \{1\}).</math>
* '''iloczyn liczb kardynalnych ''' <math>a \cdot b</math> jako moc [[iloczyn kartezjański|iloczynu kartezjańskiego]] <math>X \times Y.</math>
* '''potęgę liczb kardynalnych''' <math>a^b</math> jako moc zbioru wszystkich funkcji ze zbioru <math>Y</math> o wartościach w zbiorze <math>X.</math>

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 <math>b</math> jest nieskończona i <math>a<b,</math> to <math>a+b=b,</math> a jeśli ponadto <math>a</math> jest niezerowa, to
: <math>a\cdot b=b.</math>

== Zobacz też ==
* [[duże liczby kardynalne]]
* [[regularna liczba kardynalna]]
* [[teoria PCF]]

== Uwagi ==
{{Uwagi}}

== Przypisy ==
{{Przypisy}}

== Bibliografia ==
* {{cytuj książkę |nazwisko=Błaszczyk |imię=Aleksander |autor link=Aleksander Błaszczyk |nazwisko2=Turek |imię2=Sławomir |tytuł=Teoria Mnogości |miejsce=Warszawa |wydawca=PWN |rok=2007}}
* {{cytuj książkę |nazwisko=Sierpiński |imię=Wacław |autor link=Wacław Sierpiński |tytuł=Cardinal and ordinal numbers |wydawca=[[Wydawnictwo Naukowe PWN|PWN]] |rok=1965 |wydanie=drugie poprawione |miejsce=Warszawa}}

== Linki zewnętrzne ==
{{Commonscat|Cardinality}}
* {{Pismo Delta | url = 2013/07/rowne-i-rozne/ | autor = Joanna Jaszuńska | tytuł = Równe i różne ∞ | data = lipiec 2013 | data dostępu = 2024-10-30 }}
* {{Cytuj |autor=Tomasz Miller |url=https://www.youtube.com/watch?v=iNMyy9fZpZk |tytuł=Liczby kardynalne {{!}} Zacznijmy od zera #7 | praca = [[Centrum Kopernika Badań Interdyscyplinarnych|Copernicus Center for Interdisciplinary Studies]] |opublikowany=[[YouTube]] |data=14 grudnia 2021 | język=pl | dostęp = o }}
* {{otwarty dostęp}} ''[https://encyclopediaofmath.org/wiki/Cardinal_number Cardinal number]'' {{lang|en}}, Encyclopedia of Mathematics, encyclopediaofmath.org [dostęp 2024-04-05].
* {{otwarty dostęp}} ''[https://www.youtube.com/watch?v=i7c2qz7sO0I A Hierarchy of Infinities]'' {{lang|en}}, kanał PBS Infinite Series na [[YouTube]], 8 grudnia 2016 [dostęp 2024-08-22].

{{Liczby kardynalne}}
{{Główne rodzaje liczb}}
{{Funkcje matematyczne}}

{{Kontrola autorytatywna}}

[[Kategoria:Liczby kardynalne| ]]