Zbiory przeliczalne i nieprzeliczalne
Zbiór przeliczalny
Zbiór A ≠ 0 jest przeliczalny wtedy i tylko wtedy, gdy jest on zbiorem wyrazów pewnego ciągu nieskończonego, czyli wtedy i tylko wtedy, gdy istnieje funkcja f przekształcająca zbiór wszystkich liczb naturalnych na zbiór A.
Zbiór przeliczalny zatem to zbiór skończony lub równoliczny ze zbiorem wszystkich liczb naturalnych. Zbiory przeliczalne nieskończone są równej mocy. Moc zbiorów przeliczalnych nieskończonych oznaczamy symbolem ℵ0 (czytaj: alef zero).
Przykłady zbiorów przeliczalnych:
- podzbiór zbioru przeliczalnego jest zbiorem przeliczalnym,
- suma dowolnej skończonej ilości zbiorów przeliczalnych jest zbiorem przeliczalnym,
- produkt kartezjański zbiorów przeliczalnych jest zbiorem przeliczalnym,
- zbiór wszystkich liczb całkowitych jest zbiorem przeliczalnym,
- zbiór wszystkich liczb wymiernych jest zbiorem przeliczalnym,
- zbiór wszystkich ciągów skończonych o wyrazach należących do ustalonego zbioru przeliczalnego jest zbiorem
przeliczalnym,
- zbiór wszystkich wielomianów jednej zmiennej o współczynnikach wymiernych jest przeliczalny,
- zbiór wszystkich liczb algebraicznych jest przeliczalny.
Zbiór nieprzeliczalny
Zbiór nieprzeliczalny to zbiór, który nie jest przeliczalny.
Zbiór liczb rzeczywistych przedziału <0, 1> jest zbiorem nieprzeliczalnym, gdyż nie istnieje ciąg o wyrazach z przedziału <0, 1>, taki że każda liczba rzeczywista z tego przedziału jest wyrazem ciągu.
Jeżeli zbiór A jest nieprzeliczalny i A ⊂ B, to B jest również zbiorem nieprzeliczalnym. Z twierdzenia tego wynika, że zbiór wszystkich liczb rzeczywistych jest nieprzeliczalny.
Moc zbioru wszystkich liczb rzeczywistych nazywamy continuum i oznaczamy symbolicznie ℭ.
Zbiór wszystkich liczb niewymiernych jest zbiorem nieprzeliczalnym
Zbiór wszystkich liczb przestępnych jest nieprzeliczalny.