Счётное неперечислимое множество

[Dialectic]

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

[Таня Тайс]

Sorry, я не знаю, что такое перечисляющий алгоритм,
но разве не может один и тот же алгоритм перечислять два и больше различных счётных множеств?

[Dialectic]

Таня Тайс в сообщении #230443 писал(а):

Sorry, я не знаю, что такое перечисляющий алгоритм,
но разве не может один и тот же алгоритм перечислять два и больше различных счётных множеств?

Когда речь идёт о перечислимом множестве, то имеют в виду, что существует вычислимая функция F определённая НА ВСЁМ натуральном ряду, множеством значений которой как раз и является требуемое множество. Т.е перечислимое множество, это множество значений некоторой вычислимой функции. Естественно, что множество значений функции
есть то, что оно есть т.е. оно единственно. А "перечисляющи алгоритм" это констатация того факта, что все значения некоторой вычислимой функции могут быть получены по единому алгоритму.

[Таня Тайс]

А разве не может один алгоритм с разными начальными значениями выдать нам два разных счётных множества? По-моему, да. И тогда Ваш вывод неверен.

Dialectic в сообщении #230439 писал(а):

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

[maxal]

Всё правильно.
Счётность - понятие математическое, перечислимость - алгоритмическое. Второе влечёт первое, но не наоборот.

[Таня Тайс]

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

[Dialectic]

Таня Тайс в сообщении #230447 писал(а):

А разве не может один алгоритм с разными начальными значениями выдать нам два разных счётных множества? По-моему, да. И тогда Ваш вывод неверен.

Dialectic в сообщении #230439 писал(а):

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

Дак я же специально написал большими буквами "НА ВСЁМ" натуральном ряду. Т.е. область опредления алгоритма есть ВЕСЬ натуральный ряд т.е мы уже его примени ко всему ряду, а не к кускам. А область значений, есть некоторое конретное множество. Оно и только оно а не некоторое его подмножество и есть перечислимое. Вообще, насколько мне известно, некоторое подмножество перечислимого множества тогда и только тогда само перечислимо, когда оно разрешимо. Хотелось бы получить подтверждение у специалистов словам "тогда и только тогда". Просто в том учебнике, что я читаю, сказано по другому "всякое разрешимое подмножество перечислимого множества перечислимо". Но ведь не сказано, что перечислимы только разрешимые подмножества...

[maxal]

А что неубедительного? Вот есть возрастающая функция $F$ из $\mathbb{N}$ в $\mathbb{N}$. Ей соответствует множество, которое она "перечисляет":

$$S = \{ F(i) \mid i=1,2,\dots \}.$$

Множество $S$ - счётное по определению, но вот перечислимым оно будет если и только если функция $F$ вычислима.

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

maxal в сообщении #230459 писал(а):

Множество $S$ - счётное по определению, но вот перечислимым оно будет если и только если функция $F$ вычислима.

Это неверно. Достаточно рассмотреть любое перечислимое, но не вычислимое множество. Оно будет, естественно, перечислимым, но не будет перечислимо в порядке возрастания.

-- Ср июл 22, 2009 13:08:10 --

Автору темы. Счётность множества означает, что в ZFC можно доказать наличие биекции между $\mathbb{N}$ и этим множеством. А перечислимость (более точно - алгоритмическая перечислимость) означает наличие вычислимой функции, для которой данное множество является областью значений. Это совершенно разные вещи. Не все функции, существование которых можно доказать в ZFC, вычислимы.

[Dialectic]

Здрасти Профессор Снэйп. Какая удача Вас повстречать! Пока Вы здесь ответте пожалуйста на один вопрос: верно ли, что те и только те подмножества перечислимого множества перечислимы, если они разрешимы? Как можно это можно доказать?Спасибо.

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

Dialectic в сообщении #230531 писал(а):

Здрасти Профессор Снэйп. Какая удача Вас повстречать! Пока Вы здесь ответте пожалуйста на один вопрос: верно ли, что те и только те подмножества перечислимого множества перечислимы, если они разрешимы? Как можно это можно доказать?Спасибо.

Нет, неверно.

Так как $\mathbb{N}$ перечислимо, то частным случаем Вашего является следующий вопрос: верно ли, что подмножество $\mathbb{N}$ перечислимо тогда и только тогда, когда оно разрешимо. Очевидно, это не так

[Dialectic]

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

Dialectic в сообщении #230531 писал(а):

Здрасти Профессор Снэйп. Какая удача Вас повстречать! Пока Вы здесь ответте пожалуйста на один вопрос: верно ли, что те и только те подмножества перечислимого множества перечислимы, если они разрешимы? Как можно это можно доказать?Спасибо.

Нет, неверно.

Так как $\mathbb{N}$ перечислимо, то частным случаем Вашего является следующий вопрос: верно ли, что подмножество $\mathbb{N}$ перечислимо тогда и только тогда, когда оно разрешимо. Очевидно, это не так

Ну я имел в виду "собственое подмножество" т.е. не такое, которое совпадает целиком с исходным множеством.Кстати, вроде любое множество разрешимо относительно себя. Или ВЫ что-то иное хотели сказать?

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

Dialectic в сообщении #230537 писал(а):

Ну я имел в виду "собственое подмножество" т.е. не такое, которое совпадает целиком с исходным множеством.Кстати, вроде любое множество разрешимо относительно себя. Или ВЫ что-то иное хотели сказать?

Честное слово, перестаньте маяться глупостями!!!!!

Dialectic в сообщении #230537 писал(а):

Ну я имел в виду "собственое подмножество" т.е. не такое, которое совпадает целиком с исходным множеством.

Хотите собственное подмножество? Ну уберите из $\mathbb{N}$ один элемент. К примеру, начните натуральный ряд с $1$, а не с $0$. Что-нибудь изменится?

Dialectic в сообщении #230537 писал(а):

Кстати, вроде любое множество разрешимо относительно себя.

Что Вы подразумеваете под "разрешимостью относительно себя". То, что любое множество сводится по Тьюрингу к самому себе? Это, безусловно, так.

Dialectic в сообщении #230537 писал(а):

Или ВЫ что-то иное хотели сказать?

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

[Dialectic]

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

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

Dialectic в сообщении #232722 писал(а):

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

Надеюсь, Вы действительно хотите получить ответы на вопросы, а не разразиться очередной порцией бессмыслицы.

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

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

2) Пример maxal я назвал неверным, потому что не каждое перечислимое подмножество $\mathbb{N}$ перечислимо в порядке возрастания элементов. Более того, возможность алгоритмически перечислить множество в порядке возрастания равносильна вычислимости этого множества.

3) Вычислимое множество = разрешимое множество. Это синонимы.

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