В теории рекурсии , α теория рекурсии является обобщением теории рекурсии для подмножеств допустимых порядковых . Допустимое множество замкнуто относительно функции, где обозначает ранг конструктивной иерархии Гёделя . Еслиявляется моделью теории множеств Крипке – Платека, тодопустимый ординал. В дальнейшем считается исправленным.
Объекты исследования в рекурсия - это подмножества . Говорят, что эторекурсивно перечислимым, если это определяемый по . A рекурсивно, если и A, и (его дополнение в ) находятся рекурсивно перечислимый.
Члены называются конечны и играют роль, аналогичную конечным числам в классической теории рекурсии.
Мы говорим, что R - процедура редукции, если она рекурсивно перечислимым, и каждый член R имеет вид где H , J , K все α-конечны.
A называется α-рекурсивным в B, если существуют процедуры сокращения, такие как:
Если A рекурсивно в B, это записывается. По этому определению A рекурсивна в( пустое множество ) тогда и только тогда, когда A рекурсивно. Однако рекурсивность A в B не эквивалентна тому, что A является.
Мы говорим A регулярным, еслиили другими словами, если каждая начальная часть A является α-конечной.
Результаты в рекурсия
Теорема Шора о расщеплении: пусть A будет рекурсивно перечислимый и регулярный. Существуют рекурсивно перечислимый такой, что
Теорема Шора о плотности: пусть A , C - α-регулярные рекурсивно перечислимые множества такие, чтото существует регулярное α-рекурсивно перечислимое множество B такое, что.
Рекомендации
- Джеральд Сакс, Высшая теория рекурсии , Springer Verlag, 1990 https://projecteuclid.org/euclid.pl/1235422631
- Роберт Соар, Рекурсивно перечислимые множества и степени , Springer Verlag, 1987 г. https://projecteuclid.org/euclid.bams/1183541465
- Кейт Дж. Девлин, Введение в тонкую структуру конструируемой иерархии (стр.38), North-Holland Publishing, 1974