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

[Nxx]

Цитата:

Зачем Вы устраиваете ПРОВОКАЦИИ? Пробуете себя в роли тролля, или тролльскую квалификацию повышаете? В заголовке Вы пишете: "Множество вещественных чисел счетно?".
А потом плавненько подменяете тему на обсуждение конструктивизма.
Нехорошо...с....

Извините, не понял о чем вы. Я еще в институте преподавателя доставал с этим вопросом, так как изложение теории вещественных чисел мне было совершенно не понятно. Только он не понял, что я сказать хотел.

[bot]

Brukvalub в сообщении #181285 писал(а):

Зачем Вы устраиваете ПРОВОКАЦИИ?

Похоже, что так - прикидывается.

[TOTAL]

Nxx писал(а):

Что ж, из этого следует, что взаимно однозначного соответствия сделать нельзя, тем не менее ...

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

[Nxx]

Цитата:

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

Теорема Кантора основана на предположении, что если два множества равномощны, то существует между ними биекция. Но откуда следует это предположение?

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

Цитата:

Ну вот и всё. Вещественных чисел больше, чем счетное множество.

Если нет взаимно-отнозначного соответствия, это не значит, что их больше. Как я уже сказал, между натуральными и вычислимыми числами нет взаимно-однозначного соответствия, но вычислимых чисел не больше, чем натуральных (так как все алгоритмы можно пронумеровать).

[bot]

И в самом деле прикидывается.

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

Теорема Кантора основана на предположении, что если два множества равномощны, то существует между ними биекция. Но откуда следует это предположение?

Это определение равномощности.

[Nxx]

Цитата:

Это определение равномощности.

Окей.

Пример:

Есть множества А и Б.

Б1 - подмножество Б
Б2 - надмножество Б

Между А и Б1 есть биекция
Между А и Б2 есть биекция.

Следует ли из этого, что множества А и Б равномощны?
Означает, что при этом неизбежно существует биекция из А в Б?

[id]

Nxx
Теорема Кантора-Бернштейна.

[Nxx]

id писал(а):

Теорема Кантора-Бернштейна.

Спасибо. Сейчас попробую разобраться.

[bot]

Вы собираетесь ещё и теорему Кантора-Берштейна опровергать?
С каких позиций?
Впрочем всё - надоело. Считайте вопрос риторическим.

[Brukvalub]

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

Спасибо. Сейчас попробую разобраться.

Вы, наверное, вообразили, что вы - первый клоун в этом жанре на этом форуме? Так сказать, торите новую тропу?
Спешу вас разочаровать. Здесь таких индейцев и до вас немало пробегало.
И перетирать одно и то же с клоунами, прикидывающимися, что они не имеют никаких представлений о действительных числах, нам ой как надоело.
Все ваши последующие реплики выдают вас с головой. Видно, что вы далеко не новичок в этой области, и намерено "ваньку" валяете.
Хотите нас повеселить - придумайте что-нибудь поновее, а то этот БАЯН вызывает только раздражение.
Да, и еще - не забудьте вступить в партию Давидюка!

[Nxx]

Цитата:

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

Вот ерунда. Я правда, не понимаю. Попробую сформулировать конкретнее.

Добавлено спустя 36 минут 59 секунд:

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

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

У Давидюка множество верных последователей...

Когструктивные (вычислимые, алгоритмически определяемые) действительные числа - сложная тема, и подходить к ней с наскоку, имея кашу в голове, не рекомендуется. Прежде чем начинать о них рассуждать, для начала следует хорошо изучить классическую теорию; теоремы Кантора, Кантора-Бернштейна и т. д.

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

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

Nxx писал(а):

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

Для каждого вычислимого действительного числа по определению существует алгоритм, вычисляющимй сходящуюся к нему последовательность рациональных чисел. Множество же всех алгоритмов счётно

Вообще, если уж вести дальше разговор на эту тему, давайте зафиксируем определения. Классическое определение таково.

Действительное число $r$ называется вычислимым, если существует вычислимая последовательность рациональных чисел $\{ q_n \}_{n \in \mathbb{N}}$, такая что для любого $n$ справедливо неравенство $|r - q_n| < 2^{-n}$.

Последовательность рациональных чисел $\{ q_n \}_{n \in \mathbb{N}}$ называется вычислимой, если существует тройка рекурсивных функций $f, g, h : \mathbb{N} \to \mathbb{N}$, такая что $q_n = (f(n) - g(n))/(h(n) + 1)$ для любого $n \in \mathbb{N} = \{ 0, 1, 2, \ldots \}$.

Это классические определения. Но существуют и другие подходы...

[Nxx]

Цитата:

Для каждого вычислимого действительного числа по определению существует алгоритм, вычисляющимй сходящуюся к нему последовательность рациональных чисел. Множество же всех алгоритмов счётно

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

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

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

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

[PAV]

Brukvalub,
замечание за разжигание флейма в адрес участников. Добавлю - без наличия к этому каких-либо оснований. В данной теме автор не высказывал никаких грубостей ни в чей адрес, включая Кантора. Даже пока что не заметно, чтобы автор что-либо ниспровергал (поэтому и тема находится в этом разделе, а не в дискуссионных темах). Автор лишь задает вопросы и вполне адекватно воспринимает ответы, кроме названия темы я пока никакого криминала не нахожу. Так что прекратите свои нападки. Я понимаю, что слова "счетность множества действительных чисел" для многих здесь - как красная тряпка для быка, но будьте объективны и не судите по одежке.

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

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

Nxx писал(а):

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

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

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

Добавлено спустя 8 минут 40 секунд:

Nxx писал(а):

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

Боже, ну при чём здесь теорема о неполноте! Какая же, право, у Вас в голове каша.

Чтобы не писать глупости, пользуйтесь в дальнейшем следующим очень простым правилом: если ссылаетесь на какую-то теорему, будьте готовы её сформулировать.