Cтраница 2
Действительно, позитивность или негативность нумерованного множества означает, что его номерное множество рекурсивно перечислимо и что отношение равенства или соответственно неравенства двух элементов этого множества является на нем рекурсивно перечислимым предикатом. [16]
Нумерация а произвольного множества А выше была названа простой, если номерное множество Da есть множество всех натуральных чисел. Следующая очевидная теорема показывает, что при довольно широких предположениях изучение произвольных нумераций можно сводить к изучению простых нумераций. [17]
Пусть нумерации a, p имеют R - бесконечные классы и их номерные множества Zat D являются R - множествами. Тогда из R - эквивалентности а и р следует W-изоморфизм этих нумераций. [18]
В доказанной теореме утверждается, что порожденная подсистема 61 есть а-образ ] рекурсивно перечислимого подмножества номерного множества. Это еще не дает права утверждать, что SR - рекурсивно перечислимая подалгебра, так как последнее означает, что рекурсивно перечислимо множество всех номеров элементов 9Ю, а не только тех, которые получаются при помощи термов. Однако следующее простое замечание показывает, что в большинстве важных случаев рекурсивная перечислимость 9Ю имеет место и в смысле первоначального определения. [19]
Если множество А имеет позитивную нумерацию а, то а-образ каждого рекурсивно перечислимого подмножества М номерного множества Da есть рекурсивно перечислимое подмножество А. [20]
Снова из теоремы 3.1.1 следует, что если одна из двух ор-эквивалентных алгебраических систем с общерекурсивными номерными множествами является конструктивной, то другая также конструктивна. Кроме того, согласно теореме 2.1.2 чр-изоморфизм и чр-эквивалентность одной конструктивной системы на другую являются вместе с тем и op - изоморфизмом и соответственно ор-эквивалентностью. [21]
Согласно теореме 3.1.1, если одна из двух пр-эквивалентных алгебраических систем, имеющих простые нумерации с примитивно рекурсивными номерными множествами, является примитивно рекурсивной, то вторая система также примитивно рекурсивна. [22]
Наконец, нумерованную алгебраическую систему условимся называть примитивно рекурсивной, если она имеет однозначную примитивно рекурсивную нумерацию, номерное множество которой также примитивно рекурсивно. [23]
Из теоремы 3.1.1 следует, что если одна из двух op - эквивалентных алгебраических систем, обладающих рекурсивно перечислимыми номерными множествами, является обще рекурсивной, то другая система также общерекурсивна. [24]
Из теорем 2.1.1 и 2.1.2 следует, что отношение ор-униморфизма равносильно отношению op - изоморфизма на классе нумерованных множеств с общерекурсивными номерными множествами. [25]
Тогда термальная подсистема 31, определяемая термами из Т при переменных, пробегающих множество аМ, есть а-образ подходящего абсолютно рекурсивно перечислимого подмножества номерного множества. [26]
Отсюда в свою очередь следует, что условия теоремы 2.3.1 остаются необходимыми и достаточными и для того, чтобы нумерация а была R - экви-валентна однозначной нумерации с рекурсивно перечислимым номерным множеством. [27]
С другой стороны, если нумерация а однозначна, то в качестве L ( х, у) можно взять sg х - у и из теоремы 2.3.1 непосредственно вытекает, что однозначная нумерация а тогда и только тогда R - эквивалентна простой однозначной нумерации, когда номерное множество Da рекурсивно перечислимо. [28]
Важнейшими характеристиками каждой нумерации а служат тип ее номерного множества Da и тип отношения эквивалентности 0а на Za, порождаемого нумерацией а. Номерные множества J9Y и D стандартных нумераций конечно порожденных алгебр имеют простое строение - они примитивно рекурсивны. Что же касается соответствующих эквивалентностей 0Y, Э §, то они могут быть рекурсивными всех трех типов пр, ор, чр, а также могут и не быть рекурсивно перечислимыми. Какой из этих случаев имеет место - зависит от внутреннего строения алгебры. [29]
Отметим, что согласно терминологии, принятой в предыдущем и данном пунктах, R-подсистема нумерованной системы может и не быть R-системой. Например, пусть номерное множество Da не содержит бесконечных абсолютных чр-подмножеств, но пересечение Z) a с подходящим op - множеством пусть бесконечно. [30]