Moc zbioru

Z Wikipedii

Ten artykuł wymaga dopracowania zgodnie z zaleceniami edycyjnymi.
Dokładniejsze informacje o tym, co należy poprawić, być może znajdziesz na stronie dyskusji tego artykułu.
Po naprawieniu wszystkich błędów można usunąć tę wiadomość.

Moc (liczba kardynalna) zbioru – w teorii mnogości termin określający liczebność zbioru – im zbiór „większy” tym większą ma moc. Dwa zbiory mają tę samą moc, czyli są równoliczne, gdy mają „tyle samo elementów”.

Liczba kardynalna zbioru jest naturalnym uogólnieniem liczby elementów dla zbioru skończonego, dlatego też moc zbioru skończonego jest równa liczbie elementów tego zbioru.

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.

Spis treści

1 Intuicje
2 Rys historyczny
3 Ujęcie formalne
- 3.1 Zbiory skończone i nieskończone
- 3.2 Arytmetyka liczb kardynalnych
4 Zobacz też

[edytuj] 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.

Uogólniając tę obserwację powiemy, że

dwa zbiory są równoliczne, gdy istnieje funkcja wzajemnie jednoznaczna z jednego zbioru na drugi.

Jeżeli dwa zbiory są równoliczne, to mówimy, że mają tę samą moc, lub tę samą liczbę kardynalną.

To proste i naturalne sprecyzowanie rozumienia co to znaczy, że dwa zbiory mają tyle samo elementów prowadzi jednak, jak często w matematyce, do zaskakujących konsekwencji. Okazuje się bowiem, że w przypadku zbiorów nieskończonych intuicje nabyte podczas obcowania ze zbiorami skończonymi zawodzą – na przykład zbiór liczb parzystych dodatnich jest równoliczny ze zbiorem liczb naturalnych, choć "gołym okiem" widać, że jest ich "dwa razy mniej". A jednak, elementy obu zbiorów można ustawić w pary (parzysta, naturalna) choćby w sposób następujący: (2, 1), (4, 2), (6, 3), ..., (240, 120),... Korzystając z wyżej wprowadzonego pojęcia równoliczności należy uznać, że oba zbiory liczą tyle samo elementów! Zbiór liczb wymiernych również jest równoliczny ze zbiorem liczb naturalnych, co może wydawać się zaskakujące. Podobnie przeczy intuicji fakt, że na prostej jest tyle samo punktów, co na płaszczyźnie - wydawałoby się, że powinno być ich "nieskończenie wiele razy więcej".

[edytuj] Rys historyczny

Do badań nad ogólnymi własnościami zbiorów, czyli tym, co dziś nazywa się teorią mnogości, doprowadziły Cantora rozważania nad zbieżnością szeregów trygonometrycznych. W trakcie tych prac pojawiła się konieczność precyzyjnego wyrażania uzyskanych wyników, co nasuwało kolejne problemy, z zakresu teorii mnogości właśnie.

Pierwsze rezultaty Cantora dotyczyły zbiorów przeliczalnych, czyli równolicznych ze zbiorem liczb naturalnych. Dowiódł on, że każdy nieskończony podzbiór tego zbioru jest z nim równoliczny, a co więcej, wiele innych ważnych zbiorów, które często występują w matematyce jest również z nim równolicznych. W szczególności dotyczy to zbioru liczb wymiernych i zbioru liczb algebraicznych.

W roku 1873 Cantorowi udało się również udowodnić, że zbiór liczb rzeczywistych nie jest przeliczalny, a ponieważ zbiór liczb naturalnych jest równoliczny z właściwym podzbiorem zbioru liczb rzeczywistych, należy uznać, że liczb rzeczywistych "jest więcej" niż liczb naturalnych. Okazało się, że wśród "liczb nieskończonych" też istnieje hierarchia wielkości!

Moc zbioru liczb naturalnych Cantor oznaczył symbolem $\aleph_0$ – hebrajską literą alef z indeksem 0, moc zbioru liczb rzeczywistych symbolem $\mathfrak{c}$ (continuum). Cantor udowodnił, że $\aleph_0$ jest najmniejszą liczbą kardynalną nieskończoną. Pokazał też, że dla każdej liczby kardynalnej istnieje liczba bezpośrednio od niej większa.

Dalsze badania doprowadziły Cantora do zbudowania arytmetyki liczb kardynalnych i dowodu faktu, że zbiór wszystkich podzbiorów (czyli zbiór potęgowy) dowolnego zbioru jest większej mocy niż zbiór wyjściowy (twierdzenie Cantora). Wynika stąd, że dla każdej liczby kardynalnej istnieje liczba większa od niej, zatem nie istnieje największa liczba kardynalna.

Ponadto okazało się, że zbiór podzbiorów zbioru liczb naturalnych jest mocy $\mathfrak c$ . W związku z tym Cantor rozważał pytanie, czy istnieje liczba kardynalna większa niż $\aleph_0$ i mniejsza niż $\mathfrak{c}$ . Sam Cantor spodziewał się, że nie – tzn. że $\mathfrak c$ jest najmniejszą liczbą kardynalną większą od $\aleph_0$ . Przypuszczenia tego, zwanego dziś hipotezą continuum, nie potrafił jednak dowieść. Problem pozostawał nie rozwią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.

[edytuj] Ujęcie formalne

Precyzyjnie pojęcie liczby kardynalnej (mocy) zbioru określa się następująco:

liczba kardynalna danego zbioru $X$ jest to najmniejsza liczba porządkowa α o tej własności, że istnieje funkcja wzajemnie jednoznaczna ze zbioru $X$ do α.

Definicja ta wymaga, aby spełniony był aksjomat wyboru; poniższe określenie nie wymaga żadnych warunków wstępnych:

liczba kardynalna zbioru

X

to klasa wszystkich zbiorów równolicznych ze zbiorem

X

Liczbę kardynalną (moc) zbioru $X$ oznaczamy symbolem $| X |$ lub $\overline{\overline{X}}$ – tej właśnie symboliki używał Cantor.

Powiemy, że moc zbioru $X$ jest nie większa od mocy zbioru $Y$ , gdy istnieje funkcja różnowartościowa ze zbioru $X$ do zbioru $Y$ . W takiej sytuacji piszemy: $|X|\le|Y|$ . Jeżeli $|X|\le|Y|$ i nieprawda, że $| X | = | Y |$ , to mówimy, że zbiór $X$ ma moc mniejszą niż zbiór $Y$ .

Aksjomat wyboru równoważny jest stwierdzeniu, że nierówność między liczbami kardynalnymi spełnia prawo trychotomii, to znaczy, że dla dowolnych zbiorów $X$ i $Y$ zachodzi dokładnie jeden z warunków: albo $| X | < Y$ , albo $X = Y$ , albo $X > Y$ .

Podstawowe dla teorii twierdzenie Cantora-Bernsteina-Schrödera mówi, że jeśli $|X|\le|Y|$ i $|Y|\le|X|$ , to $| X | = | Y |$ .

[edytuj] Zbiory skończone i nieskończone

Posługując się pojęciem równoliczności można precyzyjnie zdefiniować pojęcia zbiorów skończonego i nieskończonego:

Zbiór skończony to zbiór, który jest równoliczny ze zbiorem {1, 2, ..., n} dla pewnej liczby naturalnej n. Określenie to obejmuje również zbiór pusty - wystarczy przyjąć n=0.
Zbiór nieskończony to zbiór, który nie jest skończony (a więc taki, który nie jest równoliczny z żadnym zbiorem postaci {1, 2, ..., n}). Liczbę kardynalną nazywamy nieskończoną, gdy jest mocą pewnego zbioru nieskończonego.

[edytuj] 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.

Sumę liczb kardynalnych $a$ i $b$ określamy jak następuje: niech $X$ i $Y$ będą takimi zbiorami rozłącznymi, że $a = | X |$ i $b = | Y |$ . Liczbę kardynalnę $a + b$ definiujemy jako moc zbioru $X\cup Y$ . Określenie iloczynu liczb kardynalnych nie wymaga założenia, by zbiory $X$ i $Y$ były rozłączne – liczbę $a\cdot b$ określa się jako moc iloczynu kartezjańskiego zbiorów $X\times Y$ . Również definicja potęgi liczb kardynalnych nie wymaga rozłączności zbiorów $X$ i $Y$ – przez liczbę $a b$ rozumiemy moc zbioru wszystkich funkcji ze zbioru $Y$ w zbiór $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\not=0$ , to $a\cdot b=b$ .