Верны ли эти утверждения?

Для всех $%A\subseteq\mathbb N$%,

$%\emptyset \le_m A$%

$%\mathbb N \le_m A$%

--

Например, первое верно тогда и только тогда когда существует вычислимая $%f:N\to N$% такая что $%x\in \emptyset \iff f(x)\in A$%. Левая часть эквиваленции всегда ложна. Значит, чтобы импликация была верна, правая часть должна быть ложна. То есть для всех $%x$% мы должны иметь $%f(x)\notin A$%. Существует ли такая вычислимая функция?

Второе: надо проверить существует ли $%f:N\to N$% такая что $%x\in N\iff f(x)\in A$%. Тут наоборот правая часть всегда должна быть верна, чтобы эквиваленция была верна. Существует ли такая вычислимая $%f$%?

задан 1 Ноя '19 21:14

@logic: в первом случае A не равно N. Подходит функция-константа f(x)=c, где c из дополнения A. Во втором случае A непусто, но c берём из A.

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

Ваш ответ

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

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

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

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

отмечен:

×245

задан
1 Ноя '19 21:14

показан
146 раз

обновлен
1 Ноя '19 21:33

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

по почте:

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

по RSS:

Ответы

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

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