Мощность сем-ва всех РПМ, но не рек. подмножеств нат. ряда.

[Lexivore]

Какова мощность семейства всех рекурсивно перечислимых, но не рекурсивных подмножеств N ?
Существование таких множеств гарантируется множеством A={x из N | U(x,x) определено}, где U(x,x) - универсальная для класса одноместных ЧРФ. Множество А суть РПМ, но не рекурсивно. Так же оно бесконечно, в силу определения. Его дополнение до N\A не РПМ, и оно тоже бесконечно, в силу того что будь оно конечно, оно было бы рекурсивно. Таким образом добавляя или убирая из А конечные подмножества, получаемые множества будут оставаться РПМ, но не рекурсивными, и значит имеется уже счетное семейство множеств удовлетворяющих условиям задачи. Ограничение сверху по мощности : мощностью P(N) - множество всех подмножеств N, суть континуумом. В итоге установлено что мощность данного семейства не менее чем алеф-ноль и не более континуума. Дальнейшее уточнение вызывает затруднения.

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

Lexivore в сообщении #276052 писал(а):

Какова мощность семейства всех рекурсивно перечислимых, но не рекурсивных подмножеств N ?

Счётная.

-- Вт дек 29, 2009 01:05:50 --

Рекурсивно перечислимых подмножеств $\mathbb{N}$ всего счётное число. Для доказательства этого факта достаточно вспомнить определение рекурсивно перечислимого множества.

[Lexivore]

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

Рекурсивно перечислимых подмножеств всего счётное число. Для доказательства этого факта достаточно вспомнить определение рекурсивно перечислимого множества.

А можно поподробнее насчет этого?

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

Напишите определение рекурсивно перечислимого множества.

[Lexivore]

Спасибо, разобрался

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

(Оффтоп)

Вот и поговорили

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