Comments 55
Но т.к. есть алгоритм, то и есть взаимо-однозначное соответсвие.Простите, но соответсвтвие между чем и чем?
Между числом, и порякдовым номером, которого не существует, ибо алгоритм никогда не выполнится, так?
Число Pi/4 мы уточняем знак за знаком, это бесконечный итеративный процесс. По мере получения очередного знака, мы получаем конкретное число и вычисляем для него порядковый номер.
Т.е. бесконечную непереодическую дробь — можно рассматривать как несуществующее число, а можно рассматривать, как результат работы некоторого бесконечного алгоритма, который на каждом шаге выдает очередную цифру и в этом смысле порядковый номер можно тоже рассматривать как некое число, являющееся результатом работы бесконечного алгоритма.
А что является результатом работы алгоритма, который не завершится никогда? Рассуждая на пальцах: либо «ничего» (или другой определённый конкретный ответ), и тогда все иррациональные числа имеют «одинаковый номер» — нет однозначности, либо «не определено», и тогда мы не можем сравнить номера, как следствие, не можем проверить однозначность соответствия.
Или, например, так: вот для двух разных «конечных рациональных» чисел при грамотно построенной нумерации (например, по квадрату) всегда будет два конечных номера, которые можно сравнить и убедиться, что номера разные. А как сравнить между собой два бесконечных номера?
Есть существование числа самого по себе, а есть конкретная запись числа. Мы можем абстрагироваться от конкретных цифр числа — просто введя обозначение, например Pi/4. Точно также, мы можем асбтрагировать номер этого числа, пусть порядковый номер числа Pi/4 будет C(Pi/4). И в этом смысле он также существует сам по себе. Где противоречие?
Точно также, мы можем асбтрагировать номер этого числа, пусть порядковый номер числа Pi/4 будет C(Pi/4).Отлично. И какому числу сооствествует номер С(Pi/4)+1?
Пока идей как это сделать нет.
Но т.к. есть алгоритм, то и есть взаимо-однозначное соответсвие.А это значит что ваши «доказательства» бездоказательны :)
Я даже упрощу задачу… Вместо нахождения самого числа
Rev(C(Pi/4) + 1) просто определите больше оно или меньше чем Pi/4.Еще один изъян алгоритма, описан с комментарии: habr.com/post/358526/#comment_11354864.
Как его устранить — пока тоже нет идей.
Согласен, что взаимо-однозначного соответсвия нетЗамечатель, получается заголовок статьи прямо сейчас врет. Надеюсь вы его поправите.
но алгоритм устанавливает соответсвие в одну сторону каждому R на [0,1] ставит в соответствие NИ все равно вы за свое… Еще одна задачка для вас: что больше, C(Pi/4) или C(Pi/3) (вы же их «пронумеровали», т.е. дали порядковый номер)?
Предлагаю рассмотреть числа: Pi/4 и Pi/5.
Алгоритм проходит по всем уровням последовательно, сверу вниз, а на каждом уровне слева направо, от меньших чисел к большим, поэтому C(Pi/5) < C(Pi/4).
Pi/3 > 1, выходит за интервал [0,1].Да, мой косяк. Надо конечно Pi/5.
Алгоритм проходит по всем уровням последовательно, сверу вниз, а на каждом уровне слева направо, от меньших чисел к большим, поэтому C(Pi/5) < C(Pi/4).Как интересно… ну раз
C(Pi/5) < C(Pi/4)то чему тогда равно C(Pi/4) - C(Pi/5).
В вашем подходе, чтобы число было пронумерованно, должна существовать запись этого числа принадлежащая какому-то уровню. Соответственно вопрос, существует ли такая запись иррационального числа (например, Pi/5, как предрагалось раньше), которая принадлежит хоть какому-то уровню?
Или другими словами, вы утверждаете, что ваш алгоритм перебирает все вещественные числа, но доказательство этого вы не привели, а лишь ограничились фразой:
мы можем пронумеровать все числа из диапазона [0,1], т.к. мы последовательно проходим по каждому уровню и последовательно нумеруем все возможные комбинации на данном уровне
Которая говорит толькто то, что вы можете пронумеровать все числа, которые можно вписать в вашу таблицу, но из этого никак не следует что все вещественные числа могут быть вписаны в вашу таблицу. На этом диагональный принцип как раз и строится, он предъявляет число, которое нельзя вписать в таблицу, пусть и немного другой структуры.
Проблема в том, что и для многих рациональных чисел не подобрать номер.
Например 1/3.
Возьмем сколь угодно большое число, X.
Разложим его на сумму степеней двойки: X = 2^1 + 2^2 +… + 2^k + L(k+1)
Если L(k+1) — нечтное — то цифра на уровне k+1 — 1, если четное — то — 0.
Далее, используя соотношение: Lk = (Lk-1 — 1)*S + N + 1, мы всегда сможем вычислить порядковый номер цифры для предыдущего уровня.
Т.о. двигясь в сторону корня дерева (вверх) и мы в итоге построим конкретное десятичное число, которому соответсвует данный номер.
Но это подразумевает, что мы должны использовать опредленное значение номера. Т.е. если рассмотреть номер для числа Pi/5 — число С(Pi/5), то обратное восстановление невозможно в силу того, что сам номер — не определен, т.к. он вычисляется бесконечно долго. Как-то так…
Возьмем сколь угодно большое число, X.Ну давайте, разложите C(Pi/4). Даже любопытно.
Разложим его на сумму степеней двойки: X = 2^1 + 2^2 +… + 2^k + L(k+1)
Если L(k+1) — нечтное — то цифра на уровне k+1 — 1, если четное — то — 0.
Кстати, а C(Pi/4) само четное или нечетное?
Т.о. двигясь в сторону корня дерева (вверх) и мы в итоге построим конкретное десятичное число, которому соответсвует данный номер.Движение как-бы надо начать из некой позиции.
Т.е. если рассмотреть номер для числа Pi/5 — число С(Pi/5), то обратное восстановление невозможно в силу того, что сам номер — не определен, т.к. он вычисляется бесконечно долго. Как-то так…Т.е. все что вы тут предложили ранее, это не работает и чушь, причем вы это сами понимаете?
Число существует не потому что мы дали ему имя/обозначение. Я тоже могу ввести число Гладина, которое в поле действительных чисел при делении на единицу не равно себе. От этого оно существовать не станет.
пусть порядковый номер числа Pi/4 будет C(Pi/4).
Отлично а зачем тогда ваше доказательство? Пусть для любого числа x из R его номер это n(x), где n пренадлежит N. Как вам такое "доказательство"?
Ваш алгоритм С никогда не заканчивается потому что для Pi/4 он выглядит так:
while True:
find_next_digit()Задача о том чтобы придумать несчетное число алгоритмов параметризованных вещесвтенным числом и задача о том чтобы построить взаимно однозначное соответсвие между множеством [0,1] и N — это разные задачи.
Но верно то, что между множеством Q и N бикция таки есть.
Есть существование числа самого по себе, а есть конкретная запись числа.Кстати, вот интересное следствие:
Существуют действительные (иррациональные) числа, которые не могут быть записаны конечным числом знаков, какую бы систему обозначений мы не приняли исходно.
P.S. кстати, а как в рамках рассматриваемой статьи определяется понятие действительного числа?
Вы пронумеровали все конечные десятичные (ну или двоичные) дроби. Но какому натуральному числу в вашей схеме будет соответствовать число 0,01001000100001… или примеры выше с Pi? Ваш алгоритм просто не завершится для этих чисел, нельзя просто сказать "и так далее до бесконечности", в этом то вся и проблема.
Бесконечные непериодические дроби у вас не получилось пронумеровать, т.е. не получилось построить биекцию (взаимно однозначное соответствие).
Я просто предлагаю рассматривать биекцию как алгоритм. Потому что само понятие «бесконечное число» по смысло ближе всего к понятию «бесконечно работающий алгоритм, генерирующий это число». В этом смысле мы можем пронумеровать числа на [0,1]. Просто мы никогда не узнаем точного номера числа 0,01001000100001…, т.к. никогда не узнаем, как выглядит число полностью.
Биекция не алгоритм (в конечном итоге). Это взаимно-однозначное отображение, т.е. соответствие каждому элементу одного множества ровно одного элемента другого множества и наоборот. Вы не можете сказать, что вот этому числу соответствует не элемент множества, а некий "бесконечно работающий алгоритм". 0.010010001… — это конкретная точка на прямой, и если построена биекция, то этой точке должно соответствовать конкретное число, а не нечто бесконечно генерящееся.
"Просто мы никогда не узнаем точного номера числа..." — неужели вы не понимаете, что такого числа просто не существует в вашей схеме?
Судя по вашим комментариям, вы представляете себе биекцию «вычислимых» чисел (для которых есть алгоритм, вычисляющий каждую цифру) и натурального ряда. Он существует. Но описываете не его. Всё это из-за того, что для бесконечной дроби не может быть следующей дроби. Какой хвост бы не поменяли, всё равно пропустим континуум чисел.
Только, если добавлять число «после» проверки нельзя, а можно только «до», то такой прикол не получится. Так как для любого набора бесконечного количества чисел можно найти такое, которое не совпадает со всеми по такой характеристике, которая счетно адресуется, вроде цифры с тем же номером, под которым число подсчитано.
Говоря проще, погружение в детализацию происходит быстрее чем перебор, и значит, различие вводится гораздо проще чем вводится равенство. Поэтому, различие счетного множества и несчетного легче доказывается, чем опровергается.
Но если думать, что счетное множество это не только те элементы которые можно посчитать, но и те которые можно «продолжать считать», то получится вот что:
«Мы эти понятия не различаем, поэтому они не различаются».
m — это количество знаков после запятой, n — алфавит системы счисления.
Иными словами, алгоритм подсчитывает количество размещений с повторениями для каждой позиции после запятой. Количество размещений увеличивается экспоненциально с каждой следующей позицией.
Для десятичных дробей, записанных в десятичной системы счисления алгоритм последовательно будет выдавать такой результат (порядковые номера присваиваются слева направо):
m = 1
0,0; 0,1; ...; 0,9 — всего 10 комбинаций.
m = 2
0,00; 0,01; 0,02; ...; 0,10; 0,11; ...; 0,90; 0,91; ...; 0,99
Т.о. для m=2 получается 100 комбинаций, а для обоих уровней общее количество комбинаций — уже 110.
m = 3
Т.о. для m=3 получается 1000 комбинаций
…
m = k
Количество всевозможных комбинаций — 10k
k — растет линейно, а количество комбинаций, соответствующее k — экспоненциально.
2. Давайте посмотрим на ваши таблицы и заметим что талица уровня 2 включает все числа, которые есть на уровне 1, таблица уровня 3 включает все числа которые есть в таблицах на уровнях 1 и 2, и так далее. Т. е. другими словами несколько уровней не добавляют ровным счетом ничего, вы с тем же успехом можете рассматривать «предельную таблицу» в которой все числа имеют бесконечное число разрядов, потому как она будет содержать все числа, котороые есть в каждой из «конечных таблиц». И, сюрприз-сюрприз, согласно аргументу Кантора, который вы так легко отвергли, найдется такое число, которого не будет в этой «предельной таблице».
3. Скорость роста на которую вы ссылаетесь никакого отношение к определеню счетности не имеет, соответсвенно скорость роста каких-то там функций ни на что не влияет.
2 — кстати (целая волна каментов выше) любое упоминание Pi в этом контексте не уместно — Pi изначально ирациональное
Правильно ли я понял, что вы считаете, что всё множество действительных чисел счётно?
P.S. Если предложенный мной алгоритм имеет ошибку, которую я, в силу своей невнимательности, не вижу – большая просьба написать об этом в комментариях.
P.P.S Если же ошибки нет – то получается, что |[0,1]| = |N|! Т.е. ВСЕ действительные числа из диапазона [0,1] можно пронумеровать!
Идея была вот в чем.
В множестве иррациональных чисел – любое число, например, Pi, √2, √3, e, Pi/n, e/n, √2/n, √3/n и т.д. — имеет бесконечное множество символов в записи, но это конкретное число, которое существует само по себе.
Чтобы получить все цифры в записи иррационального можно, например, воспользоваться методом приближения иррациональных чисел рациональными, но этот процесс будет бесконечным и мы никогда не получим все знаки в иррациональном числе, но при этом, это вполне конкретное число, существующее само по себе! Т.о. иррациональное число можно представить как бесконечно работающий алгоритм, который на каждой очередной итерации уточняет данное число, при этом процесс уточнения происходит бесконечно. Вопрос 1. Если нельзя, то почему?
В предложенном подходе порядковый номер любого числа N из [0,1] (обозначаемый как C(N)) есть функция от конкретных цифр его записи.
В такой интерпретации, порядковый номер иррационального числа становится таким же не определенным, как и все циры в записи самого иррационального числа. Порядковый номер иррационального будет вычисляться также бесконечно долго, как и все цифры в записи этого числа. Вопрос 2. Но, если доказано, что рациональные числа существуют сами по себе, тогда почему мы не можем утверждать, что при такой (алгоритмической) интерпретации их порядковые номера тоже существуют сами по себе?
Рассмотрим пример. Обозначим порядковый номер числа Pi/5 как C(Pi/5). С алгоритмической точки зрения, все знаки в записи числа Pi/5 будут утояняться бесконечно долго, => порядковый номер C(Pi/5) тоже будет вычисляться бесконечно долго.
Переформирую вопрос.
Понятно ли, что отрезок [0, 1] и действительная прямая R равномощны?
1. Определение: континуум — мощность множества всех чисел из сегмента [0,1].
2. Теорема: множество континуума несчетно. Доказательство опирается на расмотренный выше диагональный метод Кантора.
3.… много разных определений, лемм, теорем…
4. Теорема Теорема Кантора — Бернштейна (упрощенно): если между множествами существует биекция, то |A| = |B|.
5. Устанавливаем биекцию между [0,1] и R, из чего, согласно (4) следует равномощность [0,1] и R.
Но, равномощность-то есть, однако несчетность — это пункт 2, а его доказательство опирается на диагональный метод Кантора, который, как я писал в статье вызывает у меня сомнения. Не могу объяснить, это на каком-то интуитивном уровне происходит.
Собственно, именно с целью прояснить этот момент (в первую очередь для себя), я и згорелся идей рассмотреть данный вопрос с другого ракурса, используя алгоритмический подход. Свои размышления я запостил на хабр с целью получить обратную связь от сообщества. Иногда так бывает, что самому трудно увидеть ошибку в своих же рассуждениях :-).
И, скорее всего, данный подход поможет (в первую очередь — мне) согласиться с правильностью диагонального метода Кантора. Т.к. у моего подхода уже вскрылось множество недостатков, за что спасибо всем, кто на все такие недостатки обратил внимание в комментариях.
С алгоритмической точки зрения, все знаки в записи числа Pi/5 будут утояняться бесконечно долго, => порядковый ном уточняетер C(Pi/5) тоже будет вычисляться бесконечно долго.Видите тут разницу? Уточняться vs вычисляться?
Уточняя некое число вы всегда можете остановиться и сказать «ну ок, мы получили число с заданной точностью. оно гарантированно лежит в таком-то диапазоне, ошибrа меньше чем некое конкретное число».
Т.о. иррациональное число можно представить как бесконечно работающий алгоритм, который на каждой очередной итерации уточняет данное число, при этом процесс уточнения происходит бесконечно.Ну, можете и так формулировать, если хотите.
В такой интерпретации, порядковый номер иррационального числа становится таким же не определенным, как и все циры в записи самого иррационального числа. Порядковый номер иррационального будет вычисляться также бесконечно долго, как и все цифры в записи этого числа.И тут уже «вычислятся» вместо «уточнятся». Айайай, как ловко (сарказм) вы поменяли одно на другое :)
Я сейчас прихожу к мысли, что мой подход, наоборот, только еще раз показывает несчетность континуума, только с другой стороны. Пытаясь пронумеровать [0,1] способом, который я привел, мы просто получим бесконечное множество бесконечных алгоритмов, которые никогда не вычслят точный порядковый номер иррационального числа.
На мой простой житейский взгляд, при "диагональном методе" актуальная бесконечность представляется в законченном виде, что приводит к парадоксам типа "множества всех множеств, которые не являются элементами самих себя". По поводу одного из таких парадоксов, в котором доказывается, что бесконечное множество всех натуральных чисел имеет последний (он же наибольший) элемент, см. мою статью с моим юмористическим мультфильмом: https://habr.com/ru/post/474426/
Насколько я знаю, у др. греков не было актуальной бесконечности, к примеру, прямая у них - это отрезок, который при необходимости можно продолжить в обе стороны.
Вызывает улыбку один комментарий: "Иррациональные числа существуют сами по себе, это доказано математически". Откуда взялись действительные числа? Это такая "аксиома", которая по-простому звучит так: давайте будем считать, что, куда ни ткни в числовую прямую остро заточенным карандашом, обязательно попадёшь на какое-то число, между числами нет промежутков, а иначе у нас не получатся красивые рассуждения из обл. анализа бесконечно малых и такие же красивые формулы. Поэтому числовая прямая и действительные числа на ней вообще непонятно что такое. А переход к пределу и "устремление к бесконечности", о которых говорят на лекциях по матанализу, - это такие мантры, "финты ушами" за которыми не стоит какой-то смысл. Хочешь - принимай, а иначе студент может выслушать лекцию на тему "Методы отчисления. Лекция № 1: метод последовательного исключения" (шутка, если кто не понял).
Я подумал раза 2 и, кажется, нашёл число, которое Кантор пропустил в своей диагональной таблице: рассмотрим, напр., десятичное представление корня из двух минус один: 0,4142... Теперь рассмотрим его справа налево: ...2414 (ноль с запятой отбросим за ненадобностью). Это десятичная часть какого-то числа, которое начинается с бесконечности и заканчивается на 4. В каком месте таблицы у Кантора оно стоит? А если кто-то скажет, что так делать нельзя, то возникает вопрос: почему Кантору можно, а мне нельзя по-всякому работать с бесконечностями? Можете вы доказать, что так делать нельзя? :-)
при "диагональном методе" актуальная бесконечность представляется в законченном виде
AFAIK, в серьёзной математике «актуальная бесконечность» возникает только при неформальном объяснении каких-то идей или построений. Так-то всё формально: есть теория, есть аксиомы, если теорема, есть доказательство.
Откуда взялись действительные числа? Это такая "аксиома"
Да, это система аксиом, без кавычек. Кстати, каких именно? Там их несколько.
А переход к пределу и "устремление к бесконечности", о которых говорят на лекциях по матанализу, - это такие мантры, "финты ушами" за которыми не стоит какой-то смысл
Плохое преподавание не является аргументом в текущей теме, хотя и проблема в целом.
почему Кантору можно, а мне нельзя по-всякому работать с бесконечностями?
(отвечаю на другой вопрос: что было у Кантора такого, чего не хватает в приведённом построении)
У Кантора была на руках теорема о том, что любой последовательность цифр (т.е. функции N → {0,1,2,3,4,5,6,7,8,9}) однозначно сопоставляется числу на отрезке [0,1], а каждое число может быть представлено последовательностью цифр. К слову, его построение подходит для доказательства несчётности функций с числовым аргументом и хотя бы двумя объектами в области значений, напр., N → {0,1}.
Можете вы доказать, что так делать нельзя?
Это Ваша задача доказывать, а наша — проверять доказательство. Например, корректность канторовых построений в соответствующей формальной теории доказывается, поэтому с ними считаются.
Пронумеровать все действительные числа на отрезке [0,1]