Для всех тех, у кого несчётность R вызывает сомнения

[Cosinus]

Сменил название с Диагональный метод Кантора для доказательства несчётности на Для всех тех, у кого несчётность R вызывает сомнения: во избежание множения сущностей. Моё сомнение разрешилось, но с бесконечными множествами очень легко перемудрить. Так что пусть младые умы высказывают найденные ими "противоречия" здесь.

Интерлюдия.
На первом курсе матанализа неравномощность множеств {Q} и {R} нам обосновывали с помощью диагонального метода Кантора. Я убедился, что эта практика является общеупотребимой для ВУЗов моего города. Ни в коей мере не утверждаю, что |{Q}| = |{R}|, ибо интуитивно уверен в обратном, однако, хочу твёрдое тому доказательство. Диагональный метод вызывает серьёзные сомнения с моей стороны. Если я не прав, прошу указать на допущенную мной ошибку в рассуждениях. Если прав, то мне очень бы хотелось взгянуть на корректное доказательство (желательно, но не обязательно, не апеллирующее к чему-либо, что не может быть уяснено первокурсником) |{Q}| \neq |{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 единицами впереди" удовлетворяет, в числе прочих, строка с номером $2^k-1. И нулевому числовому элементу вполне подходит формируемая алгоритмом цифровая последовательность в том смысле, что $2^0-1 = 0
Список составлен неправильно? Может, существует способ "правильного" составления списка?

Соображения.
Если ошибался Кантор, а не я, то ошибка его в том, что он, оперируя с перечислимым бесконечным списком, забывает о бесконечности новообразованной цифровой последовательности. Таким образом, по приведённому мною примеру, можно "доказать" счётность {R}. И всё бы, вроде, хорошо, очередное, часто практикуемое на этом форуме, ниспровержение основ математики -- да только, совершенно непонятно, какой строке отвечает, например, значение (1/3), записываемое как 0.(01). Очевидно, что доказательство непригодности определённого алгоритма к "желаемой нумерации" никак не влияет на теоретическую возможность/невозможность таковой нумерации: действительно, стандартный "метод зигзага", используемый для доказательства счётности множества {Q}, нумерует как любую строку в исходном списке, так и всевозможные дроби, знаменатель коих не является произведением некоторых степеней каких-либо множителей, на которые разлагается основание СС. Тем же "методом зигзага" можно доказать счётность любого алгебраического числа.
Возникает вопрос, существует ли такой алфавит, на котором можно было бы выразить хотя бы все {Q} подобным методом "выписывания в список"? Для этого основание СС должно делиться на любое из чисел натурального ряда. Не возьмусь судить, делится ли на них бесконечность, но, очевидно, это справедливо для нуля. Правда, совершенно не понятно, как его (число) в нулевом основании представить; кроме того, уже для единичного основания СС та перестаёт быть позиционной.

"Метод зигзага", в наиболее общем случае, означает алгоритм выбора очередного элемента множества по заданию самого множества и "истории выбора" предшествующих элементов. Вопрос о счётности или несчётности множества эквивалентен вопросу исчерпываемости множества бесконечной последовательностью таких выборок ("бесконечной историей"). Если мы можем каким-либо образом представить элемент, не входящий в множество, перебираемое алгоритмом, то несчётность доказана. Абстрагируя метод Кантора, можно считать, что "контралгоритм" описывается следующим образом: "Возьмём любой элемент множества, отличный от любого элемента выборки исходного алгоритма". Вопрос в том, с какой стати принимать на веру существование хотя бы одного такого элемента? На конечном множестве, ИМХО, никому на трезвую голову не взбредёт искать элемент, отличный от любого, включённого в него. В крайнем случае, результатом такого поиска можно считать пустое множество. Какое принципиальное отличие множеств заставляет предположить, что на бесконечных множествах этот результат будет от пустого множества отличаться?
P.S. Возьмём алгоритм, последовательность выборки элементов которого сводима к "методу зигзага", обходящего последовательности, образованные исходным алгоритмом и множеством всех контралгоритмов...

Вопрос.
И, (если мой тезис верен,) как всё таки доказать несчётность множества на [0..1)?

[PAV]

Ох, придется мне по такому случаю временно вернуться...

Первое. У Вас утверждение сформулировано так: множество всех последовательностей, состоящих из нулей и единиц, несчетно. Диагональный метод это безусловно доказывает. В Вашем примере таблица не содержит последовательности, состоящей из одних единиц, которую диагональный метод Вам и предъявил в качестве контрпримера.

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

Обойти эту сложность можно двумя путями. Первый - заметить, что множество всех "неправильных" последовательностей счетно. Поэтому если бы множество вещественных чисел было бы счетно, то объединение двух счетных множеств давало бы также счетное множество всех последовательностей, что противоречит доказанному.

Второй метод - использовать любое основание системы счисления $n>2$. Потому что тогда при построении контрпримера можно выбирать очередную цифру, отличную и от написанной, и от цифры $n-1$. Например, в десятичном случае можно построить контрпример, который вообще не содержит ни одной девятки. Он обязательно соответствует некоторому вещественному числу.

Все, снова ухожу...

[TOTAL]

Cosinus писал(а):

Если прав, то мне очень бы хотелось взгянуть на корректное доказательство

Вы не прав, поэтому Вам очень не хотелось бы взглянуть на корректное доказательство.

[Brukvalub]

Сшит кафтан по-Давидюковски....

[id]

Однако, какая солидарность в голосовании...

[Someone]

Cosinus в сообщении #162183 писал(а):

Теорема Кантора

Множество бесконечных последовательностей нулей и единиц несчетно.

Cosinus в сообщении #162183 писал(а):

Мой тезис.
Вышеприведённое доказательство -- ошибочно.

Обоснование тезиса.
Прежде всего, оговоримся, что оперируем множеством [0..1). Для лучшей иллюстративности, следует "свернуть" его в окружность с единичной длиной.

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

Cosinus в сообщении #162183 писал(а):

Если ошибался Кантор, а не я, то ошибка его в том, что он, оперируя с перечислимым бесконечным списком, забывает о бесконечности новообразованной цифровой последовательности.

А Вы доказательство Кантора читали? Работа называется "Об одном свойстве совокупности всех действительных алгебраических чисел" (Георг Кантор. Труды по теории множеств. Москва, "Наука", 1985).

Так вот, нет там ничего похожего на то, о чём Вы говорите. Кантор строит стягивающуюся последовательность вложенных отрезков, пересечение которой заведомо не содержит ни одного элемента заданной последовательности.

Cosinus в сообщении #162183 писал(а):

Поскольку доказательство Кантора не оговаривает основание СС, для которой оно справедливо, значит, мы имеем право записывать числа в ПСС с любым основанием. Например, в двоичной СС.

Кантор действительно не оговаривает основание системы счисления, поскольку он никакой системой счисления в доказательстве не пользуется.

В тех же случаях, когда доказательство использует запись в какой-либо системе счисления, эта система счисления берётся вполне конкретной, и при аккуратном доказательстве принимаются специальные меры, чтобы избежать чисел, допускающих двойную запись. Впрочем, эти "специальные меры" очень простые. Если основание системы счисления больше 3, то при построении числа, отсутствующего в списке, пользуемся только цифрами 1 и 2. Если же основание равно 2 или 3, то объединяем цифры попарно (0,10'11'00'00'01'...) и заменяем не отдельные цифры, а их пары: если $k$-тая пара $k$-того числа не есть 01, то пишем 01, а если она есть 01, то пишем 10.

Cosinus в сообщении #162183 писал(а):

P.S. Возьмём алгоритм, последовательность выборки элементов которого сводима к "методу зигзага", обходящего последовательности, образованные исходным алгоритмом и множеством всех контралгоритмов...

Вот я указал один единственный "контралгоритм", который угробливает все возможные "алгоритмы". Воспользуйтесь "методом зигзага" и постройте алгоритм, который "обходит" этот "контралгоритм".

P.S. Вас не смущает "солидарность в голосовании", которую заметил id? Я сам не голосовал, но результаты посмотрел.

P.P.S. А что вообще эта тема делает в данном разделе? Вы действительно хотите разобраться?

[Алексей К.]

Someone в сообщении #162750 писал(а):

Вы действительно хотите разобраться?

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

[Cosinus]

Приношу свои извинения за долгое отсутствие.

PAV писал(а):

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

Истинно так.

PAV писал(а):

После этого отдельным утверждением можно показать, что множество всех последовательностей равномощно множеству вещественных чисел.

Кстати, как это сделать? Двойным неравенством, насколько я могу судить, не получится...

PAV писал(а):

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

Обойти эту сложность можно двумя путями. Первый - заметить, что множество всех "неправильных" последовательностей счетно. Поэтому если бы множество вещественных чисел было бы счетно, то объединение двух счетных множеств давало бы также счетное множество всех последовательностей, что противоречит доказанному.

Согласен.

TOTAL писал(а):

Cosinus писал(а):

Если прав, то мне очень бы хотелось взгянуть на корректное доказательство

Вы не прав, поэтому Вам очень не хотелось бы взглянуть на корректное доказательство.

Как коварны бывают математики...

Someone писал(а):

А Вы доказательство Кантора читали? Работа называется "Об одном свойстве совокупности всех действительных алгебраических чисел" (Георг Кантор. Труды по теории множеств. Москва, "Наука", 1985).

Нет! Спасибо за наводку!

Someone писал(а):

В тех же случаях, когда доказательство использует запись в какой-либо системе счисления, эта система счисления берётся вполне конкретной, и при аккуратном доказательстве принимаются специальные меры, чтобы избежать чисел, допускающих двойную запись. Впрочем, эти "специальные меры" очень простые. Если основание системы счисления больше 3, то при построении числа, отсутствующего в списке, пользуемся только цифрами 1 и 2. Если же основание равно 2 или 3, то объединяем цифры попарно (0,10'11'00'00'01'...) и заменяем не отдельные цифры, а их пары: если $k$-тая пара $k$-того числа не есть 01, то пишем 01, а если она есть 01, то пишем 10.

Ясно.

Someone писал(а):

Cosinus в сообщении #162183 писал(а):

P.S. Возьмём алгоритм, последовательность выборки элементов которого сводима к "методу зигзага", обходящего последовательности, образованные исходным алгоритмом и множеством всех контралгоритмов...

Вот я указал один единственный "контралгоритм", который угробливает все возможные "алгоритмы". Воспользуйтесь "методом зигзага" и постройте алгоритм, который "обходит" этот "контралгоритм".

Не в силах.

Someone писал(а):

P.S. Вас не смущает "солидарность в голосовании", которую заметил id? Я сам не голосовал, но результаты посмотрел.

P.P.S. А что вообще эта тема делает в данном разделе? Вы действительно хотите разобраться?

Не смущает. Очевидно, верен либо второй, либо третий вариант. Оставалось лишь узнать -- какой именно. Голосую за "автор спятил". ^_^




Что меня навело на ошибочные рассуждения?
Пофантазируем. Создадим "всесодержащую" таблицу, i-ая строка которой отличается от диагонали лишь i-ым элементом. Вопрос стоял в том -- может ли строка c "бесконечным номером" (отличающаяся "в бесконечном знаке") содержать новопостроенную диагональ? Иначе говоря, можно ли считать, что осуществляется предельный переход? С одной стороны, нет, ибо в противном случае можно было бы явно указать номер, в котором переход осуществился бы. С другой, что нам мешает добавить эту "самоневходящуюся" строку в начало нашего списка (с номером "нуль")? Логично, что мы не сможем достроить по квазидиагональному методу (новая последовательность отличается от любой построенной последовательности хотя бы одним разрядом, но покрытие натурального ряда номерами разрядов происходит не обязательно в порядке соответствия разряда строке) новую строку, так как не сможем указать разряд, в коем отличается новая строка от исходной.
Это рассуждение неверно; кроме того, дальше я совершенно неправильно предположил, что x.(1)=(x+1).(0) в силу неосознанного предельного перехода в подобных последовательностях.


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


Благодарен Someone и PAV за пояснения!

[infoliokrat]

Так как тут впервые (заглянул с ВИКИ с унарной системы счисления, как автор записи любого числа только одной цифрой), то естественно задаю 1-й вопрос всем пессимистам и оптимистам: изменится ли ваша точка зрения, если вы убедитесь, что любое число можно записать только одной цифрой?
Любые вопросы типа:
-какой строке отвечает, например, значение (1/3), записываемое как 0.(01)
будут иметь однозначный ответ, причем номер такой строки ОДНОЗНАЧНО определят "соседа" слева и/или справа. (кажется никакое "Диагональное число" вышеупомянутым способом не получится - цифра то лишь одна). З павагай= уважением

[infoliokrat]

Cosinus
Для каждого числа сопоставим последовательность только из одних 111111111111111
Например, для 1/3, котрая записывается в виде 0,(3), очевидно получится последовательность чисел типа 0,3 0,33 0,333 .... 0,3333333.. каждому из которых естественно будет соответствовать только один набор одинаковых цифр после разделительной ,11111111... То, что таких последовательностей сколько угодно много не смущает даже всех математиков, ведь натуральные все числа счётны, и даже натуральное в степени натуральное тоже счётно. Аналогично и для всех иных периодических и НЕПЕРИОДИЧЕСКИХ дробей будет получаться соответствующая однозначно последовательность единиц (об этом дискутировали на КаспаровЧесс в Университет Философия науки). Как по мне, то получилось, что
КОНТИНУУМ придумали люди.
НО в этой, т.н. единичной 1математике многое видится иначе. Например, см. Сходимость суммы членов ряда 1/2 +1/3 +1/4+ ... , который считается не сходящимся и т.п.
З павагай

[ewert]

infoliokrat в сообщении #270831 писал(а):

, и даже натуральное в степени натуральное тоже счётно.

Увы. Даже два в степени натуральное -- уже несчётно.

[Профессор Снэйп]

(Оффтоп)

infoliokrat в сообщении #270831 писал(а):

З павагай

Что это значит? И первое слово какое: цифра "3" или буква "З"?

[infoliokrat]

ewert в сообщении #270834 писал(а):

infoliokrat в сообщении #270831 писал(а):

, и даже натуральное в степени натуральное тоже счётно.

Увы. Даже два в степени натуральное -- уже несчётно.

А что, уже такое постановление есть? (два в степени натуральное -- уже несчёт..)
Просто в прошлом тысячелетии, когда был инженером-конструктором, то помню выписывал книгу типа " Дискретная математика для инженеров"
Поиск выдал
1. Кузнецов О.П., Адельсон-Вельский Г.М. — Дискретная математика для инженера...
Изложены основные понятия теории множеств, общей алгебры, логики, теории графов, теории алгоритмов и формальных систем. Для инженеров, специализирующихся в области автоматизированного управления и проектирования, вычислительной техники...
Но на моём древнем компе ОНА не открывается (местные сбои). Там точно была доказана и обоснована счётность: сначала натуральное в степени два, потом два в степени натуральное, и просто сказано было, что натуральное в степени натуральное- тоже стчётно. Хотите верьте, хотите проверьте. З павагай

-- Вс дек 13, 2009 19:28:55 --

(Оффтоп)

Офтопик — Википедия
Оффто́пик (иначе офто́пик, оффтоп от англ. off topic) (дословный перевод "вне темы")— любое сетевое сообщение, выходящее за рамки заранее установленной темы общения.
ru.wikipedia.org/wiki/Офф сохраненная копия еще с сайта
2. Оффтопик — Lurkmore
Оффтоп (also офтоп, офтопик, оффтопик, овтоб, автоб или ахтоб(на худой таки конец)) (англ. «off topic» — вне темы) — процесс превращения унылого топика в интересную дискуссию или просто постинг сообщений не по теме обсуждения.

Уважаемый Профессор Снэйп, это + или - для счётности континуума: или где и какая тема будет ПО ТЕМЕ на эту тему... З (предлог, а не цифра 3) павагай

[PAV]

infoliokrat в сообщении #271118 писал(а):

Там точно была доказана и обоснована счётность: сначала натуральное в степени два, потом два в степени натуральное, и просто сказано было, что натуральное в степени натуральное- тоже стчётно. Хотите верьте, хотите проверьте.

Проверил. Это неправда, нет там такого утверждения. Натуральное в степени 2 (и вообще в любой конечной степени) - да, а 2 в степени натуральное - нет. И не может быть, потому что это очевидно неверно, так как два в степени натуральное - это практически то же самое, что и множество всех вещественных чисел.

[ewert]

infoliokrat в сообщении #271118 писал(а):

натуральное в степени натуральное- тоже стчётно.

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

И совсем другое дело -- "натуральный ряд" (сиречь множество натуральных чисел) в своей собственной степени. В теоретико-множественном смысле. Это -- уже совсем другой вопрос.

-- Вс дек 13, 2009 21:50:59 --

(Оффтоп)

Профессор Снэйп в сообщении #270857 писал(а):

infoliokrat в сообщении #270831 писал(а):

З павагай

Что это значит? И первое слово какое: цифра "3" или буква "З"?

Он ранее уж расшифровывал. Это -- по-украински. В вольном переводе означает "с почтением".