Zbiór przeliczalny - Polski Serwis Naukowy

Zbiór przeliczalny – intuicyjnie, zbiór którego elementy można ustawić w ciąg (skończony bądź nie), tzn. "wypisać je po kolei", "ponumerować". Istnieją dwie nierównoważne konwencje użycia terminu zbiór przeliczalny w matematyce:

zbiór przeliczalny to zbiór skończony lub zbiór równoliczny ze zbiorem liczb naturalnych (tzn. taki zbiór, że istnieje funkcja wzajemnie jednoznaczna między nim a zbiorem liczb naturalnych. Zbiór równoliczny ze zbiorem liczb naturalnych jest zbiorem nieskończonym).

zbiór przeliczalny to zbiór równoliczny ze zbiorem liczb naturalnych (definicja ta wyklucza możliwość bycia zbiorem skończonym ponieważ nie istnieje funkcja różnowartościowa określona w zbiorze liczb naturalnych o wartościach w zbiorze skończonym).

Liczbę kardynalną zbioru liczb naturalnych – a więc i każdego nieskończonego zbioru przeliczalnego – oznacza się symbolem $\aleph_0$ (czyt.: alef zero). Niektórzy matematycy oznaczają tę liczbę kardynalną symbolem $\omega$ (ponieważ formalnie $\aleph_0$ jest najmniejszą nieskończoną liczbą porządkową).

Liczby naturalne – liczby służące podawaniu liczności (trzy osoby, zob. liczebnik główny/kardynalny) i ustalania kolejności (trzecia osoba, zob. liczebnik porządkowy), poddane w matematyce dalszym uogólnieniom (odpowiednio: liczby kardynalne, liczby porządkowe). Badaniem własności liczb naturalnych zajmują się arytmetyka i teoria liczb.

Liczba algebraiczna to liczba rzeczywista (ogólniej zespolona), która jest pierwiastkiem pewnego niezerowego wielomianu o współczynnikach wymiernych (a więc i całkowitych).

Własności

Poniższe własności są prawdziwe dla zbiorów przeliczalnych w sensie obu powyższych definicji:

Nieskończony podzbiór zbioru przeliczalnego jest przeliczalny.

Suma przeliczalnie wielu zbiorów przeliczalnych jest zbiorem przeliczalnym.

Iloczyn kartezjański skończonej liczby zbiorów przeliczalnych jest zbiorem przeliczalnym.

Przykłady

Zbiór liczb wymiernych jest równoliczny ze zbiorem liczb naturalnych

Zbiór wszystkich liczb naturalnych nieparzystych jest zbiorem przeliczalnym ponieważ funkcja f(n) = 2n + 1 ustala równoliczność zbioru liczb naturalnych ze zbiorem liczb nieparzystych.

Zbiór wszystkich liczb pierwszych jest (nieskończonym) zbiorem przeliczalnym, jako nieskończony podzbiór zbioru liczb naturalnych.

Zbiór wszystkich liczb całkowitych jest przeliczalny. Można bowiem liczby całkowite ustawić w ciąg, na przykład w ten sposób: 0, 1, -1, 2, -2, 3, -3, 4, -4, 5, -5, ...

Zbiór wszystkich liczb wymiernych jest przeliczalny. Aby to udowodnić wystarczy wszystkie liczby wymierne wpisać do następującej tablicy: w wierszu pierwszym wpiszemy liczby 1/1, -1/1, 1/2, -1/2 ,1/3, -1/3... w wierszu drugim 2/1, -2/1, 2/2, -2/2, 2/3, -2/3... itd.; ogólnie, w wierszu n-tym wpisujemy liczby postaci n/i, -n/i gdzie i=1,2,3,... W ten sposób w tablicy znajdą się wszystkie liczby wymierne. Aby teraz z takiej dwuwymiarowej tabeli wybrać ciąg zawierający kolejno wszystkie jej elementy, wystarczy wybierać liczby według reguły "po skosie" zaczynając od lewego górnego rogu i poruszając się raz w dół, raz do góry. Otrzymujemy tym samym uporządkowanie wszystkich liczb wymiernych w ciąg – co więcej, każda liczba wymierna pojawi się w tym ciągu nieskończenie wiele razy.

Zbiór liczb algebraicznych jest przeliczalny.

Zbiór liczb rzeczywistych nie jest zbiorem przeliczalnym (jest to przykład zbioru nieprzeliczalnego) - zob.: rozumowanie przekątniowe.

Bibliografia

Helena Rasiowa: Wstęp do matematyki współczesnej. Wyd. dwunaste. Warszawa: PWN, 1998, s. 95-99. ISBN 83-01-01373-7.

Zobacz też

paradoks Hilberta

Zbiór skończony - oznacza w matematyce zbiór równoliczny ze zbiorem {1, 2, ..., n} dla pewnej liczby naturalnej n. Definicja ta obejmuje również zbiór pusty, wystarczy przyjąć n = 0.

Rozumowanie przekątniowe to klasyczny przykład rozumowania w dowodzie nie wprost. Za jego pomocą można wykazać na przykład, że moc zbioru liczb rzeczywistych z przedziału [0,1] jest większa od mocy zbioru liczb naturalnych. Natychmiastowy wniosek z tego faktu podawany jest obrazowo: liczb rzeczywistych jest więcej niż liczb naturalnych.