Страница 23 из 30
Некоторые множества, образованные натуральными числами.
Вопрос, на который Кантор ответил в своей статье 1892 года, гласит: «Какова мощность 'P(N) ?» Для ответа нужно найти удобный способ представления множеств, образованных натуральными числами. Для определения числового множества достаточно знать, какие числа принадлежат множеству, а какие нет. Представим, что двое, Алиса и Бруно, играют в игру: Алиса загадывает множество, а Бруно должен отгадать его. Для этого он по порядку называет натуральные числа: 0, 1,2, 3, 4,...; каждый раз, когда названное число входит в загаданное множество, Алиса говорит «Да», если нет — «Нет». Если она говорит: «Нет, да, нет, да, нет, да, нет, да,...», Бруно может заключить, что речь идет о множестве нечетных чисел. Если все ее ответы — «Да», то это множество 'P(N) ; если это множество простых чисел, то ответы будут: «Нет, нет, да, да, нет, да, нет, да, нет, нет, нет, да,...». Каждое «Да» мы можем заменить числом 1, а каждое «Нет» — числом 0. Таким образом, каждое множество, состоящее из натуральных чисел, будет являться бесконечной последовательностью нуля и единицы. Если мы перезапишем ответы Алисы, то множество нечетных чисел будет представлено последовательностью 010101..., множество 'P(N) — 11111..., а множество простых чисел — 001101010001... То есть каждой бесконечной последовательности нуля и единицы соответствует некое множество, и наоборот, каждому множеству соответствует бесконечная последовательность нуля и единицы. Это взаимно однозначное соответствие подразумевает, что вопрос о мощности 'P(N) и мощности всех бесконечных последовательностей нуля и единицы — одно и то же (см. рисунок).
В статье 1892 года «Об одном элементарном вопросе учения о многообразиях» Кантор доказывает по существу две вещи. Прежде всего — что множество всех последовательностей нуля и единицы не является счетным, поэтому и 'P(N) несчетно. Для этого ученый использовал диагональный метод (см. главу 2). В действительности данный метод впервые появился именно в этой работе 1892 года. Доказательство несчетности, которое привел Кантор в 1874 году, следовало другой логике и основывалось на определении вещественных чисел.
Доказательство, что 'P(N) несчетное, основывается на алгоритме, описанном в главе 2 для вещественных чисел. Однако несчетность 'P(N) и R, даже если в ходе доказательства мы рассуждали так же, не гарантирует, что у них одинаковая мощность. Метод диагонали дает нам отрицательный результат, то есть позволяет убедиться, что ни у 'P(N), ни у R мощность не равна X0 , но не показывает, какую конкретно мощность имеет каждое из них, и не дает оснований заключить, что их мощности равны.
Взаимнооднозначное соответствие между множествами и последовательностями нуля и единицы.
В статье 1892 года Кантор доказал, что эти множества равномощные, однако это нельзя заключить на основе диагонального метода; необходимо предъявить отдельное доказательство. Итак, требуется доказать, что 'P(N) и R эквивалентны или что R эквивалентно всем бесконечным последовательностям нуля и единицы.
Для начала вспомним, что способ привычной нам записи натуральных чисел основан на десятичной системе, так как для них необходимы все 10 цифр, а также на степенях числа 10. Когда мы записываем число 235, на самом деле мы пишем 2 · 102 + 3 х 101 + 5 · 100 (напомним, что 101 = 10, а 100 = 1). Нечто похожее происходит с числами, которые не являются целыми, но в этом случае используются степени с отрицательным знаком: 10-1 равное 0,1; 10-2, равное 0,01, и так далее. 0,76 на самом деле означает 7 ∙ 101 + 6 ∙ 10-2. Интересно подчеркнуть, что числа с бесконечным количеством цифр после запятой, такие как 0,3333..., можно представить в виде бесконечных сумм.
Действительно, 0,333... = 3 ∙ 10-1 + 3 ∙ 10-2 + 3 ∙ 10-3 + 3 ∙ 10-4 + ... Хотя десятичная запись используется чаще всего, она не единственно возможная: например, числа можно записывать на основе так называемой двоичной системы. Как явствует из ее названия, в ней используются только две цифры — 0 и 1, — а основана она на степенях числа 2. Число 13 в двоичной системе будет записано как 1101, поскольку 13 = 1 ∙ 23 + 1 ∙ 22 + 0 ∙ 21 + 1 ∙ 20. Как и в предыдущем случае, этот способ записи не распространяется на целые числа. Например, в двоичной системе число 0,333... будет выглядеть как 0,01010101..., поскольку бесконечная сумма 0 ∙ 2-1 + 1 ∙ 2-2 + 1 ∙ 2-4 + 0 ∙ 2-5 + 1 ∙ 2-6 в результате даст 0,333... (записанное в десятичной системе).
Понятия теории множеств — известные и необходимые инструменты.
Жак Адамар, французский математик (1865-1963), на конференции 1897 года
Теперь докажем, что множество всех вещественных чисел с 0 по 1 на отрезке числовой прямой эквивалентно 'P(М). Необходимо получить такой результат, при котором каждому числу с 0 по 1 точно соответствует множество натуральных чисел.
Возьмем число 0,333... Как найти эквивалентное ему множество? На рисунке показано, что сначала мы должны записать его в двоичной системе. Получив выражение 0,01010101..., возьмем только его часть после запятой, в данном случае 010101..., и посмотрим, какое множество соответствует этой последовательности. Поскольку это последовательность нечетных чисел, то 0,333... соответствует ей.
Таким же образом, если у нас есть множество, образованное, например, числами 2 и 3, и мы хотим узнать, какому числу оно соответствует, сначала мы должны представить его в виде последовательности нуля и единицы. В данном случае это будет выражение 00110000..., и рассмотрим его как цифры после запятой некоего числа, записанного в двоичной системе. Это число 0,001100000..., которое в десятичной системе будет выглядеть как 0,1875. Таким образом, множеству, состоящему из чисел 2 и 3, соответствует число 0,1875.
Итак, мы видим, что 'P(N) эквивалентно множеству всех чисел между 0 и 1. Но в главе 3 отмечалось, что оно эквивалентно R (любой отрезок эквивалентен всей прямой); таким образом, мы выводим, что 'P(N) эквивалентно R. Наконец, на вопрос, какова же мощность 'P(N), в 1892 году Кантор ответил, что она равна мощности R.
Взаимно однозначное соответствие между вещественными числами (в промежутке от 0 до 1) и множествами, состоящими из вещественных чисел.
Рассмотрим еще одну операцию из области трансфинитной математики.
Вернемся к последовательностям нуля и единицы, но теперь рассмотрим только конечные. Сколько таких последовательностей мы можем образовать, если в них должно быть только две цифры? Всего четыре последовательности: 00, 01, 10 и 11. Если цифр три, то их будет восемь: 000, 001, 010, 100, 110, 101,011, 111, а если цифр всего четыре, то 16. Если цифра одна, то последовательностей будет только две: 0 и 1.
Итак, у нас есть 21 последовательности из одной цифры, 22 последовательности из двух цифр, 23 последовательности из трех цифр и так далее. Логично было бы предположить, что мощность последовательностей из «X0 цифр» будет равна 2X0. Действительно, в «Обоснованиях» Кантор дает определение возведению мощностей в степень и основывает его на понятии, которое он назвал покрытием. Когда мы составляем бесконечную последовательность из нуля и единицы, утверждает Кантор, мы покрываем каждый элемент N нулем или единицей.