Сменил название с
Диагональный метод Кантора для доказательства несчётности на
Для всех тех, у кого несчётность R вызывает сомнения: во избежание множения сущностей. Моё сомнение разрешилось, но с бесконечными множествами очень легко перемудрить. Так что пусть младые умы высказывают найденные ими "противоречия" здесь.
Интерлюдия.На первом курсе матанализа неравномощность множеств
и
нам обосновывали с помощью диагонального метода Кантора. Я убедился, что эта практика является общеупотребимой для ВУЗов моего города. Ни в коей мере не утверждаю, что
, ибо интуитивно уверен в обратном, однако, хочу твёрдое тому доказательство. Диагональный метод вызывает серьёзные сомнения с моей стороны. Если я не прав, прошу указать на допущенную мной ошибку в рассуждениях. Если прав, то мне очень бы хотелось взгянуть на корректное доказательство (
желательно, но не обязательно, не апеллирующее к чему-либо, что не может быть уяснено первокурсником)
.
Исходные данные. (скопипастено с http://www.intuit.ru/department/ds/theorysets/4/)Теорема Кантора
Множество бесконечных последовательностей нулей и единиц несчетно.
Доказательство
Предположим, что оно счетно. Тогда все последовательности нулей и единиц можно перенумеровать:
Составим бесконечную вниз таблицу, строками которой будут наши последовательности:
(через
мы обозначаем
j-й член
i-й последовательности). Теперь рассмотрим последовательность, образованную стоящими на диагонали членами
,
,
,
; ее
i-й член есть
и совпадает с
i-м членом
i-й последовательности. Заменив все члены на противоположные, мы получим последовательность
, у которой
так что последовательность
отличается от любой из последовательностей
(в позиции
i) и потому отсутствует в таблице. А мы предположили, что таблица включает в себя все последовательности - противоречие.
Мой тезис.Вышеприведённое доказательство -- ошибочно.
Обоснование тезиса.Прежде всего, оговоримся, что оперируем множеством
[0..1). Для лучшей иллюстративности, следует "свернуть" его в окружность с единичной длиной.
Для любого числа в любой позиционной системе счисления справедливо:
0.(t)=1.(0), где
t -- наибольшая цифра для данного основания СС, а круглые скобки -- обозначение периода дроби.
Поскольку доказательство Кантора не оговаривает основание СС, для которой оно справедливо, значит, мы имеем право записывать числа в ПСС с любым основанием. Например, в двоичной СС.
Создадим следующую таблицу, перечисляющую "все" числа:
0. 0.0000...
1. 0.1000...
2. 0.0100...
3. 0.1100...
4. 0.0010...
5. 0.1010...
6. 0.0110...
7. 0.1110...
8. 0.0001...
...В строке с номером
n в дробной части стоит записанное в обратном порядке её двоичное цифровое представление, дополняемое справа необходимым (бесконечным) количеством нулей. Следуя указанному Кантором алгоритму, новополученное, "опровергающее" включение в исходный список число равно
0.(1). Что, вообще говоря, является единицей, но для исходного самозамкнутого множества
[0..1) -- нулём.
Можно заметить, что если
k -- количество подряд стоящих с начала дроби единиц, то числу с описанием "с
k единицами впереди" удовлетворяет, в числе прочих, строка с номером
. И нулевому числовому элементу вполне подходит формируемая алгоритмом цифровая последовательность в том смысле, что
Список составлен неправильно? Может, существует способ "правильного" составления списка?
Соображения.Если ошибался Кантор, а не я, то ошибка его в том, что он, оперируя с перечислимым бесконечным списком, забывает о бесконечности новообразованной цифровой последовательности. Таким образом, по приведённому мною примеру, можно "доказать" счётность
. И всё бы, вроде, хорошо, очередное, часто практикуемое на этом форуме, ниспровержение основ математики -- да только, совершенно непонятно, какой строке отвечает, например, значение
(1/3), записываемое как
0.(01). Очевидно, что доказательство непригодности определённого алгоритма к "желаемой нумерации" никак не влияет на теоретическую возможность/невозможность таковой нумерации: действительно, стандартный "метод зигзага", используемый для доказательства счётности множества
, нумерует как любую строку в исходном списке, так и всевозможные дроби, знаменатель коих не является произведением некоторых степеней каких-либо множителей, на которые разлагается основание СС. Тем же "методом зигзага" можно доказать счётность любого алгебраического числа.
Возникает вопрос, существует ли такой алфавит, на котором можно было бы выразить хотя бы все
подобным методом "выписывания в список"? Для этого основание СС должно делиться на любое из чисел натурального ряда. Не возьмусь судить, делится ли на них бесконечность, но, очевидно, это справедливо для нуля. Правда, совершенно не понятно, как его (число) в нулевом основании представить; кроме того, уже для единичного основания СС та перестаёт быть позиционной.
"Метод зигзага", в наиболее общем случае, означает алгоритм выбора очередного элемента множества по заданию самого множества и "истории выбора" предшествующих элементов. Вопрос о счётности или несчётности множества эквивалентен вопросу исчерпываемости множества бесконечной последовательностью таких выборок ("бесконечной историей"). Если мы можем каким-либо образом представить элемент, не входящий в множество, перебираемое алгоритмом, то несчётность доказана. Абстрагируя метод Кантора, можно считать, что "контралгоритм" описывается следующим образом: "Возьмём любой элемент множества, отличный от любого элемента выборки исходного алгоритма". Вопрос в том, с какой стати принимать на веру существование хотя бы одного такого элемента? На конечном множестве, ИМХО, никому на трезвую голову не взбредёт искать элемент, отличный от любого, включённого в него. В крайнем случае, результатом такого поиска можно считать пустое множество. Какое принципиальное отличие множеств заставляет предположить, что на бесконечных множествах этот результат будет от пустого множества отличаться?
P.S. Возьмём алгоритм, последовательность выборки элементов которого сводима к "методу зигзага", обходящего последовательности, образованные исходным алгоритмом и множеством всех контралгоритмов...
Вопрос.И, (если мой тезис верен,) как всё таки доказать несчётность множества на
[0..1)?