En la teoría de la recursividad , la teoría de la recursividad α es una generalización de la teoría de la recursividad a subconjuntos de ordinales admisibles. . Un juego admisible se cierra bajo funciones, donde denota un rango de la jerarquía constructiva de Gödel . Sies un modelo de la teoría de conjuntos de Kripke-Platek, entonceses un ordinal admisible. En lo que sigue se considera fijo.
Los objetos de estudio en recursividad son subconjuntos de . Se dice que A esrecursivamente enumerable si es definible sobre . A es recursivo si tanto A como (su complemento en ) están recursivamente enumerable.
Miembros de son llamados finitos y juegan un papel similar a los números finitos en la teoría de recursividad clásica.
Decimos que R es un procedimiento de reducción si es recursivamente enumerable y cada miembro de R tiene la forma donde H , J , K son todos α-finitos.
Se dice que A es α-recursivo en B si existen procedimientos de reducción tales que:
Si A es recursivo en B, esto se escribe. Según esta definición, A es recursiva en(el conjunto vacío ) si y solo si A es recursivo. Sin embargo, que A sea recursivo en B no es equivalente a que A sea.
Decimos que A es regular sio en otras palabras, si cada porción inicial de A es α-finita.
Resultados en recursividad
Teorema de la división de Shore: Sea A recursivamente enumerable y regular. Allí existe recursivamente enumerable tal que
Teorema de la densidad de Shore: Sean A , C conjuntos α-regulares enumerables recursivamente, tales queentonces existe un conjunto B regular enumerable recursivamente α tal que.
Referencias
- Gerald Sacks, Teoría de recursividad superior , Springer Verlag, 1990 https://projecteuclid.org/euclid.pl/1235422631
- Robert Soare, Conjuntos y grados recursivamente enumerables , Springer Verlag, 1987 https://projecteuclid.org/euclid.bams/1183541465
- Keith J. Devlin, Introducción a la fina estructura de la jerarquía constructible (p. 38), North-Holland Publishing, 1974