Cтраница 2
Пга получаются навешиванием кванторов на разрешимые множества, а разрешимое множество арифметично. [16]
Напомним, что они называются неотделимыми, если не существует разрешимого множества, содержащего одно из них и не пересекающегося с другим. Это определение можно переформулировать так: если Wx и Wy - два непересекающихся перечислимых множества, содержащие А и В соответственно, то объединение Wx U Wy содержит не все натуральные числа. Нам будет удобно обозначать перечислимые множества через Wx и Wv, считая, что W - главное универсальное множество. [17]
Заметим, что перечислимые множества могут быть описаны иначе как проекции разрешимых множеств и что в этом контексте проекции не создают неразрешимых множеств. [18]
Мы уже говорили, что перечислимые множества можно эквивалентно определить как проекции разрешимых множеств: множество А С N перечислимо тогда и только тогда, когда существует разрешимое множество В С С N х BJ, проекцией которого оно является. [19]
Существуют два непересекающихся перечислимых множества X и Y, которые не отделяются никаким разрешимым множеством. [20]
Теория первого порядка называется разрешимо аксиматизируе-мой, если она имеет хотя бы одно разрешимое множество аксиом. [21]
Сводимость Р к К имеет место всегда, а к Р не сводится ни одно разрешимое множество. [22]
Если Е - неразрешимое рекурсивно перечислимое множество, то из этого соотношения следует незамкнутость класса разрешимых множеств относительно экзистенциальной квантификации. [23]
Множество Р натуральных чисел перечислимо тогда и только тогда, когда оно является проекцией некоторого разрешимого множества Q пар натуральных чисел. [24]
В самом деле, если X разрешимо, то мы можем отделить Р от Q разрешимым множеством. [25]
Из этого замечания следует, что если заменить исчисление предикатов любой другой формальной системой с разрешимым множеством аксиом и конечным числом разрешимых правил вывода, то лемма остается верной. [26]
Напротив, если Р - перечислимое множество, перечисляемое алгоритмом А, то оно есть проекция разрешимого множества Q, состоящего из всех таких пар ( ж п), что х появляется в течении первых п шагов работы алгоритма А. [27]
Покажите, что существует счетное число непересекающихся перечислимых множеств, никакие два из которых нельзя отделить разрешимым множеством. [28]
Проекция любого перечислимого множества перечислима ( перечисляющий алгоритм должен лишь удалять вторые члены пар), так что проекция разрешимого множества тем более перечислима. [29]
Отметим, что если отношение R разрешимо, то его область определения ( значений) не обязательно разрешима - класс разрешимых множеств не замкнут относительно экзистенциальной квантификации. [30]