En el campo matemático de la teoría de la computabilidad , un grado de PA es un grado de Turing que calcula una extensión completa de la aritmética de Peano (Jockusch 1987). Estos grados están estrechamente relacionados con las funciones de punto fijo libre (DNR) y han sido investigados exhaustivamente en la teoría de la recursión.
En teoría de recursión, denota la función computable con índice (programa) e en alguna numeración estándar de funciones computables, y denota la e- ésima función computable utilizando un conjunto B de números naturales como oráculo.
Un conjunto A de números naturales es reducible por Turing a un conjunto B si existe una función computable que, dado un oráculo para el conjunto B , calcula la función característica χ A del conjunto A . Es decir, existe un e tal que . Esta relación se denota A ≤ T B ; la relación ≤ T es un preorden .
Dos conjuntos de números naturales son equivalentes de Turing si cada uno es reducible de Turing al otro. La notación A ≡ T B indica que A y B son equivalentes de Turing. La relación ≡ T es una relación de equivalencia conocida como equivalencia de Turing. Un grado de Turing es una colección de conjuntos de números naturales, de modo que dos conjuntos cualesquiera de la colección son equivalentes de Turing. De manera equivalente, un grado de Turing es una clase de equivalencia de la relación ≡ T .
Los grados de Turing están parcialmente ordenados por la reducibilidad de Turing. La notación a ≤ T b indica que hay un conjunto de grado b que calcula un conjunto de grado a . De manera equivalente, a ≤ T b se cumple si y solo si cada conjunto de b calcula cada conjunto de a .
Se dice que una función f de los números naturales a los números naturales es diagonalmente no recursiva (DNR) si, para todo n , (aquí la desigualdad se cumple por definición si no está definida). Si el rango de f es el conjunto {0,1} entonces f es una función DNR 2 . Se sabe que hay funciones DNR que no calculan ninguna función DNR 2 .
Una compleción de la aritmética de Peano es un conjunto de fórmulas en el lenguaje de la aritmética de Peano, tal que el conjunto es consistente en lógica de primer orden y tal que, para cada fórmula, dicha fórmula o su negación está incluida en el conjunto. Una vez que se ha fijado una numeración de Gödel de las fórmulas en el lenguaje de la PA, es posible identificar compleciones de la PA con conjuntos de números naturales y, por lo tanto, hablar de la computabilidad de estas compleciones.
Un grado de Turing se define como un grado PA si hay un conjunto de números naturales en el grado que calcula una completitud de la Aritmética de Peano. (Esto es equivalente a la proposición de que cada conjunto en el grado calcula una completitud de PA). Debido a que no hay completitudes computables de PA, el grado 0 que consiste en los conjuntos computables de números naturales no es un grado PA.
Debido a que PA es una teoría de primer orden eficaz, las compleciones de PA se pueden caracterizar como los caminos infinitos a través de un subárbol computable particular de 2 < ω . Por lo tanto, los grados de PA son exactamente los grados que calculan un camino infinito a través de este árbol.
Los grados PA están cerrados hacia arriba en los grados de Turing: si a es un grado PA y a ≤ T b entonces b es un grado PA.
El grado de Turing 0 ', que es el grado del problema de detención , es un grado PA. También hay grados PA que no son mayores que 0 '. Por ejemplo, el teorema de base baja implica que hay un grado PA bajo. Por otro lado, Antonín Kučera ha demostrado que hay un grado menor que 0 ' que calcula una función DNR pero no es un grado PA (Jockusch 1989:197).
Carl Jockusch y Robert Soare (1972) demostraron que los grados de PA son exactamente los grados de las funciones DNR 2 .
Por definición, un grado es PA si y solo si calcula un camino a través del árbol de compleciones de la aritmética de Peano. Se cumple una propiedad más fuerte: un grado a es un grado PA si y solo si a calcula un camino a través de cada subárbol computable infinito de 2 < ω (Simpson 1977).
MM Arslanov dio una caracterización de qué conjuntos ce son completos (es decir, equivalentes de Turing a ). Para un conjunto ce , si y solo si se calcula una función DNR. En particular, cada grado de PA es DNR 2 y, por lo tanto, DNR, por lo que es el único grado de PA ce.
