Докажите, что если А, B ⊂ N — бесконечные разрешимые множества с бесконечными дoполнениями, то существует вычислимая биекция N → N, переводящая А в В.

задан 18 Июн '19 22:00

10|600 символов нужно символов осталось
1

Это утверждение верно даже без дополнительных предположений по поводу дополнения.

Если бесконечное множество A разрешимо, и a(1) < a(2) < ... < a(n) < ... -- упорядоченные по возрастанию его элементы, то функция n -> a(n) вычислима. Действительно, проверяя последовательно числа 1, 2, ... на предмет принадлежности A, мы рано или поздно найдём n-й по порядку элемент из A. Это и есть a(n).

Обратное отображение A -> N, переводящее a(n) в N, также вычислимо, так как по элементу a из A мы всегда можем узнать его номер по счёту, проверяя все меньшие на предмет принадлежности A.

Таким образом, у нас есть две взаимно обратные вычислимые биекции A на N и наоборот. Для бесконечного разрешимого множества B верно то же самое. Получается композиция двух вычислимых биекций a(n) -> n -> b(n), которая является искомой.

ссылка

отвечен 18 Июн '19 23:56

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×501

задан
18 Июн '19 22:00

показан
238 раз

обновлен
18 Июн '19 23:56

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru