Вот доказательство того, что в бесконечном перечислимом множестве есть бесконечное разрешимое подмножество:

alt text

Вопросы такие:

1) Все элементы х, для которых $%b_0 < x < b_1$% просто игнорируются? То есть отсюда не следует, что любое перечислимое множество можно перечислить в порядке возрастания? И это утверждение верно или нет?

2) В конце написано "нужно запустить перечисление В..." В перечислимо потому что можно модифицировать перечислитель для А, игнорировав все х, для которых $%b_0 < x < b_1$%?

задан 23 Май 3:08

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

Эта задача и на форуме не раз была, но ссылку неохота искать.

Элементы с условием b(0) < x < b(1) не игнорируются -- они просто не входят в B по построению. Совершенно не исключено, что они есть в A. Вообще, может так быть, что A состоит из всех натуральных чисел, но они могут появляться где-то очень далеко, и мы не знаем априори, появятся ли они.

Чтобы было ясно, что такое B, достаточно взять хаотичную последовательность чисел, а потом по определению найти элементы B по порядку.

Например: 3, 14, 15, 92, 65, 35, 8, 9, 7, ... (это A). Тогда

b(0)=3, b(1)=14, b(2)=15, b(3)=92, и дальше долго ждём появления числа, большего 92. Оно точно появится, так как A бесконечно.

Здесь по построению b(0) < b(1) < ... возрастает, и есть алгоритм нахождения b(n) для любого n. Просто ждём достаточно долго.

Когда у нас есть явно заданная возрастающая последовательность, то множество её значений разрешимо, что очевидно. Мы либо дожидаемся появления поданного на вход числа x среди b(i), либо оно не появляется, но появляется b(i) > x, и тогда x нет в B, так как ещё не было, но уже и не будет -- всё остальное возрастает, и маленькие числа не появляются. Есть ли оно при этом в A, мы не знаем, но нс это никак не волнует, так как мы сами выбираем подмножество по заданному нами правилу.

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

ссылка

отвечен 23 Май 3:27

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

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

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

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

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

отмечен:

×42

задан
23 Май 3:08

показан
23 раза

обновлен
23 Май 3:27

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

по почте:

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

по RSS:

Ответы

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

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