Апология математики (сборник статей)

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

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

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

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

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

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

Пример 42. Доказать, что объединение счётного множества A с конечным множеством B является счётным множеством.

Пусть A = {a₁, a₂, a₃, …, a_n, …} и B = {b₁, b₂, b₃, …, b_n}. Тогда их объединение A ∪ B можно расположить в последовательность {b₁, b₂, b₃, …, b_n, a₁, a₂, a₃, … a_n, …}. Элемент a₁ получит в этой последовательности номер (n + 1). Следовательно, объединение счётного и конечного множеств счётно.

Пример 43. Доказать, что объединение счётного множества A со счётным множеством B является счётным множеством.

Пусть A = {a₁, a₂, a₃, …, a_n, …} и B = {b₁, b₂, b₃, …, b_n, …}. Тогда их объединение A ∪ B можно расположить в последовательность {a₁, b₁, a₂, b₂, a₃, b₃, …, a_n, b_n, …}. Значит, объединение двух счётных множеств счётно.

Пример 44. Доказать, что всякое бесконечное множество M содержит счётное подмножество.

Так как множество M бесконечно, в нём имеется какой-то элемент, который мы обозначим a₁. Бесконечное множество не может исчерпываться этим единственным элементом, поэтому в M присутствует ещё какой-то, отличный от a₁ элемент, который мы обозначим a₂. Но и этими двумя элементами не исчерпывается бесконечное множество, поэтому в нём найдётся элемент a₃, отличающийся как от a₁, так и от a₂. Продолжая процесс, мы выделим из множества M счётное подмножество {a₁, a₂, a₃, …}. Итак, всякое бесконечное множество содержит счётное подмножество.