Существование подобных гостиниц, которые невозможно заполнить, — это не просто любопытный факт, связанный с четными числами, а основное свойство бесконечных множеств, как заметил Рихард Дедекинд в своей статье «Что такое числа и для чего они служат», опубликованной в 1888 году. Множество является бесконечным, если можно определить биекцию между ним и его частью. Очевидно, что с конечными множествами подобное невозможно, так как часть конечного множества не может быть поставлена в соответствие целому (как мы говорили выше, между двумя конечными множествами, число элементов которых равно m и n соответственно, можно установить биекцию только при m = n). Тем не менее натуральных чисел бесконечно много, так как часть этого множества, строго включенная в него, то есть множество четных чисел, имеет то же кардинальное число, что и все множество в целом. Следовательно, новое определение соответствует рассуждениям, основанным на аксиомах Пеано, с помощью которых мы в предыдущей главе доказали, что натуральных чисел бесконечно много. Однако множество натуральных чисел — это наименьшее бесконечное множество из всех, что можно представить.
Поэтому все множества, для которых можно установить биекцию со множеством натуральных чисел, называются счетными множествами, а их кардинальное число обозначается буквой алеф — первой буквой еврейского алфавита. Индекс указывает, что речь идет о наименьшем кардинальном числе: 
.
Счетность множества означает, что между множеством X и множеством натуральных чисел можно установить биекцию. Так, каждому натуральному n можно поставить в соответствие элемент этого множества, который мы обозначим через хn, так, что если n и m различны, то хn и хm также различны. С другой стороны, все элементы X можно записать в виде хn для некоторого n. Когда дети идут на экскурсию с классом, учитель иногда присваивает им номера, чтобы никто не потерялся.
Перед тем как сесть в автобус, каждый ученик громко выкрикивает свой номер: пе-е-ервый! второ-о-ой! тре-е-етий! Каждый ученик имеет свой номер, и ни один из номеров не повторяется. Элементы счетных множеств также имеют свои порядковые номера: «пе-е-ервый!» — это x1 «второ-о-ой!» — х2. Счетные множества — это множества, элементы которых можно выстроить в ряд. Мы показали, что множество четных чисел является счетным, так как их можно упорядочить: 0, 2, 4, 6, 8, 10… Это же справедливо и для положительных и отрицательных чисел, так как можно, начав с нуля, называть их поочередно: 0, 1, —1, 2, —2.
Элементы любого ли множества можно выстроить в ряд? Если это так, то все множества будут счетными, и мы придем к тому же, с чего начали, когда использовали примитивный метод подсчета элементов множества. Однако пусть читатель не беспокоится: одним из величайших достижений Георга Кантора стало открытие множеств, которые не являются счетными. Пусть дано множество, образованное бесконечными последовательностями нулей и единиц, то есть объектами вида 0100100010… или 1100101001… Покажем, что если мы будем считать это множество счетным, то придем к противоречию. В самом деле, если бы это множество было счетным, мы могли бы записать все его элементы в виде списка следующим образом:
Напомним, что аn, Ьn и сn принимают только значения 0 и 1. Составим элемент, который будет принадлежать к множеству бесконечных последовательностей нулей и единиц и при этом не будет упомянут в нашем списке. Для этого рассмотрим элементы, расположенные по диагонали и обведенные рамкой. Рассмотрим a0: если этот элемент равен 0, начнем нашу последовательность с 1, и наоборот. Так мы определим первый член нашей последовательности. Перейдем к b1 если этот элемент равен 0, то вторым членом нашей последовательности будет 1. Если же, напротив, этот элемент равен 1, то вторым членом последовательности будет 0. В общем случае для определения n-го члена нашей последовательности мы будем рассматривать соответствующий элемент на диагонали и записывать противоположное ему значение. Таким образом, мы получим последовательность, все члены которой будут иметь значение 0 или 1, следовательно, эта последовательность будет принадлежать к рассматриваемому множеству. Например, если наш список будет начинаться так: