Существует ли биекция между вычислимыми числами и нат.?

[Nxx]

Цитата:

Сходимость определена не для алгоритмов, а для последовательность. Алгоритм, сходящийся к действительному числу - это нонсенс.

Если хотите разумных ответов, выражайтесь точнее.

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

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

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


Соответственно, возникает вопрос: правомерно ли называть равномощными два множества, если между ними принципиально невозможно построить биекцию (хотя ни одно из них не превосходит по мощности другое)?

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

Nxx писал(а):

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

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

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


Соответственно, возникает вопрос: правомерно ли называть равномощными два множества, если между ними принципиально невозможно построить биекцию (хотя ни одно из них не превосходит по мощности другое)?

Опять голова пухнет! К примеру, что означает фраза "алгоритмы,... переходящие в режим бесконечного нециклического развития при определенных значениях N." Я уже не один десяток лет занимаюсь теорией вычислимости, но не знаю, что такое "режим бесконечного нециклического развития" алгоритма.

Ну да ладно, постараемся быть максимально дружелюбными.

Определение мощности даётся в рамках неконструктивной математики. Биекция, которая Вас интересует, не обязана быть вычислимой. Либо смиритесь с существованием невычислимых функций, либо забудьте о мощностях!

Такой ответ Вас устроит? Или требуются пояснения? Если да, то начните сами; дайте определение счётного множества.

[Nxx]

Цитата:

Биекция, которая Вас интересует, не обязана быть вычислимой.

Опс, вот это сюрприз! А откуда следует, что принципиально невычислимая биекция вообще может существовать? Может быть, правильнее сказать, что биекции просто нет, раз ее ни найти, ни показать нельзя?

Цитата:

Либо смиритесь с существованием невычислимых функций, либо забудьте о мощностях!

То есть, следует читать "либо смиритесь с существованием генератора случайных чисел, либо забудьте о понятии мощности множества"?

[TOTAL]

Nxx писал(а):

Может быть, правильнее сказать, что биекции просто нет, раз ее ни найти, ни показать нельзя?

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

[Nxx]

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

TOTAL писал(а):

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

Еслди про функцию вообще ничего нельзя сказать принципиально (например, функция случайная), то такой функции просто не существует без привлечения нерекурсивного оракула (=она невычислима). Если про функцию просто что-то не известно, но она вычислима, то и корни вычислимы, но неизвестны.

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

Nxx писал(а):

А откуда следует, что принципиально невычислимая биекция вообще может существовать?

Невычислимая биекция существует, так как её существование можно доказать в аксиоматической теории множеств.

Такое чувство, что Nxx --- это хитро замаскированный Давидюк, который вернулся сюда пудрить людям мозги.

Nxx писал(а):

Может быть, правильнее сказать, что биекции просто нет, раз ее ни найти, ни показать нельзя?

Для кого правильнее? Для конструктивиста, может быть, и правильнее, но для ортодоксального математика --- нет. Вы сам-то кто?

Nxx писал(а):

То есть, следует читать "либо смиритесь с существованием генератора случайных чисел, либо забудьте о понятии мощности множества"?

Какой ещё "генератор случайных чисел"? Если Вы таким хитрым образом пытаетесь указать на невычислимую функцию, то да: либо смиритесь с существованием невычислимых функций, либо забудьте о понятии мощности множества.

Давайте ещё раз по пунктам.

1) В рамках классической математики множество действительных чисел несчётно. У него есть счётное подмножество --- множество конструктивных действительных чисел. Между множеством конструктивных действительных чисел и множеством натуральных чисел существует много биекций, но ни одна из них не вычислима.

2) В рамках конструктивной математики существуют только те действительные числа, которые мы в рамках классической математики называем конструктивными. Между ними и натуральным рядом не существует биекции (поскольку в конструктивной математике все отображения, которые существуют, вычислимы). Так что множество действительных чисел опять же оказывается "несчётным" Слово "несчётный" взято в кавычки, поскольку в конструктивной математике мощностей, как таковых, нет. Есть некоторые наработки, дающие аналоги понятия мощности, но это немного не то.

Вообще, последовательным конструктивистом быть очень сложно. У них, если что, и логика другая: в частности, они не признают закон исключённого третьего и доказательств от противного. А у Nxx в голове каша, и мне кажется, что он злонамеренно разжигает этот флейм. Я согласен с мнением Brukvalub по его поводу; PAV поспешил с оправданием.

[TOTAL]

Nxx писал(а):

Тут несколько другая ситуация. По определению, два множества являются равномощными, если можно построить между ними биекцию.

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

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

TOTAL писал(а):

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

У конструктивистов именно так! А классические математики допускают существование невычислимых функций. Nxx же хочет посидеть на двух стульях разом.

[PAV]

Nxx в сообщении #181375 писал(а):

По определению, два множества являются равномощными, если можно построить между ними биекцию.

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

Еще раз напоминаю про необходимость сменить название темы на более нейтральное. Указания модераторов необходимо выполнять. Или я действительно ошибся и обвинения в Ваш адрес в итоге оказались справедливыми?

Добавлено спустя 3 минуты 1 секунду:

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

А у Nxx в голове каша

На то и существуют преподаватели, чтобы каши в голове помогать разгребать.

[Nxx]

Цитата:

Невычислимая биекция существует, так как её существование можно доказать в аксиоматической теории множеств.

Используется ли для этого аксиома выбора?

Цитата:

Для кого правильнее? Для конструктивиста, может быть, и
правильнее, но для ортодоксального математика --- нет. Вы сам-то кто?

Я признаю закон исключенного третьего и доказательства от противного. Значит, я - не конструктивист?

Цитата:

А у Nxx в голове каша, и мне кажется, что он злонамеренно разжигает этот флейм.

Если бы у меня не было каши в голове после курса матана, я бы ничего тут не спрашивал.

Добавлено спустя 3 минуты 34 секунды:

Цитата:

Еще раз напоминаю про необходимость сменить название темы на более нейтральное. Указания модераторов необходимо выполнять. Или я действительно ошибся и обвинения в Ваш адрес в итоге оказались справедливыми?

По-моему, прежнее название довольно точно отражало мое непонимание, но раз вы настаиваете, я сменил название.

[PAV]

Nxx в сообщении #181394 писал(а):

Значит, я - не конструктивист?

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

[Nxx]

PAV писал(а):

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

То есть, или доказательства от противного, или невычислимая биекция существует? Значит ли это, что ее существование доказывается методом "от противного"?

[PAV]

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

Nxx в сообщении #181399 писал(а):

Значит ли это, что ее существование доказывается методом "от противного"?

Да, полагаю что метод "от противного" там фигурирует. Пусть знатоки лучше ответят.

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

Nxx писал(а):

Цитата:

Невычислимая биекция существует, так как её существование можно доказать в аксиоматической теории множеств.

Используется ли для этого аксиома выбора?

Нет.

Nxx писал(а):

Я признаю закон исключенного третьего и доказательства от противного. Значит, я - не конструктивист?

Да. Вы действительно не конструктивист.

Nxx писал(а):

Если бы у меня не было каши в голове после курса матана, я бы ничего тут не спрашивал.

Так, может, Вам стоит для начала повторить курс матана и попытаться разобраться в нём?

Хотя матан, собственно, здесь не при чём. Мы говорим о матлогике.

Давайте сделаем так. Пусть у нас есть некоторое (эффективное) перечисление (возможно, с повторениями) всех алгоритмов: $A_0, A_1, A_2, \ldots$. Некоторые алгоритмы задают конструктивное действительное число (то есть генерируют последовательность рациональных чисел, сходящуюся к действительному числу с заданной оценкой скорости сходимости), а некоторые - нет. Пусть $n_0$ --- некоторое число, такое что алгоритм $A_{n_0}$ задаёт конструктивное действительное число. Мы можем определить функцию из $\mathbb{N}$ в $\mathbb{N}$ следующим образом:

$$ f(0) = n_0 $$

$f(i+1)$ равно минимальному натуральному числу $n$, такому что алгоритм $A_n$ задаёт конструктивное действительное число, отличное от чисел, задаваемых алгоритмами $A_{f(0)}, \ldots, A_{f(i)}$.

Тогда отображение, сопоставляющее каждому натуральному числу $n$ конструктивное действительное число, задаваемое алгоритмом $A_{f(n)}$, будет являться биекцией между множеством всех натуральных чисел и множеством всех конструктивных действительных чисел.

Функция $f$, естественно, не вычислима (это можно доказать. сведя к ней проблему остановки или проблему равенства конструктивных действительных чисел). Однако в рамках классической математики она построена совершенно законными методами (и даже без использования аксиомы выбора). Какие тут могут быть вопросы, не понимаю!

Добавлено спустя 4 минуты 15 секунд:

PAV писал(а):

Да, полагаю что метод "от противного" там фигурирует. Пусть знатоки лучше ответят.

Метод "от противного" не фигурирует. А закон исключённого третьего фигурирует. Вот в том построении биекции, которое я привёл выше, мы используем то, что для любого $n$ алгоритм $A_n$ либо задаёт конструктивное действительное число, либо не задаёт

[ИСН]

Знаете, Nxx, как онтогенез повторяет филогенез, так каждый человек должен повторять путь всего человечества. Вот и пройдите этот путь до Кантора, а конструктивистов - не надо, не надо, не трогайте. Совсем. Maybe later.
А то получится как учить геометрию Лобачевского параллельно с евклидовой - не понимая ни того, в чём разница, ни того, что таковая вообще есть.