|
Существует ли универсальное разрешимое множество Y ⊆ N^2, т.е. такое что Y разрешимо и для каждого разрешимого множества A ⊆ N найдется число n ∈ N, т.ч. x ∈ A ⇐⇒ (n, x) ∈ Y при всех x ∈ N? задан 24 Июн '19 21:38 
cfrhfkmysqcvsck |
|
Предположим, что такое множество существует. Пусть 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 
falcao |