Zbiory i są równoliczne, gdy ich elementy można dobrać w pary (każdy element z ma dokładnie jedną parę w i na odwrót). Piszemy wtedy Jeśli to zbiór nazywamy przeliczalnym; dobranie w pary jego elementów z liczbami naturalnymi odpowiada ustawieniu ich w ciąg: (element zbioru oznaczony jako jest w parze z liczbą naturalną ).

Zakładamy, że oznacza zbiór liczb całkowitych, to zbiór liczb wymiernych, oznacza zbiór dodatnich liczb z

Udowodnimy, że liczb całkowitych, wbrew pozorom, nie jest wcale więcej, niż naturalnych, a dokładnie tyle samo. W tym celu ustawmy je w następujący ciąg: Każda liczba całkowita występuje w tym ciągu dokładnie jeden raz, jest ich więc tyle samo, co liczb naturalnych.

Rys. 1 Zygzak odwiedza dokładnie raz każdy punkt dla

Wykażemy teraz, że również liczb wymiernych jest przeliczalnie wiele. Najpierw udowodnimy, że W tym celu rozważmy punkty płaszczyzny o obu współrzędnych całkowitych dodatnich. Każdemu takiemu punktowi przypiszmy dodatnią liczbę wymierną Następnie odwiedźmy po kolei wszystkie te punkty, spacerując po płaszczyźnie zygzakiem o początku w jak na rysunku 1. Spisujmy kolejno odwiedzane liczby wymierne ale bez powtórzeń (np. liczbę pomijamy, bo wcześniej była ). Otrzymujemy w ten sposób ciąg wszystkich dodatnich liczb wymiernych:

Aby wykazać, że zastosujmy podobny pomysł, jak przy dowodzie - ustawmy na przemian liczby z powyższego ciągu i liczby do nich przeciwne, a na początku zero:

Rys. 2 Przykładowe wartości ciągu oraz przekątna tabeli. Tutaj

Liczb rzeczywistych jest więcej, niż liczb naturalnych, czyli nieprzeliczalnie wiele. Wykażemy, że nieprzeliczalny jest już podzbiór takich liczb z odcinka których rozwinięcie dziesiętne składa się wyłącznie z cyfr 0 i 1.

Załóżmy, że podzbiór ten jest przeliczalny, czyli jego elementy można ustawić w ciąg Otrzymujemy tabelę (Rys. 2); jest ona nieskończona w prawo (liczbom o skończonym rozwinięciu dziesiętnym dopisujemy dalej same zera) oraz w dół (liczb rozważanej postaci jest nieskończenie wiele, m.in.

Zapiszmy ciąg cyfr z przekątnej tabeli, a następnie zamieńmy w nim wszystkie 0 na 1, a 1 na 0. Niech liczba ma w zapisie dziesiętnym zero, a po przecinku uzyskany w ten sposób ciąg cyfr. Wtedy oraz ma w rozwinięciu dziesiętnym same 0 i 1, zatem z założenia występuje w naszym ciągu czyli w którymś wierszu rozważanej tabeli. Nie jest on równy bo wskutek zamiany 0 i 1 z przekątnej, od liczby w pierwszym wierszu różni się na pierwszym miejscu po przecinku. Podobnie bo od liczby w drugim wierszu różni się na drugim miejscu po przecinku. Analogicznie nie jest równy żadnej z pozostałych liczb z naszego ciągu, bo od liczby w -tym wierszu różni się na -tym miejscu po przecinku. Zbudowaliśmy więc liczbę z rozważanego zbioru, ale spoza ciągu, który miał zawierać wszystkie jego elementy. Uzyskana sprzeczność dowodzi, że zbiór ten jest nieprzeliczalny, zatem także oraz

Gdyby liczb niewymiernych było przeliczalnie wiele, można by ustawić je w ciąg Wykorzystując nasz ciąg liczb wymiernych, uzyskalibyśmy ciąg wszystkich liczb rzeczywistych: Wiemy jednak, że zatem to niemożliwe. Stąd

Rys. 3

Pokażemy teraz, że odcinek zawiera tyle samo punktów, co prosta. Najpierw wykażemy, że Rozważmy odcinek na osi oraz dodatnią półoś (Rys. 3). Zapalmy latarkę w punkcie i każdemu punktowi z odcinka przydzielmy do pary jego cień na półprostej

Analogicznie, punktom z odcinka przydzielamy pary z niedodatniej półosi (latarka w punkcie ), co wobec powyższego daje

Twierdzenie Cantora orzeka, że każdy zbiór ma więcej podzbiorów niż elementów. Stąd dla dowolnego zbioru nieskończonego istnieje zbiór jeszcze od niego większy! Opisane powyżej zbiory, równoliczne z lub to tylko niektórzy, najczęściej spotykani przedstawiciele zbiorów nieskończonych.