Существует ли универсальное разрешимое множество Y ⊆ N^2, т.е. такое что Y разрешимо и для каждого разрешимого множества A ⊆ N найдется число n ∈ N, т.ч. x ∈ A ⇐⇒ (n, x) ∈ Y при всех x ∈ N?

задан 24 Июн '19 21:38

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

Предположим, что такое множество существует. Пусть U(x,y) -- его характеристическая функция. Она вычислима. Рассмотрим функцию f(x)=not(U(x,x)), где not(0)=1, not(1)=0. Она также вычислима. Обозначим через A множество всех x таких, для которых f(x)=1. Понятно, что A разрешимо, и тогда оно должно иметь номер n для которого U(n,y)=1 <=> y in A <=> f(y)=1 при всех y. В частности, для y=n. То есть U(n,n)=1 <=> f(n)=1 <=> U(n,n)=0 -- противоречие.

ссылка

отвечен 25 Июн '19 2:20

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

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

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

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

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

отмечен:

×1,469
×886

задан
24 Июн '19 21:38

показан
125 раз

обновлен
25 Июн '19 2:20

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

по почте:

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

по RSS:

Ответы

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

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