Мы уже говорили, что перечислимые множества можно эквивалентно определить как проекции A(x) натуральных чисел перечислимо тогда
и только тогда, когда его можно представить в виде
где B(x,y) некоторое разрешимое свойство.
(В этом разделе мы предполагаем знакомство читателя с простейшими логическими обозначениями: квантор $$\exists x$$ читается как " существует x ", квантор $$\forall x$$ читается как " для всех x ", знак $$\wedge$$ читается как " и" и называется конъюнкцией, знак $$\vee$$ читается как " или" и называется дизъюнкцией, знак $$\neg$$ читается как " неверно, что" и называется отрицанием. Как и раньше, знак $$\Leftrightarrow$$ означает равносильность.)
Возникает естественный вопрос: что можно сказать про другие наборы кванторов? Например, какие свойства представимы в виде
$$A(x) \Leftrightarrow \exists\ y\ \exists\ z\ C(x,y,z),$$где C разрешимое свойство троек натуральных чисел? Легко
сообразить, что это по-прежнему перечислимые множества. В самом деле,
два подряд идущих квантора одного вида можно заменить одним,
использовав вычислимую нумерацию пар (которую мы обозначаем
квадратными скобками): свойство C', для которого $$C'(x,[y,z]) \Leftrightarrow C(x,y,z)$$, также разрешимо, и $$A(x) \Leftrightarrow \exists\ w\ C'(x,w)$$.
Другой вопрос: какие свойства представимы в виде
$$A(x) \Leftrightarrow \forall\ y\ B(x,y),$$где B(x,y) некоторое разрешимое свойство? Ответ: те,
отрицания которых перечислимы (как иногда говорят, коперечислимые ). В самом деле, переходя к отрицаниям, имеем
а разрешимые свойства остаются разрешимыми при переходе к отрицаниям.
Дадим общее определение. Свойство A принадлежит классу $$\Sigma _{n}$$, если его можно представить в виде
(в правой части стоит n чередующихся кванторов) для некоторого разрешимого свойства B. Если в правой части поставить n чередующихся кванторов, начиная с
Отметим два свойства, которые мы по существу уже доказали:
Теорема 51. (а) Определение класса $$\Sigma _{n}$$ [ $$\Pi _{n}$$ ] не
изменится, если в
правой части разрешить большее число кванторов и требовать,
чтобы первый квантор был квантором существования [всеобщности] и
число групп одинаковых стоящих рядом
кванторов равнялось n. (б) Отрицания свойств из класса $$\Sigma _{n}$$ принадлежат
классу $$\Pi _{n}$$ и наоборот.
Для доказательства первого утверждения достаточно соединять рядом стоящие одинаковые кванторы с помощью нумерации пар. Для доказательства второго надо проносить отрицание внутрь (меняя тип квантора), пока оно не окажется у разрешимого свойства (где оно роли не играет).
Мы говорили о свойствах; на языке множеств можно сказать так:
множества класса $$\Sigma _{n}$$ получаются из разрешимых с помощью
последовательности операций " проекция-дополнение-проекция-дополнение-...-проекция", в которой всего n операций
проекции. Каждая Nn+1.
Теорема 52. Пересечение и объединение двух множеств из класса $$\Sigma _{n}$$ принадлежит $$\Sigma _{n}$$. Пересечение и объединение двух множеств из класса $$\Pi _{n}$$ принадлежит $$\Pi _{n}$$.
Удобно выразить это утверждение на логическом языке, сказав, что конъюнкция и дизъюнкция любых двух свойств из класса $$\Sigma _{n}$$ лежат в том же классе (аналогично для $$\Pi _{n}$$ ). На этом же языке удобно провести и доказательство: если, скажем,
$$A(x) \Leftrightarrow \exists\ y\ \forall\ z\ B(x,y,z), \\ C(x) \Leftrightarrow \exists\ u \forall\ v\ D(x,u,v), \\ то \\ A(x) \wedge C(x) \Leftrightarrow \exists\ y \exists\ u \forall\ z \forall\ v\ [B(x,y,z) \wedge D(x,u,v)],$$записанное в квадратных скобках свойство разрешимо и остается
только соединить пары кванторов в один, как объяснялось выше.
Аналогично можно действовать для классов $$\Sigma _{n}$$
и $$\Pi _{n}$$
при произвольном n.
Мы определяли классы $$\Sigma _{n}$$ и $$\Pi _{n}$$ для множеств натуральных чисел; аналогичным образом это можно сделать и для множеств пар натуральных чисел, троек и вообще любых " конструктивных объектов". Заметим, что проекция множества пар, принадлежащего классу $$\Sigma _{n}$$, также принадлежит $$\Sigma _{n}$$ (поскольку два квантора существования в начале можно объединить в один).
Добавляя фиктивные кванторы, легко убедиться, что каждый из двух классов $$\Sigma _{n}$$ и $$\Pi _{n}$$ содержится в каждом из классов $$\Sigma _{n+1}$$ и $$\Pi _{n+1}$$. Можно написать еще так:
$$\Sigma _{n} \cup \Pi _{n} \subset \Sigma _{n+1} \cap \Pi _{n+1}.$$Теорема 53. Классы $$\Sigma _{n}$$ и $$\Pi _{n}$$ " наследственны вниз" относительно m -сводимости:
если A <=m B и $$B \in \Sigma _{n}$$ [ $$B \in \Pi _{n}$$ ],
то и $$A \in \Sigma _{n}$$ [ $$A \in \Pi _{n}$$ ].
В самом деле, пусть A сводится к B с помощью всюду
определенной вычислимой функции f, то есть $$x \in A \Leftrightarrow f(x) \in B$$. Пусть B принадлежит,
например,
классу $$\Sigma _{3}$$, то есть
где R некоторое разрешимое свойство. Тогда
и осталось заметить, что R(f(x),y,z,u) (как свойство
четверки $$\langle x,y,z,u\rangle$$ ) разрешимо.
63. Докажите, что если множество A принадлежит классу $$\Sigma _{n}$$, то множество A x A также принадлежит этому классу.
64. Докажите, что если множества A и B принадлежат классу $$\Sigma _{n}$$, то их разность A \ B принадлежит
классу $$\Sigma _{n+1} \cap \Pi _{n+1}$$.
До сих пор мы не показали, что классы $$\Sigma _{n}$$
и $$\Pi _{n}$$
действительно различаются при разных n. Чтобы показать это,
убедимся, что в каждом из этих классов имеется универсальное
множество (для соответствующего класса) и что оно не принадлежит
меньшим классам.
Теорема 54. Для любого n в классе $$\Sigma _{n}$$ существует множество,
универсальное для всех множеств класса $$\Sigma _{n}$$. (Его
дополнение будет универсальным в классе $$\Pi _{n}$$.)
Говоря об универсальном множестве из класса $$\Sigma _{n}$$, мы имеем в виду множество пар натуральных чисел, которое принадлежит классу $$\Sigma _{n}$$ и среди сечений которого встречаются все множества натуральных чисел, принадлежащие классу $$\Sigma _{n}$$.
Для класса $$\Sigma _{1}$$ (перечислимых множеств) существование универсального множества мы уже обсуждали. С его помощью можно построить универсальные множества и для более высоких классов иерархии. (Начинать надо с первого уровня, так как на " нулевом" уровне не существует универсального разрешимого множества.)
По определению свойства класса $$\Pi _{2}$$ имеют вид $$S(x) \Leftrightarrow \forall\ y\ \exists\ z R(x,y,z)$$,
где R некоторое разрешимое свойство. Но их
можно эквивалентно определить и как свойства вида $$S(x) \Leftrightarrow \forall\ y\ P(x,y)$$,
где P некоторое перечислимое свойство. Теперь уже видно,
как построить универсальное множество класса $$\Pi _{2}$$. Возьмем
универсальное перечислимое свойство U(n,x,y), из которого
фиксацией различных n получаются все перечислимые свойства пар
натуральных чисел. Тогда из свойства $$T(n,x)= \forall \ y\ U(n,x,y)$$ при различных натуральных n получаются все $$\Pi _{2}$$ -свойства натуральных чисел. С другой стороны, само
свойство T по построению принадлежит
классу $$\Pi _{2}$$.
Дополнение к универсальному $$\Pi _{2}$$ -множеству будет, очевидно, универсальным $$\Sigma _{2}$$ -множеством.
Аналогично можно действовать и для $$\Sigma _{3}$$ - и $$\Pi _{3}$$ -множеств (удобнее сначала рассуждать о $$\Sigma _{3}$$ -множествах, так как в них внутренний квантор является квантором существования и задает перечислимое множество), и вообще для $$\Sigma _{n}$$ - и $$\Pi _{n}$$ -множеств.
Теорема 55. Универсальное $$\Sigma _{n}$$ -множество не принадлежит классу $$\Pi _{n}$$. Аналогичным образом, универсальное $$\Pi _{n}$$ -множество не принадлежит классу $$\Sigma _{n}$$.
Рассмотрим универсальное $$\Sigma _{n}$$ -свойство T(m,x). По определению это означает, что среди его сечений (получающихся, если зафиксировать m ) есть все $$\Sigma _{n}$$ -свойства. Пусть T принадлежит классу $$\Pi _{n}$$. Тогда его диагональ, свойство D(x)=T(x,x), также лежит в $$\Pi _{n}$$ (например, потому, что D <=m T ), а ее отрицание, свойство $$\neg D(x)$$, принадлежит классу $$\Sigma _{n}$$. Но этого не может быть, так как $$\neg D$$ отлично от всех сечений свойства T (оно отличается от m -го сечения в точке m ), а T универсально.
Из этой теоремы следует, в частности, что любой из классов $$\Sigma _{n}$$ и $$\Pi _{n}$$ является собственным подмножеством любого из классов $$\Sigma _{n+1}$$ и $$\Pi _{n+1}$$. (Мы увидим вскоре, что даже объединение $$\Sigma _{n} \cup \Pi _{n}$$ является собственным подмножеством пересечения $$\Sigma _{n+1} \cap \Pi _{n+1}$$.)
Мы хотим показать, что класс $$\Sigma _{n}$$ совпадает с классом всех A -перечислимых
множеств для некоторого множества A (зависящего от n,
естественно). Чтобы объяснить, что это за множество, нам
понадобится так называемая операция скачка.
Пусть X произвольное множество. Среди X -перечислимых множеств есть универсальное. Это множество будет m -полным в классе X -перечислимых множеств в том смысле, что все другие X -перечислимые множества к нему m -сводятся.
Сводящая
функция, как мы видели, имеет вид x $$\mapsto$$ [n,x] (и вычислима
безо всякого оракула, как того и требует определение m -сводимости). Будем обозначать через X' любое m -полное
множество в классе X -перечислимых множеств. Можно сказать,
что X' определено с точностью до m -эквивалентности.
Более формально, будем говорить, что множества P
и Q являются m - эквивалентными, если P <=m Q
и Q <=m P.
(Легко видеть, что это действительно отношение
эквивалентности.) Класс эквивалентных множеств называют m - степенью. Таким образом, можно сказать, что мы
для каждого множества X определили некоторую m -степень X'.
Аналогичным образом определяют T - степени (которые
называют также тьюринговыми степенями или степенями неразрешимости )
как классы T -эквивалентных
множеств; множества P и Q называют T - эквивалентными, или эквивалентными по Тьюрингу, если P <=T Q и Q<=T P, то есть
если каждое из множеств разрешимо относительно другого. Если множества P
и Q
эквивалентны по Тьюрингу, то класс P -вычислимых функций
совпадает с классом Q -вычислимых функций (а класс P -перечислимых множеств совпадает с классом Q -перечислимых множеств). Введя понятие T -степени, можно сказать, что m -степень X' определяется T -степенью множества X и тем
самым определено
T -степеней в множество
всех m -степеней. Это отображение называют операцией скачка ; множество (точнее, m -степень) X' называют скачком множества (точнее, T -степени) X.
65. Могут ли при этом отображении разные T -степени переходить в
одну и ту же m -степень? нет, так как перечислимые одни и те же и разрешимые тоже
66. Докажите, что любые два m -полных
в классе $$\Sigma _{n}$$ множества вычислимо
изоморфны (отличаются вычислимой перестановкой).
67. Покажите, что для любого перечислимого множества A можно
указать такое действительное число $$\alpha,$$ что множество всех
рациональных чисел, меньших $$\alpha,$$ будет перечислимо и
эквивалентно по Тьюрингу множеству A.
Обычно, впрочем, операцию скачка рассматривают на T -степенях,
считая ее результатом T -степень, содержащую X'
(это законно,
так как T -классификация более грубая).
Нам понадобятся следующие T -степени: 0 (степень, содержащая
все 0' (ее скачок, степень m -полного перечислимого неразрешимого множества; мы ее уже
рассматривали), затем 0'' (скачок степени 0' ), 0''' и так далее;
вообще 0(n+1)= (0(n))'.
Теорема 56. При любом n >= 1 класс $$\Sigma _{n}$$ совпадает с
классом всех 0(n-1) -перечислимых множеств.
(Пока что мы знаем это при n=1.)
Докажем сначала, что все $$\Sigma _{n}$$ -множества перечислимы
относительно 0(n-1). Это делается индукцией
по n.
При n=1 это известно. Рассмотрим теперь произвольное
множество X из $$\Sigma _{2}$$. По определению,
где R разрешимое свойство. Свойство $$\forall\ z\ R(x,y,z)$$
имеет перечислимое отрицание. Это отрицание разрешимо
относительно 0', так как m -сводится к m -полному
перечислимому множеству. Значит, и само свойство $$\forall \ z\ R(x,y,z)$$ разрешимо относительно 0'. Поэтому его
проекция, множество X, перечислимо
относительно 0'.
Аналогично можно рассуждать и для больших n. Если X принадлежит $$\Sigma _{3}$$, то
где R принадлежит $$\Pi _{2}$$. Отрицание R
принадлежит $$\Sigma _{2}$$
(по доказанному), поэтому 0' -перечислимо,
поэтому 0'' -разрешимо, поэтому само R тоже 0'' -разрешимо, а его проекция 0'' -перечислима.
Первая половина теоремы доказана.
Для доказательства второй половины нам потребуется некоторое
свойство классов $$\Sigma _{n}$$ и $$\Pi _{n}$$. Рассмотрим
какую-нибудь
вычислимую нумерацию всех конечных множеств натуральных чисел. Обозначим через Dx конечное множество номер x. Для
произвольного множества A рассмотрим
множество Subset(A) всех конечных подмножеств A,
точнее, множество всех их номеров:
Лемма 1. Если множество A принадлежит
классу $$\Sigma _{n}$$ [или $$\Pi _{n}$$ ], то
множество Subset(A) также
принадлежит
классу $$\Sigma _{n}$$ [соответственно $$\Pi _{n}$$ ].
(Утверждение этой леммы обобщает сформулированное в
задаче 63 утверждение о множестве Ax A: теперь мы
рассматриваем не пары, а произвольные кортежи.)
Доказательство леммы. Пусть множество A принадлежит,
например, классу $$\Sigma _{3}$$:
где R разрешимое свойство. Тогда можно записать
свойство $$\{ x_{1}, \dots ,x_{n}\} \subset A$$
следующим образом:
Эта формула использует кванторы по кортежам натуральных чисел (переменной длины), но их можно заменить на номера этих кортежей в какой-нибудь вычислимой нумерации. При этом стоящая под кванторами формула (она записана несколько условно: символическая конъюнкция на самом деле имеет переменную длину) является разрешимым свойством номеров кортежей, поэтому вся правая часть является $$\Sigma _{3}$$ -свойством.
(На самом деле мы допустили еще одну вольность речи: правая
часть является не свойством конечного
множества {x1,...,xn}, а
свойством
кортежа (упорядоченной последовательности) $$\langle
x_1,\dots,x_n\rangle$$. Но переход от номера множества к номеру
какого-то кортежа, содержащего все его элементы, вычислим,
так что проблемы тут нет.)
Лемма доказана.
68. Докажите, что
если A принадлежит
классу $$\Sigma _{n}$$ [ $$\Pi _{n}$$ ], то и
множество $$\in tersect(A)$$ номеров конечных множеств,
пересекающихся с A, принадлежит классу $$\Sigma _{n}$$
[ $$\Pi _{n}$$ ].
69. Пусть свойство R(x,y) пар натуральных чисел принадлежит классу $$\Sigma _{n}$$. Покажите, что свойство
принадлежит $$\Sigma _{n}$$. (Ограниченный квантор $$(\forall y \le x)$$ читается как " для всех y, не превосходящих x ".)
Переходя к дополнениям, мы немедленно получаем такое утверждение:
Лемма 2. Если A принадлежит
классу $$\Sigma _{n}$$ [ $$\Pi _{n}$$ ],
то множество Disjoint(A), состоящее из номеров конечных
множеств, не пересекающихся с A,
принадлежит $$\Pi _{n}$$ [ $$\Sigma _{n}$$ ].
Доказательство леммы. Не пересекаться с A означает быть
подмножеством дополнения к A, и остается воспользоваться
предыдущей леммой и тем, что дополнение к множеству из
класса $$\Sigma _{n}$$ [ $$\Pi _{n}$$ ] лежит в
классе $$\Pi _{n}$$ [ $$\Sigma _{n}$$ ].
Лемма доказана.
Теперь мы можем перейти к доказательству того факта, что все
множества, перечислимые относительно 0(n-1),
принадлежат классу $$\Sigma _{n}$$. Это также доказывается индукцией
по n.
Начнем с первого нетривиального случая: почему множество,
перечислимое относительно 0', лежит в $$\Sigma _{2}$$?
(Здесь можно было бы применить критерий 0' -вычислимости, приведенный выше, но мы предпочитаем
действовать по общей схеме, которая годится и для
больших n.)
Итак, пусть некоторое множество A перечислимо относительно 0'. Тогда оно перечислимо относительно некоторого перечислимого множества B, то есть перечислимо относительно характеристической функции b множества B. Согласно доказанному нами выше критерию (теорема 45), это означает, что существует перечислимое множество Q пар вида $$\langle x,t\rangle$$, где x число, а t образец, для которого
Без ограничения общности можно считать, что образец t представляет собой функцию, определенную на конечном множестве и принимающую значения 0 и 1. (Если у t есть какие-то другие значения, то он не может быть частью характеристической функции множества B и роли не играет.) Условие " b продолжает t " в терминах множества B звучит так: B содержит множество тех аргументов, на которых t принимает значение 1, и не пересекается с множеством тех аргументов, на которых t принимает значение 0. Поэтому вместо образцов можно говорить о парах конечных множеств; тогда вместо Q надо рассмотреть перечислимое множество P троек вида $$\langle x,u,v \rangle$$ и написать так:
Теперь вместо " Du содержится в B " напишем " $$u \in opSubset(B)$$ ", а вместо " Dv не пересекается с B " напишем " $$v \in Disjoint(B)$$ ". Остается заметить, что все три свойства, соединенные союзом " и" в правой части, принадлежат классу $$\Sigma _{2}$$ и даже меньшим классам. Именно, первые два принадлежат классу $$\Sigma _{1}$$, так как P и B перечислимы (для второго свойства применяем лемму 1). Третье же принадлежит классу $$\Pi _{1}$$ по лемме 2. Поэтому их конъюнкция принадлежит классу $$\Sigma _{2}$$, и n=2 разобран.
Далее, если какое-то множество A перечислимо относительно 0'', то по определению это означает, что оно перечислимо относительно некоторого B, которое перечислимо относительно 0' и потому лежит в $$\Sigma _{2}$$. После этого все рассуждения проходят точно так же со сдвигом на 1. Аналогично разбираются и все следующие значения n.
Из доказанной теоремы немедленно вытекает такое следствие:
Теорема 57. Пересечение классов $$\Sigma _{n} \cap \Pi _{n}$$ совпадает с классом разрешимых относительно 0(n-1) множеств.
В самом деле, релятивизованная теорема Поста (теорема 2) утверждает, что некоторое множество является X -разрешимым тогда и только тогда, когда оно и его дополнение X -перечислимы (здесь X произвольный оракул).
Теорема 58. Класс $$\Sigma _{n} \cup \Pi _{n}$$ является собственным подмножеством класса $$\Sigma _{n+1} \cap \Pi _{n+1}$$.
Вспомним, что такое 0(n). Это степень множества X, являющегося m -полным в классе 0(n-1) -перечислимых множеств. Поскольку X является m -полным в указанном классе, оно не 0(n-1) -разрешимо, то есть его дополнение не является 0(n-1) -перечислимым.
Значит, по доказанной только что теореме X принадлежит классу $$\Sigma _{n}$$, а его дополнение нет. Напротив, дополнение к X принадлежит $$\Pi _{n}$$, но не $$\Sigma _{n}$$. Рассмотрим теперь " соединение" множества X с его дополнением, е множество
К этому множеству m -сводятся как X, так и его дополнение, поэтому оно не может принадлежать ни $$\Sigma _{n}$$, ни $$\Pi _{n}$$. С другой стороны, оно, очевидно, разрешимо относительно X, поэтому по доказанной теореме принадлежит и $$\Sigma _{n+1}$$, и $$\Pi _{n+1}$$.
Интересно посмотреть, какое место разные конкретные множества занимают в описанной нами иерархии. Например, что можно сказать о множестве номеров какой-то фиксированной вычислимой функции в главной нумерации?
Мы уже говорили, что множество всех номеров всех функций с непустой областью определения перечислимо, то есть принадлежит классу $$\Sigma _{1}$$. Следовательно, его дополнение, множество всех номеров нигде не определенной функции, принадлежит классу $$\Pi _{1}$$. (Классу $$\Sigma _{1}$$ оно принадлежать не может, так как неразрешимо, см. теорему 21)
70.Докажите, что множество номеров нигде не определенной функции в любой главной нумерации является m -полным в классе $$\Pi _{1}$$ множеством.
А что можно сказать о номерах других функций? Например, что можно сказать о множестве номеров тождественно нулевой функции? Оказывается, можно получить в некотором смысле полный ответ на этот вопрос.
Теорема 59. (а) Пусть U вычислимая универсальная функция для класса вычислимых функций. Тогда множество тех n, при которых Un всюду определено и тождественно равно 0, принадлежит классу $$\Pi _{2}$$. (б) Пусть U главная универсальная функция. Тогда указанное множество является m -полным в классе $$\Pi _{2}$$.
Заметим, что требование главности в пункте (б) существенно: в однозначной нумерации это множество состоит из единственного номера.
Интересующее нас свойство числа n можно записать так: для любого k найдется такое t, что за t шагов вычисление значения U(n,k) закончится и даст результат 0. Выделенная часть является разрешимым свойством, а перед ней стоят два квантора как раз нужного вида. Итак, пункт (а) доказан.
Докажем утверждение (б). Пусть имеется произвольное множество P из класса $$\Pi _{2}$$. При этом
где R некоторое разрешимое свойство. Рассмотрим теперь функцию S(x,y), вычисляемую таким алгоритмом: перебирая все числа, ищем число z, для которого R(x,y,z) ; как только (и если) такое число найдено, выдаем на выход 0. Ясно, что x -ое сечение Sx функции S будет тождественно нулевой функцией в том и только том случае, когда $$x\in P$$. Применим свойство главности и получим функцию s, для которой Us(x)=Sx. Она и будет сводить P к множеству всех номеров тождественно нулевой функции.
Что можно сказать про другие функции? Для любой вычислимой универсальной функции U и любой вычислимой функции f множество всех U -номеров функции f является $$\Pi _{2}$$ -множеством. Верен даже более сильный факт: свойство Um=Un (числа m и n являются номерами одной и той же функции) является $$\Pi _{2}$$ -свойством пары $$\langle m,n\rangle$$, поэтому тем более любое его сечение (е множество всех номеров любой конкретной функции) является $$\Pi _{2}$$ -множеством.В самом деле, свойство Um=Un можно сформулировать так: " для всяких x и t1 найдется такое t2, что если вычисление U(m,x) завершается за t1 шагов, то вычисление U(n,x) завершается за t2 шагов с тем же результатом, и наоборот ". Выделенная часть разрешима, а до нее стоит $$\Pi _{2}$$ -префикс.
Можно даже понять, для каких функций множество номеров является $$\Pi _{2}$$ -полным: для функций с бесконечной областью определения. Если область определения функции конечна, то множество всех ее номеров является 0' -разрешимым (и потому не $$\Pi _{2}$$ -полным): имея оракул для проблемы остановки, можно убедиться, что функция определена всюду, где она должна быть определена (после чего проверить, что значения правильны), а затем проверить, что ни в одной из оставшихся точек она не определена (процесс поиска точки вне данного конечного множества, в которой функция определена, является перечислимым процессом и потому его успешность может быть проверена с помощью 0' -оракула).
Если же функция имеет бесконечную область определения, то существует бесконечное
71.Проведите это рассуждение подробно.
72.Покажите, что множество всех номеров всех всюду определенных функций (в главной нумерации) является $$\Pi _{2}$$ -полным.
73.В каком наименьшем классе арифметической иерархии лежит множество номеров всех функций с бесконечной областью определения? Будет ли оно m -полным в этом классе?
74.Покажите, что для любой (не обязательно главной!) нумерации множество всех номеров всюду определенных функций неперечислимо. Более того, оно не имеет перечислимого подмножества, включающего в себя хотя бы по одному номеру каждой вычислимой всюду определенной функции. (Указание: используйте диагональную конструкцию.)
В книге Х.Роджерса ([8], параграф 14.8) приведено много результатов подобного рода для многих других свойств вычислимых функций и перечислимых множеств. Например, для любого m -полного множества K множество всех его номеров является $$\Pi _{2}$$ -полным. (Здесь и далее, говоря о номерах, мы имеем в виду главную нумерацию перечислимых множеств.) Множество номеров всех конечных множеств является $$\Sigma _{2}$$ -полным. Множество номеров множеств, содержащих хотя бы один номер бесконечного множества, является $$\Sigma _{3}$$ -полным. Множество номеров всех
75. Докажите перечисленные утверждения (или прочтите их доказательства в книге Роджерса [8]).
76. Рассмотрим квантор $$\exists ^\infty x$$, который читается как "существует бесконечно много x, для которых". Покажите, что все свойства из класса $$\Pi _{2}$$ (и только они) представимы в виде
$$\exists ^\infty$$ x,(разрешимое свойство)
и что все свойства из класса $$\Sigma _{3}$$ (и только они) представимы в виде
$$\exists ^\infty x$$ $$\forall y$$ (разрешимое свойство).
(Аналогичное утверждение верно и для старших классов, см. теорему XVIII в разделе 14.8 книги [8].)
Мы уже говорили, что перечислимые множества можно эквивалентно определить как проекции A(x) натуральных чисел перечислимо тогда
и только тогда, когда его можно представить в виде
где B(x,y) некоторое разрешимое свойство.
(В этом разделе мы предполагаем знакомство читателя с простейшими логическими обозначениями: квантор $$\exists x$$ читается как " существует x ", квантор $$\forall x$$ читается как " для всех x ", знак $$\wedge$$ читается как " и" и называется конъюнкцией, знак $$\vee$$ читается как " или" и называется дизъюнкцией, знак $$\neg$$ читается как " неверно, что" и называется отрицанием. Как и раньше, знак $$\Leftrightarrow$$ означает равносильность.)
Возникает естественный вопрос: что можно сказать про другие наборы кванторов? Например, какие свойства представимы в виде
$$A(x) \Leftrightarrow \exists\ y\ \exists\ z\ C(x,y,z),$$где C разрешимое свойство троек натуральных чисел? Легко
сообразить, что это по-прежнему перечислимые множества. В самом деле,
два подряд идущих квантора одного вида можно заменить одним,
использовав вычислимую нумерацию пар (которую мы обозначаем
квадратными скобками): свойство C', для которого $$C'(x,[y,z]) \Leftrightarrow C(x,y,z)$$, также разрешимо, и $$A(x) \Leftrightarrow \exists\ w\ C'(x,w)$$.
Другой вопрос: какие свойства представимы в виде
$$A(x) \Leftrightarrow \forall\ y\ B(x,y),$$где B(x,y) некоторое разрешимое свойство? Ответ: те,
отрицания которых перечислимы (как иногда говорят, коперечислимые ). В самом деле, переходя к отрицаниям, имеем
а разрешимые свойства остаются разрешимыми при переходе к отрицаниям.
Дадим общее определение. Свойство A принадлежит классу $$\Sigma _{n}$$, если его можно представить в виде
(в правой части стоит n чередующихся кванторов) для некоторого разрешимого свойства B. Если в правой части поставить n чередующихся кванторов, начиная с
Отметим два свойства, которые мы по существу уже доказали:
Теорема 51. (а) Определение класса $$\Sigma _{n}$$ [ $$\Pi _{n}$$ ] не
изменится, если в
правой части разрешить большее число кванторов и требовать,
чтобы первый квантор был квантором существования [всеобщности] и
число групп одинаковых стоящих рядом
кванторов равнялось n. (б) Отрицания свойств из класса $$\Sigma _{n}$$ принадлежат
классу $$\Pi _{n}$$ и наоборот.
Для доказательства первого утверждения достаточно соединять рядом стоящие одинаковые кванторы с помощью нумерации пар. Для доказательства второго надо проносить отрицание внутрь (меняя тип квантора), пока оно не окажется у разрешимого свойства (где оно роли не играет).
Мы говорили о свойствах; на языке множеств можно сказать так:
множества класса $$\Sigma _{n}$$ получаются из разрешимых с помощью
последовательности операций " проекция-дополнение-проекция-дополнение-...-проекция", в которой всего n операций
проекции. Каждая Nn+1.
Теорема 52. Пересечение и объединение двух множеств из класса $$\Sigma _{n}$$ принадлежит $$\Sigma _{n}$$. Пересечение и объединение двух множеств из класса $$\Pi _{n}$$ принадлежит $$\Pi _{n}$$.
Удобно выразить это утверждение на логическом языке, сказав, что конъюнкция и дизъюнкция любых двух свойств из класса $$\Sigma _{n}$$ лежат в том же классе (аналогично для $$\Pi _{n}$$ ). На этом же языке удобно провести и доказательство: если, скажем,
$$A(x) \Leftrightarrow \exists\ y\ \forall\ z\ B(x,y,z), \\ C(x) \Leftrightarrow \exists\ u \forall\ v\ D(x,u,v), \\ то \\ A(x) \wedge C(x) \Leftrightarrow \exists\ y \exists\ u \forall\ z \forall\ v\ [B(x,y,z) \wedge D(x,u,v)],$$записанное в квадратных скобках свойство разрешимо и остается
только соединить пары кванторов в один, как объяснялось выше.
Аналогично можно действовать для классов $$\Sigma _{n}$$
и $$\Pi _{n}$$
при произвольном n.
Мы определяли классы $$\Sigma _{n}$$ и $$\Pi _{n}$$ для множеств натуральных чисел; аналогичным образом это можно сделать и для множеств пар натуральных чисел, троек и вообще любых " конструктивных объектов". Заметим, что проекция множества пар, принадлежащего классу $$\Sigma _{n}$$, также принадлежит $$\Sigma _{n}$$ (поскольку два квантора существования в начале можно объединить в один).
Добавляя фиктивные кванторы, легко убедиться, что каждый из двух классов $$\Sigma _{n}$$ и $$\Pi _{n}$$ содержится в каждом из классов $$\Sigma _{n+1}$$ и $$\Pi _{n+1}$$. Можно написать еще так:
$$\Sigma _{n} \cup \Pi _{n} \subset \Sigma _{n+1} \cap \Pi _{n+1}.$$Теорема 53. Классы $$\Sigma _{n}$$ и $$\Pi _{n}$$ " наследственны вниз" относительно m -сводимости:
если A <=m B и $$B \in \Sigma _{n}$$ [ $$B \in \Pi _{n}$$ ],
то и $$A \in \Sigma _{n}$$ [ $$A \in \Pi _{n}$$ ].
В самом деле, пусть A сводится к B с помощью всюду
определенной вычислимой функции f, то есть $$x \in A \Leftrightarrow f(x) \in B$$. Пусть B принадлежит,
например,
классу $$\Sigma _{3}$$, то есть
где R некоторое разрешимое свойство. Тогда
и осталось заметить, что R(f(x),y,z,u) (как свойство
четверки $$\langle x,y,z,u\rangle$$ ) разрешимо.
63. Докажите, что если множество A принадлежит классу $$\Sigma _{n}$$, то множество A x A также принадлежит этому классу.
64. Докажите, что если множества A и B принадлежат классу $$\Sigma _{n}$$, то их разность A \ B принадлежит
классу $$\Sigma _{n+1} \cap \Pi _{n+1}$$.
До сих пор мы не показали, что классы $$\Sigma _{n}$$
и $$\Pi _{n}$$
действительно различаются при разных n. Чтобы показать это,
убедимся, что в каждом из этих классов имеется универсальное
множество (для соответствующего класса) и что оно не принадлежит
меньшим классам.
Теорема 54. Для любого n в классе $$\Sigma _{n}$$ существует множество,
универсальное для всех множеств класса $$\Sigma _{n}$$. (Его
дополнение будет универсальным в классе $$\Pi _{n}$$.)
Говоря об универсальном множестве из класса $$\Sigma _{n}$$, мы имеем в виду множество пар натуральных чисел, которое принадлежит классу $$\Sigma _{n}$$ и среди сечений которого встречаются все множества натуральных чисел, принадлежащие классу $$\Sigma _{n}$$.
Для класса $$\Sigma _{1}$$ (перечислимых множеств) существование универсального множества мы уже обсуждали. С его помощью можно построить универсальные множества и для более высоких классов иерархии. (Начинать надо с первого уровня, так как на " нулевом" уровне не существует универсального разрешимого множества.)
По определению свойства класса $$\Pi _{2}$$ имеют вид $$S(x) \Leftrightarrow \forall\ y\ \exists\ z R(x,y,z)$$,
где R некоторое разрешимое свойство. Но их
можно эквивалентно определить и как свойства вида $$S(x) \Leftrightarrow \forall\ y\ P(x,y)$$,
где P некоторое перечислимое свойство. Теперь уже видно,
как построить универсальное множество класса $$\Pi _{2}$$. Возьмем
универсальное перечислимое свойство U(n,x,y), из которого
фиксацией различных n получаются все перечислимые свойства пар
натуральных чисел. Тогда из свойства $$T(n,x)= \forall \ y\ U(n,x,y)$$ при различных натуральных n получаются все $$\Pi _{2}$$ -свойства натуральных чисел. С другой стороны, само
свойство T по построению принадлежит
классу $$\Pi _{2}$$.
Дополнение к универсальному $$\Pi _{2}$$ -множеству будет, очевидно, универсальным $$\Sigma _{2}$$ -множеством.
Аналогично можно действовать и для $$\Sigma _{3}$$ - и $$\Pi _{3}$$ -множеств (удобнее сначала рассуждать о $$\Sigma _{3}$$ -множествах, так как в них внутренний квантор является квантором существования и задает перечислимое множество), и вообще для $$\Sigma _{n}$$ - и $$\Pi _{n}$$ -множеств.
Теорема 55. Универсальное $$\Sigma _{n}$$ -множество не принадлежит классу $$\Pi _{n}$$. Аналогичным образом, универсальное $$\Pi _{n}$$ -множество не принадлежит классу $$\Sigma _{n}$$.
Рассмотрим универсальное $$\Sigma _{n}$$ -свойство T(m,x). По определению это означает, что среди его сечений (получающихся, если зафиксировать m ) есть все $$\Sigma _{n}$$ -свойства. Пусть T принадлежит классу $$\Pi _{n}$$. Тогда его диагональ, свойство D(x)=T(x,x), также лежит в $$\Pi _{n}$$ (например, потому, что D <=m T ), а ее отрицание, свойство $$\neg D(x)$$, принадлежит классу $$\Sigma _{n}$$. Но этого не может быть, так как $$\neg D$$ отлично от всех сечений свойства T (оно отличается от m -го сечения в точке m ), а T универсально.
Из этой теоремы следует, в частности, что любой из классов $$\Sigma _{n}$$ и $$\Pi _{n}$$ является собственным подмножеством любого из классов $$\Sigma _{n+1}$$ и $$\Pi _{n+1}$$. (Мы увидим вскоре, что даже объединение $$\Sigma _{n} \cup \Pi _{n}$$ является собственным подмножеством пересечения $$\Sigma _{n+1} \cap \Pi _{n+1}$$.)
Мы хотим показать, что класс $$\Sigma _{n}$$ совпадает с классом всех A -перечислимых
множеств для некоторого множества A (зависящего от n,
естественно). Чтобы объяснить, что это за множество, нам
понадобится так называемая операция скачка.
Пусть X произвольное множество. Среди X -перечислимых множеств есть универсальное. Это множество будет m -полным в классе X -перечислимых множеств в том смысле, что все другие X -перечислимые множества к нему m -сводятся.
Сводящая
функция, как мы видели, имеет вид x $$\mapsto$$ [n,x] (и вычислима
безо всякого оракула, как того и требует определение m -сводимости). Будем обозначать через X' любое m -полное
множество в классе X -перечислимых множеств. Можно сказать,
что X' определено с точностью до m -эквивалентности.
Более формально, будем говорить, что множества P
и Q являются m - эквивалентными, если P <=m Q
и Q <=m P.
(Легко видеть, что это действительно отношение
эквивалентности.) Класс эквивалентных множеств называют m - степенью. Таким образом, можно сказать, что мы
для каждого множества X определили некоторую m -степень X'.
Аналогичным образом определяют T - степени (которые
называют также тьюринговыми степенями или степенями неразрешимости )
как классы T -эквивалентных
множеств; множества P и Q называют T - эквивалентными, или эквивалентными по Тьюрингу, если P <=T Q и Q<=T P, то есть
если каждое из множеств разрешимо относительно другого. Если множества P
и Q
эквивалентны по Тьюрингу, то класс P -вычислимых функций
совпадает с классом Q -вычислимых функций (а класс P -перечислимых множеств совпадает с классом Q -перечислимых множеств). Введя понятие T -степени, можно сказать, что m -степень X' определяется T -степенью множества X и тем
самым определено
T -степеней в множество
всех m -степеней. Это отображение называют операцией скачка ; множество (точнее, m -степень) X' называют скачком множества (точнее, T -степени) X.
65. Могут ли при этом отображении разные T -степени переходить в
одну и ту же m -степень? нет, так как перечислимые одни и те же и разрешимые тоже
66. Докажите, что любые два m -полных
в классе $$\Sigma _{n}$$ множества вычислимо
изоморфны (отличаются вычислимой перестановкой).
67. Покажите, что для любого перечислимого множества A можно
указать такое действительное число $$\alpha,$$ что множество всех
рациональных чисел, меньших $$\alpha,$$ будет перечислимо и
эквивалентно по Тьюрингу множеству A.
Обычно, впрочем, операцию скачка рассматривают на T -степенях,
считая ее результатом T -степень, содержащую X'
(это законно,
так как T -классификация более грубая).
Нам понадобятся следующие T -степени: 0 (степень, содержащая
все 0' (ее скачок, степень m -полного перечислимого неразрешимого множества; мы ее уже
рассматривали), затем 0'' (скачок степени 0' ), 0''' и так далее;
вообще 0(n+1)= (0(n))'.
Теорема 56. При любом n >= 1 класс $$\Sigma _{n}$$ совпадает с
классом всех 0(n-1) -перечислимых множеств.
(Пока что мы знаем это при n=1.)
Докажем сначала, что все $$\Sigma _{n}$$ -множества перечислимы
относительно 0(n-1). Это делается индукцией
по n.
При n=1 это известно. Рассмотрим теперь произвольное
множество X из $$\Sigma _{2}$$. По определению,
где R разрешимое свойство. Свойство $$\forall\ z\ R(x,y,z)$$
имеет перечислимое отрицание. Это отрицание разрешимо
относительно 0', так как m -сводится к m -полному
перечислимому множеству. Значит, и само свойство $$\forall \ z\ R(x,y,z)$$ разрешимо относительно 0'. Поэтому его
проекция, множество X, перечислимо
относительно 0'.
Аналогично можно рассуждать и для больших n. Если X принадлежит $$\Sigma _{3}$$, то
где R принадлежит $$\Pi _{2}$$. Отрицание R
принадлежит $$\Sigma _{2}$$
(по доказанному), поэтому 0' -перечислимо,
поэтому 0'' -разрешимо, поэтому само R тоже 0'' -разрешимо, а его проекция 0'' -перечислима.
Первая половина теоремы доказана.
Для доказательства второй половины нам потребуется некоторое
свойство классов $$\Sigma _{n}$$ и $$\Pi _{n}$$. Рассмотрим
какую-нибудь
вычислимую нумерацию всех конечных множеств натуральных чисел. Обозначим через Dx конечное множество номер x. Для
произвольного множества A рассмотрим
множество Subset(A) всех конечных подмножеств A,
точнее, множество всех их номеров:
Лемма 1. Если множество A принадлежит
классу $$\Sigma _{n}$$ [или $$\Pi _{n}$$ ], то
множество Subset(A) также
принадлежит
классу $$\Sigma _{n}$$ [соответственно $$\Pi _{n}$$ ].
(Утверждение этой леммы обобщает сформулированное в
задаче 63 утверждение о множестве Ax A: теперь мы
рассматриваем не пары, а произвольные кортежи.)
Доказательство леммы. Пусть множество A принадлежит,
например, классу $$\Sigma _{3}$$:
где R разрешимое свойство. Тогда можно записать
свойство $$\{ x_{1}, \dots ,x_{n}\} \subset A$$
следующим образом:
Эта формула использует кванторы по кортежам натуральных чисел (переменной длины), но их можно заменить на номера этих кортежей в какой-нибудь вычислимой нумерации. При этом стоящая под кванторами формула (она записана несколько условно: символическая конъюнкция на самом деле имеет переменную длину) является разрешимым свойством номеров кортежей, поэтому вся правая часть является $$\Sigma _{3}$$ -свойством.
(На самом деле мы допустили еще одну вольность речи: правая
часть является не свойством конечного
множества {x1,...,xn}, а
свойством
кортежа (упорядоченной последовательности) $$\langle
x_1,\dots,x_n\rangle$$. Но переход от номера множества к номеру
какого-то кортежа, содержащего все его элементы, вычислим,
так что проблемы тут нет.)
Лемма доказана.
68. Докажите, что
если A принадлежит
классу $$\Sigma _{n}$$ [ $$\Pi _{n}$$ ], то и
множество $$\in tersect(A)$$ номеров конечных множеств,
пересекающихся с A, принадлежит классу $$\Sigma _{n}$$
[ $$\Pi _{n}$$ ].
69. Пусть свойство R(x,y) пар натуральных чисел принадлежит классу $$\Sigma _{n}$$. Покажите, что свойство
принадлежит $$\Sigma _{n}$$. (Ограниченный квантор $$(\forall y \le x)$$ читается как " для всех y, не превосходящих x ".)
Переходя к дополнениям, мы немедленно получаем такое утверждение:
Лемма 2. Если A принадлежит
классу $$\Sigma _{n}$$ [ $$\Pi _{n}$$ ],
то множество Disjoint(A), состоящее из номеров конечных
множеств, не пересекающихся с A,
принадлежит $$\Pi _{n}$$ [ $$\Sigma _{n}$$ ].
Доказательство леммы. Не пересекаться с A означает быть
подмножеством дополнения к A, и остается воспользоваться
предыдущей леммой и тем, что дополнение к множеству из
класса $$\Sigma _{n}$$ [ $$\Pi _{n}$$ ] лежит в
классе $$\Pi _{n}$$ [ $$\Sigma _{n}$$ ].
Лемма доказана.
Теперь мы можем перейти к доказательству того факта, что все
множества, перечислимые относительно 0(n-1),
принадлежат классу $$\Sigma _{n}$$. Это также доказывается индукцией
по n.
Начнем с первого нетривиального случая: почему множество,
перечислимое относительно 0', лежит в $$\Sigma _{2}$$?
(Здесь можно было бы применить критерий 0' -вычислимости, приведенный выше, но мы предпочитаем
действовать по общей схеме, которая годится и для
больших n.)
Итак, пусть некоторое множество A перечислимо относительно 0'. Тогда оно перечислимо относительно некоторого перечислимого множества B, то есть перечислимо относительно характеристической функции b множества B. Согласно доказанному нами выше критерию (теорема 45), это означает, что существует перечислимое множество Q пар вида $$\langle x,t\rangle$$, где x число, а t образец, для которого
Без ограничения общности можно считать, что образец t представляет собой функцию, определенную на конечном множестве и принимающую значения 0 и 1. (Если у t есть какие-то другие значения, то он не может быть частью характеристической функции множества B и роли не играет.) Условие " b продолжает t " в терминах множества B звучит так: B содержит множество тех аргументов, на которых t принимает значение 1, и не пересекается с множеством тех аргументов, на которых t принимает значение 0. Поэтому вместо образцов можно говорить о парах конечных множеств; тогда вместо Q надо рассмотреть перечислимое множество P троек вида $$\langle x,u,v \rangle$$ и написать так:
Теперь вместо " Du содержится в B " напишем " $$u \in opSubset(B)$$ ", а вместо " Dv не пересекается с B " напишем " $$v \in Disjoint(B)$$ ". Остается заметить, что все три свойства, соединенные союзом " и" в правой части, принадлежат классу $$\Sigma _{2}$$ и даже меньшим классам. Именно, первые два принадлежат классу $$\Sigma _{1}$$, так как P и B перечислимы (для второго свойства применяем лемму 1). Третье же принадлежит классу $$\Pi _{1}$$ по лемме 2. Поэтому их конъюнкция принадлежит классу $$\Sigma _{2}$$, и n=2 разобран.
Далее, если какое-то множество A перечислимо относительно 0'', то по определению это означает, что оно перечислимо относительно некоторого B, которое перечислимо относительно 0' и потому лежит в $$\Sigma _{2}$$. После этого все рассуждения проходят точно так же со сдвигом на 1. Аналогично разбираются и все следующие значения n.
Из доказанной теоремы немедленно вытекает такое следствие:
Теорема 57. Пересечение классов $$\Sigma _{n} \cap \Pi _{n}$$ совпадает с классом разрешимых относительно 0(n-1) множеств.
В самом деле, релятивизованная теорема Поста (теорема 2) утверждает, что некоторое множество является X -разрешимым тогда и только тогда, когда оно и его дополнение X -перечислимы (здесь X произвольный оракул).
Теорема 58. Класс $$\Sigma _{n} \cup \Pi _{n}$$ является собственным подмножеством класса $$\Sigma _{n+1} \cap \Pi _{n+1}$$.
Вспомним, что такое 0(n). Это степень множества X, являющегося m -полным в классе 0(n-1) -перечислимых множеств. Поскольку X является m -полным в указанном классе, оно не 0(n-1) -разрешимо, то есть его дополнение не является 0(n-1) -перечислимым.
Значит, по доказанной только что теореме X принадлежит классу $$\Sigma _{n}$$, а его дополнение нет. Напротив, дополнение к X принадлежит $$\Pi _{n}$$, но не $$\Sigma _{n}$$. Рассмотрим теперь " соединение" множества X с его дополнением, е множество
К этому множеству m -сводятся как X, так и его дополнение, поэтому оно не может принадлежать ни $$\Sigma _{n}$$, ни $$\Pi _{n}$$. С другой стороны, оно, очевидно, разрешимо относительно X, поэтому по доказанной теореме принадлежит и $$\Sigma _{n+1}$$, и $$\Pi _{n+1}$$.
Интересно посмотреть, какое место разные конкретные множества занимают в описанной нами иерархии. Например, что можно сказать о множестве номеров какой-то фиксированной вычислимой функции в главной нумерации?
Мы уже говорили, что множество всех номеров всех функций с непустой областью определения перечислимо, то есть принадлежит классу $$\Sigma _{1}$$. Следовательно, его дополнение, множество всех номеров нигде не определенной функции, принадлежит классу $$\Pi _{1}$$. (Классу $$\Sigma _{1}$$ оно принадлежать не может, так как неразрешимо, см. теорему 21)
70.Докажите, что множество номеров нигде не определенной функции в любой главной нумерации является m -полным в классе $$\Pi _{1}$$ множеством.
А что можно сказать о номерах других функций? Например, что можно сказать о множестве номеров тождественно нулевой функции? Оказывается, можно получить в некотором смысле полный ответ на этот вопрос.
Теорема 59. (а) Пусть U вычислимая универсальная функция для класса вычислимых функций. Тогда множество тех n, при которых Un всюду определено и тождественно равно 0, принадлежит классу $$\Pi _{2}$$. (б) Пусть U главная универсальная функция. Тогда указанное множество является m -полным в классе $$\Pi _{2}$$.
Заметим, что требование главности в пункте (б) существенно: в однозначной нумерации это множество состоит из единственного номера.
Интересующее нас свойство числа n можно записать так: для любого k найдется такое t, что за t шагов вычисление значения U(n,k) закончится и даст результат 0. Выделенная часть является разрешимым свойством, а перед ней стоят два квантора как раз нужного вида. Итак, пункт (а) доказан.
Докажем утверждение (б). Пусть имеется произвольное множество P из класса $$\Pi _{2}$$. При этом
где R некоторое разрешимое свойство. Рассмотрим теперь функцию S(x,y), вычисляемую таким алгоритмом: перебирая все числа, ищем число z, для которого R(x,y,z) ; как только (и если) такое число найдено, выдаем на выход 0. Ясно, что x -ое сечение Sx функции S будет тождественно нулевой функцией в том и только том случае, когда $$x\in P$$. Применим свойство главности и получим функцию s, для которой Us(x)=Sx. Она и будет сводить P к множеству всех номеров тождественно нулевой функции.
Что можно сказать про другие функции? Для любой вычислимой универсальной функции U и любой вычислимой функции f множество всех U -номеров функции f является $$\Pi _{2}$$ -множеством. Верен даже более сильный факт: свойство Um=Un (числа m и n являются номерами одной и той же функции) является $$\Pi _{2}$$ -свойством пары $$\langle m,n\rangle$$, поэтому тем более любое его сечение (е множество всех номеров любой конкретной функции) является $$\Pi _{2}$$ -множеством.В самом деле, свойство Um=Un можно сформулировать так: " для всяких x и t1 найдется такое t2, что если вычисление U(m,x) завершается за t1 шагов, то вычисление U(n,x) завершается за t2 шагов с тем же результатом, и наоборот ". Выделенная часть разрешима, а до нее стоит $$\Pi _{2}$$ -префикс.
Можно даже понять, для каких функций множество номеров является $$\Pi _{2}$$ -полным: для функций с бесконечной областью определения. Если область определения функции конечна, то множество всех ее номеров является 0' -разрешимым (и потому не $$\Pi _{2}$$ -полным): имея оракул для проблемы остановки, можно убедиться, что функция определена всюду, где она должна быть определена (после чего проверить, что значения правильны), а затем проверить, что ни в одной из оставшихся точек она не определена (процесс поиска точки вне данного конечного множества, в которой функция определена, является перечислимым процессом и потому его успешность может быть проверена с помощью 0' -оракула).
Если же функция имеет бесконечную область определения, то существует бесконечное
71.Проведите это рассуждение подробно.
72.Покажите, что множество всех номеров всех всюду определенных функций (в главной нумерации) является $$\Pi _{2}$$ -полным.
73.В каком наименьшем классе арифметической иерархии лежит множество номеров всех функций с бесконечной областью определения? Будет ли оно m -полным в этом классе?
74.Покажите, что для любой (не обязательно главной!) нумерации множество всех номеров всюду определенных функций неперечислимо. Более того, оно не имеет перечислимого подмножества, включающего в себя хотя бы по одному номеру каждой вычислимой всюду определенной функции. (Указание: используйте диагональную конструкцию.)
В книге Х.Роджерса ([8], параграф 14.8) приведено много результатов подобного рода для многих других свойств вычислимых функций и перечислимых множеств. Например, для любого m -полного множества K множество всех его номеров является $$\Pi _{2}$$ -полным. (Здесь и далее, говоря о номерах, мы имеем в виду главную нумерацию перечислимых множеств.) Множество номеров всех конечных множеств является $$\Sigma _{2}$$ -полным. Множество номеров множеств, содержащих хотя бы один номер бесконечного множества, является $$\Sigma _{3}$$ -полным. Множество номеров всех
75. Докажите перечисленные утверждения (или прочтите их доказательства в книге Роджерса [8]).
76. Рассмотрим квантор $$\exists ^\infty x$$, который читается как "существует бесконечно много x, для которых". Покажите, что все свойства из класса $$\Pi _{2}$$ (и только они) представимы в виде
$$\exists ^\infty$$ x,(разрешимое свойство)
и что все свойства из класса $$\Sigma _{3}$$ (и только они) представимы в виде
$$\exists ^\infty x$$ $$\forall y$$ (разрешимое свойство).
(Аналогичное утверждение верно и для старших классов, см. теорему XVIII в разделе 14.8 книги [8].)
Для получения официальных документов о завершении программы дополнительного профессионального образования (удостоверения о повышении квалификации, дипломов о профессиональной переподготовке и MBA) необходимо предоставить:
Внимание! Вы можете не заказывать доставку бумажной версии официального документы, а скачать его в электронном виде и распечатать самостоятельно. Информация о выданном документе в течение 1 месяца загружается в Федеральную информационную систему «Федеральный реестр сведений о документах об образовании и (или) о квалификации, документах об обучении» - ФИС ФРДО.
Доступ на новый сайт осуществляется с использованием адреса электронной почты, который был указан вами при регистрации на "старом". Мы постарались перенести все ваши данные с прежнего ресурса, однако не исключена вероятность потери части информации.
При возникновении проблемы со входом, воспользуйтесь функцией сброса пароля
Если вы обнаружите несоответствия, пожалуйста, сообщите нам.