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

синонимичны. Они несут в себе одинаковый смысл.

Очевиден следующий принцип транзитивности:

если два множества равномощны третьему, то они равномощны друг другу.

(Предлагаем читателю в качестве упражнения самостоятельно сформулировать принцип транзитивности в терминах взаимно однозначных соответствий.)

Но вернёмся к примеру 33.

В силу только что сказанного частей нашего подмножества столько же, сколько цепочек плюсов и минусов длины n, а число таких цепочек, как показано в примере 32, есть 2ⁿ.

Пример 34. Пусть в алфавите s букв. Сколько в этом алфавите слов длины n?

Рассуждаем как в примере 32. Удлинение на одну букву приводит к увеличению количества слов в s раз. Начиная со слов длины 0, количество коих есть 1, приходим к выводу, что количество слов длины n равно sⁿ.

Пример 35. Дан список из n слов длины n в каком-то алфавите. Как указать слово в том же алфавите, не входящее в заданный список?

Решение проиллюстрируем на частном случае. В качестве алфавита возьмём двухбуквенный алфавит {0; 1}, а список такой: 00100100100; 01011011010; 10011011001; 01111011101; 11001010110; 11111111111; 11010001000; 11001000100; 00000000000; 10101010101; 01010101010. Расположим слова списка одно под другим, так чтобы получилась квадратная таблица:

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

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

Пример 36 (Кантор). Доказать, что множества Ω и N имеют различное количество элементов.

Для этого мы должны установить невозможность взаимно однозначного соответствия между указанными множествами. Рассуждаем от противного. Пусть такое соответствие возможно. Тогда бесконечные двоичные последовательности, из которых состоит множество Ω, можно занумеровать натуральными числами: первая, вторая, третья и т. д. Расположим эти последовательности друг под другом. Возможный вариант такого расположения показан ниже.