Zbiór przeliczalny.html

Zbiór przeliczalny – zbiór skończony lub równoliczny ze zbiorem liczb naturalnych. Mówiąc nieformalnie, zbiór przeliczalny to taki zbiór, którego elementy można ponumerować liczbami naturalnymi. Jeszcze inaczej: elementy zbioru przeliczalnego można ustawić w ciąg – "wypisać je po kolei". Moc zbiorów nieskończonych przeliczalnych oznacza się symbolem $\aleph_0$ (czytaj: alef zero) – jest to najmniejsza moc nieskończona.

edytuj Ujęcie formalne

Zbiór X nazywamy przeliczalnym wtedy i tylko wtedy, gdy istnieje suriekcja przekształcająca zbiór N wszystkich liczb naturalnych na zbiór X.

Równoważnie: gdy istnieje ciąg wyczerpujący zbiór X, tzn. taki, że każdy element zbioru X występuje (przynajmniej raz) w tym ciągu.

Kilka własności zbiorów przeliczalnych:

Podzbiór zbioru przeliczalnego jest przeliczalny.
Suma przeliczalnej ilości zbiorów przeliczalnych jest zbiorem przeliczalnym.
Iloczyn kartezjański skończonej liczby zbiorów przeliczalnych jest zbiorem przeliczalnym.

edytuj 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 N i tego zbioru.
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 rzeczywistych nie jest zbiorem przeliczalnym. Zobacz: rozumowanie przekątniowe.

Pojęcie zbioru przeliczalnego pochodzi od Georga Cantora.

Zbiór przeliczalny.html

edytuj Ujęcie formalne

edytuj Przykłady

edytuj Zobacz też