К сожалению, оба натуральных ряда претендуют на обозначение N. Это не слишком страшно, потому что из контекста ясно, какой из двух натуральных рядов имеется в виду. В этом параграфе натуральный ряд начинается с единицы.

Множество называется счётным, если между ним и натуральным рядом можно установить взаимно однозначное соответствие. Например, множество всех целых чисел счётно, как показывает бесконечная таблица из двух строк:

В первой строке в некотором порядке выписаны все целые числа, во второй – соответствующие им члены натурального ряда. Ясно, что между любыми двумя счётными множествами можно установить взаимно однозначное соответствие (хотя бы через промежуточное соответствие каждого из них с натуральным рядом). Поэтому все счётные множества имеют одинаковую мощность или одинаковое количество элементов – столько же, сколько их содержится в натуральном ряду, т. е. столько же, сколько существует натуральных чисел.

Позволительно дать и такое определение счётного множества:

множество называется счётным, если его можно пересчитать, т. е. назвать какой-то его элемент первым; какой-то элемент, отличный от первого, – вторым; какой-то, отличный от первых двух, – третьим и т. д., причём ни один элемент множества не должен быть пропущен при пересчёте.

Как только какое-либо бесконечное множество удалось расположить в последовательность отличных друг от друга элементов, так сразу возникает его взаимно однозначный пересчёт: член последовательности, стоящий на первом месте, и только он, объявляется первым; член, стоящий на втором месте, и только он, – вторым и т. д. Возьмём, к примеру, множество всех слов, составленных из букв a и b, и расположим его в последовательность:

A, a, b, aa, ab, ba, bb, aaa, aab, aba, abb, …, baaba, baabb, ….

A, a, b, aa, ab, ba, bb, aaa, aab, aba, abb, …, baaba, baabb, ….

Правило расположения слов в последовательности мы выбрали таким (а могли бы выбрать и другим): группируем слова по длине, а в пределах группы располагаем их в алфавитном порядке. Раз множество всех слов в двухбуквенном алфавите удалось расположить в последовательность различающихся элементов, значит, оно счётно. Аналогичным образом можно расположить в последовательность различающихся элементов и множество слов в любом другом алфавите. Поэтому имеет место следующий фундаментальный факт: каков бы ни был алфавит, множество всех слов в этом алфавите счётно.