Пусть рекурсивно перечислимое множество A перечислимо монотонно неубывающей функцией f. Тогда А вычислимо.

Доказательство. Если А конечно, то это верно потому что любое конечное множество вычислимо. Пусть А бесконечно. Тогда $%\lim_{n\to \infty} f(n)=\infty$%.

Чтобы решить $%x\in A$% или нет, делаем следующее:

Смотрим на $%f(0),f(1),\dots$% до тех пор, пока одно из значений $%\ge x$%. Пусть $%f(n)\ge x$% и $%n$% наименьшее число с этим свойством. Тогда если $%f(n)=x$%, то $%x\in A$%. Если нет, то $%x\notin A$%.

Почему $%f(n)=x\iff x\in A$%?

задан 1 Ноя '19 23:07

Тут всё сразу вытекает из определений. Множество значений f равно A. Поэтому f(n) принадлежит A. Обратно, если x принадлежит A, то x имеет вид f(n) для некоторого n. Выберем наименьшее такое n. Для него верно f(n)>=x, а для предыдущих m < n имеет место неравенство f(m)<=f(n) в силу монотонности, и равенство невозможно, так как n выбрано наименьшим. Обосновывать тут если что и нужно, то только то, что в процессе нахождения f(0), f(1), ... , у нас появится значение >=x ввиду бесконечности A. Этого мы дождёмся, а если f(n) > x (раньше был знак "меньше"), то x мы "проскочили", и его нет в f(N).

(2 Ноя '19 6:24) falcao
10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

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

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

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

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

отмечен:

×53

задан
1 Ноя '19 23:07

показан
178 раз

обновлен
2 Ноя '19 6:24

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

по почте:

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

по RSS:

Ответы

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

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