Jerarquía aritmética

Jerarquía de clases de complejidad para fórmulas que definen conjuntos

Una ilustración de cómo interactúan los niveles de la jerarquía y dónde se encuentran algunas categorías de conjuntos básicos dentro de ella.

En lógica matemática , la jerarquía aritmética , jerarquía aritmética o jerarquía de Kleene-Mostowski (en honor a los matemáticos Stephen Cole Kleene y Andrzej Mostowski ) clasifica ciertos conjuntos en función de la complejidad de las fórmulas que los definen . Cualquier conjunto que recibe una clasificación se denomina aritmético . La jerarquía aritmética fue inventada independientemente por Kleene (1943) y Mostowski (1946). ^[1]

La jerarquía aritmética es importante en la teoría de la computabilidad , la teoría de conjuntos descriptivos efectivos y el estudio de teorías formales como la aritmética de Peano .

El algoritmo de Tarski–Kuratowski proporciona una manera sencilla de obtener un límite superior para las clasificaciones asignadas a una fórmula y al conjunto que define.

La jerarquía hiperaritmética y la jerarquía analítica extienden la jerarquía aritmética para clasificar fórmulas y conjuntos adicionales.

La jerarquía aritmética de fórmulas

La jerarquía aritmética asigna clasificaciones a las fórmulas en el lenguaje de la aritmética de primer orden . Las clasificaciones se denotan como y para los números naturales n (incluido el 0). Las letras griegas aquí son símbolos de letras claras , lo que indica que las fórmulas no contienen parámetros establecidos. ^{[ aclaración necesaria ]} ${\displaystyle \Sigma _{n}^{0}}$ ${\displaystyle \Pi _{n}^{0}}$

Si una fórmula es lógicamente equivalente a una fórmula que no tiene cuantificadores ilimitados, es decir, en la que todos los cuantificadores son cuantificadores acotados , entonces se le asignan las clasificaciones y . ${\displaystyle \phi }$ ${\displaystyle \phi }$ ${\displaystyle \Sigma _{0}^{0}}$ ${\displaystyle \Pi _{0}^{0}}$

Las clasificaciones y se definen inductivamente para cada número natural n utilizando las siguientes reglas: ${\displaystyle \Sigma _{n}^{0}}$ ${\displaystyle \Pi _{n}^{0}}$

• Si es lógicamente equivalente a una fórmula de la forma , donde es , entonces se le asigna la clasificación . ${\displaystyle \phi }$ ${\displaystyle \exists m_{1}\exists m_{2}\cdots \exists m_{k}\psi }$ ${\displaystyle \psi }$ ${\displaystyle \Pi _{n}^{0}}$ ${\displaystyle \phi }$ ${\displaystyle \Sigma _{n+1}^{0}}$
• Si es lógicamente equivalente a una fórmula de la forma , donde es , entonces se le asigna la clasificación . ${\displaystyle \phi }$ ${\displaystyle \forall m_{1}\forall m_{2}\cdots \forall m_{k}\psi }$ ${\displaystyle \psi }$ ${\displaystyle \Sigma _{n}^{0}}$ ${\displaystyle \phi }$ ${\displaystyle \Pi _{n+1}^{0}}$

Una fórmula es equivalente a una fórmula que comienza con algunos cuantificadores existenciales y alterna veces entre series de cuantificadores existenciales y universales ; mientras que una fórmula es equivalente a una fórmula que comienza con algunos cuantificadores universales y alterna análogamente. ${\displaystyle \Sigma _{n}^{0}}$ ${\displaystyle n-1}$ ${\displaystyle \Pi _{n}^{0}}$

Como cada fórmula de primer orden tiene una forma normal prenexa , a cada fórmula se le asigna al menos una clasificación. Como se pueden agregar cuantificadores redundantes a cualquier fórmula, una vez que se le asigna a una fórmula la clasificación o se le asignarán las clasificaciones y para cada m > n . La única clasificación relevante asignada a una fórmula es, por lo tanto, la que tiene el menor n ; todas las demás clasificaciones se pueden determinar a partir de ella. ${\displaystyle \Sigma _{n}^{0}}$ ${\displaystyle \Pi _{n}^{0}}$ ${\displaystyle \Sigma _{m}^{0}}$ ${\displaystyle \Pi _{m}^{0}}$

La jerarquía aritmética de conjuntos de números naturales

Un conjunto X de números naturales se define mediante una fórmula φ en el lenguaje de la aritmética de Peano (el lenguaje de primer orden con símbolos "0" para cero, "S" para la función sucesora, "+" para la adición, "×" para la multiplicación y "=" para la igualdad), si los elementos de X son exactamente los números que satisfacen φ . Es decir, para todos los números naturales n ,

${\displaystyle n\in X\Leftrightarrow \mathbb {N} \models \varphi ({\underline {n}}),}$

donde es el numeral en el lenguaje de la aritmética correspondiente a . Un conjunto es definible en aritmética de primer orden si se define mediante alguna fórmula en el lenguaje de la aritmética de Peano. ${\displaystyle {\underline {n}}}$ ${\displaystyle n}$

A cada conjunto X de números naturales que se pueden definir en aritmética de primer orden se le asignan clasificaciones de la forma , , y , donde es un número natural, de la siguiente manera. Si X se puede definir mediante una fórmula, entonces a X se le asigna la clasificación . Si X se puede definir mediante una fórmula, entonces a X se le asigna la clasificación . Si X es ambas cosas y entonces se le asigna la clasificación adicional . ${\displaystyle \Sigma _{n}^{0}}$ ${\displaystyle \Pi _{n}^{0}}$ ${\displaystyle \Delta _{n}^{0}}$ ${\displaystyle n}$ ${\displaystyle \Sigma _{n}^{0}}$ ${\displaystyle \Sigma _{n}^{0}}$ ${\displaystyle \Pi _{n}^{0}}$ ${\displaystyle \Pi _{n}^{0}}$ ${\displaystyle \Sigma _{n}^{0}}$ ${\displaystyle \Pi _{n}^{0}}$ ${\displaystyle X}$ ${\displaystyle \Delta _{n}^{0}}$

Obsérvese que rara vez tiene sentido hablar de fórmulas; el primer cuantificador de una fórmula es existencial o universal. Por lo tanto, un conjunto no se define necesariamente mediante una fórmula en el sentido de una fórmula que sea a la vez y ; más bien, existen fórmulas y que definen el conjunto. Por ejemplo, el conjunto de números naturales impares se puede definir mediante o . ${\displaystyle \Delta _{n}^{0}}$ ${\displaystyle \Delta _{n}^{0}}$ ${\displaystyle \Delta _{n}^{0}}$ ${\displaystyle \Sigma _{n}^{0}}$ ${\displaystyle \Pi _{n}^{0}}$ ${\displaystyle \Sigma _{n}^{0}}$ ${\displaystyle \Pi _{n}^{0}}$ ${\displaystyle n}$ ${\displaystyle \forall k(n\neq 2\times k)}$ ${\displaystyle \exists k(n=2\times k+1)}$

Se utiliza una definición paralela para definir la jerarquía aritmética sobre potencias cartesianas finitas del conjunto de números naturales. En lugar de fórmulas con una variable libre, se utilizan fórmulas con k variables libres de primer orden para definir la jerarquía aritmética sobre conjuntos de k - tuplas de números naturales. De hecho, estos están relacionados mediante el uso de una función de emparejamiento .

Significado de la notación

A la notación de la jerarquía aritmética de las fórmulas se le pueden atribuir los siguientes significados.

El subíndice en los símbolos y indica el número de alternancias de bloques de cuantificadores universales y existenciales de primer orden que se utilizan en una fórmula. Además, el bloque más externo es existencial en las fórmulas y universal en las fórmulas. ${\displaystyle n}$ ${\displaystyle \Sigma _{n}^{0}}$ ${\displaystyle \Pi _{n}^{0}}$ ${\displaystyle \Sigma _{n}^{0}}$ ${\displaystyle \Pi _{n}^{0}}$

El superíndice en los símbolos , , y indica el tipo de los objetos sobre los que se cuantifica. Los objetos de tipo 0 son números naturales y los objetos de tipo son funciones que asignan el conjunto de objetos de tipo a los números naturales. La cuantificación sobre objetos de tipo superior, como funciones de números naturales a números naturales, se describe mediante un superíndice mayor que 0, como en la jerarquía analítica . El superíndice 0 indica cuantificadores sobre números, el superíndice 1 indicaría cuantificación sobre funciones de números a números (objetos de tipo 1), el superíndice 2 correspondería a cuantificación sobre funciones que toman un objeto de tipo 1 y devuelven un número, y así sucesivamente. ${\displaystyle 0}$ ${\displaystyle \Sigma _{n}^{0}}$ ${\displaystyle \Pi _{n}^{0}}$ ${\displaystyle \Delta _{n}^{0}}$ ${\displaystyle i+1}$ ${\displaystyle i}$

Ejemplos

• Los conjuntos de números son aquellos definibles mediante una fórmula de la forma donde sólo hay cuantificadores acotados. Éstos son exactamente los conjuntos enumerables recursivamente . ${\displaystyle \Sigma _{1}^{0}}$ ${\displaystyle \exists n_{1}\cdots \exists n_{k}\psi (n_{1},\ldots ,n_{k},m)}$ ${\displaystyle \psi }$
• El conjunto de números naturales que son índices para las máquinas de Turing que calculan funciones totales es . Intuitivamente, un índice cae en este conjunto si y solo si para cada "existe un tal que la máquina de Turing con índice se detiene al ingresar datos después de pasos". Una prueba completa mostraría que la propiedad que se muestra entre comillas en la oración anterior se puede definir en el lenguaje de la aritmética de Peano mediante una fórmula. ${\displaystyle \Pi _{2}^{0}}$ ${\displaystyle e}$ ${\displaystyle m}$ ${\displaystyle s}$ ${\displaystyle e}$ ${\displaystyle m}$ ${\displaystyle s}$ ${\displaystyle \Sigma _{1}^{0}}$
• Todo subconjunto del espacio de Baire o del espacio de Cantor es un conjunto abierto en la topología usual del espacio. Además, para cualquier conjunto de este tipo existe una enumeración computable de números de Gödel de conjuntos abiertos básicos cuya unión es el conjunto original. Por esta razón, a veces se dice que los conjuntos son efectivamente abiertos . De manera similar, todo conjunto es cerrado y a veces se dice que los conjuntos son efectivamente cerrados . ${\displaystyle \Sigma _{1}^{0}}$ ${\displaystyle \Sigma _{1}^{0}}$ ${\displaystyle \Pi _{1}^{0}}$ ${\displaystyle \Pi _{1}^{0}}$
• Cada subconjunto aritmético del espacio de Cantor o del espacio de Baire es un conjunto de Borel . La jerarquía de Borel de lightface extiende la jerarquía aritmética para incluir conjuntos de Borel adicionales. Por ejemplo, cada subconjunto del espacio de Cantor o de Baire es un conjunto , es decir, un conjunto que es igual a la intersección de un número contable de conjuntos abiertos. Además, cada uno de estos conjuntos abiertos es y la lista de números de Gödel de estos conjuntos abiertos tiene una enumeración computable. Si es una fórmula con una variable de conjunto libre y variables de número libre , entonces el conjunto es la intersección de los conjuntos de la forma como rangos sobre el conjunto de números naturales. ${\displaystyle \Pi _{2}^{0}}$ ${\displaystyle G_{\delta }}$ ${\displaystyle \Sigma _{1}^{0}}$ ${\displaystyle \phi (X,n,m)}$ ${\displaystyle \Sigma _{0}^{0}}$ ${\displaystyle X}$ ${\displaystyle n,m}$ ${\displaystyle \Pi _{2}^{0}}$ ${\displaystyle \{X\mid \forall n\exists m\phi (X,n,m)\}}$ ${\displaystyle \Sigma _{1}^{0}}$ ${\displaystyle \{X\mid \exists m\phi (X,n,m)\}}$ ${\displaystyle n}$
• Las fórmulas se pueden comprobar revisando todos los casos uno por uno, lo que es posible porque todos sus cuantificadores están acotados. El tiempo para esto es polinomial en sus argumentos (por ejemplo, polinomial en para ); por lo tanto, sus problemas de decisión correspondientes se incluyen en E (como lo es exponencial en su número de bits). Esto ya no se cumple con definiciones alternativas de que permiten el uso de funciones recursivas primitivas , ya que ahora los cuantificadores pueden estar acotados por cualquier función recursiva primitiva de los argumentos. ${\displaystyle \Sigma _{0}^{0}=\Pi _{0}^{0}=\Delta _{0}^{0}}$ ${\displaystyle n}$ ${\displaystyle \varphi (n)}$ ${\displaystyle n}$ ${\displaystyle \Sigma _{0}^{0}=\Pi _{0}^{0}=\Delta _{0}^{0}}$
• Las fórmulas bajo una definición alternativa, que permite el uso de funciones recursivas primitivas con cuantificadores acotados, corresponden a conjuntos de números naturales de la forma para una función recursiva primitiva . Esto se debe a que permitir el uso de cuantificadores acotados no agrega nada a la definición: para una función recursiva primitiva , es lo mismo que , y es lo mismo que ; con la recursión de curso de valores cada una de estas puede definirse mediante una única función recursiva primitiva. ${\displaystyle \Sigma _{0}^{0}=\Pi _{0}^{0}=\Delta _{0}^{0}}$ ${\displaystyle \{n:f(n)=0\}}$ ${\displaystyle f}$ ${\displaystyle f}$ ${\displaystyle \forall k<n:f(k)=0}$ ${\displaystyle f(0)+f(1)+...f(n)=0}$ ${\displaystyle \exists k<n:f(k)=0}$ ${\displaystyle f(0)\cdot f(1)\cdot \ldots \cdot f(n)=0}$

Jerarquías aritméticas relativizadas

Así como podemos definir lo que significa que un conjunto X sea recursivo en relación con otro conjunto Y al permitir que el cálculo que define a X consulte a Y como un oráculo, podemos extender esta noción a toda la jerarquía aritmética y definir lo que significa que X sea , o en Y , denotado respectivamente , y . Para ello, fijamos un conjunto de números naturales Y y añadimos un predicado para la pertenencia de Y al lenguaje de la aritmética de Peano. Entonces decimos que X está en si está definido por una fórmula en este lenguaje expandido. En otras palabras, X es si está definido por una fórmula que permite hacer preguntas sobre la pertenencia de Y . Alternativamente, uno puede ver los conjuntos como aquellos conjuntos que pueden construirse comenzando con conjuntos recursivos en Y y tomando alternativamente uniones e intersecciones de estos conjuntos hasta n veces. ${\displaystyle \Sigma _{n}^{0}}$ ${\displaystyle \Delta _{n}^{0}}$ ${\displaystyle \Pi _{n}^{0}}$ ${\displaystyle \Sigma _{n}^{0,Y}}$ ${\displaystyle \Delta _{n}^{0,Y}}$ ${\displaystyle \Pi _{n}^{0,Y}}$ ${\displaystyle \Sigma _{n}^{0,Y}}$ ${\displaystyle \Sigma _{n}^{0}}$ ${\displaystyle \Sigma _{n}^{0,Y}}$ ${\displaystyle \Sigma _{n}^{0}}$ ${\displaystyle \Sigma _{n}^{0,Y}}$

Por ejemplo, sea Y un conjunto de números naturales. Sea X el conjunto de números divisibles por un elemento de Y. Entonces, X se define mediante la fórmula, por lo que X está en (en realidad, también está en , ya que podríamos limitar ambos cuantificadores por n ). ${\displaystyle \phi (n)=\exists m\exists t(Y(m)\land m\times t=n)}$ ${\displaystyle \Sigma _{1}^{0,Y}}$ ${\displaystyle \Delta _{0}^{0,Y}}$

Reducibilidad aritmética y grados

La reducibilidad aritmética es una noción intermedia entre la reducibilidad de Turing y la reducibilidad hiperaritmética .

Un conjunto es aritmético (también aritmético y aritméticamente definible ) si está definido por alguna fórmula en el lenguaje de la aritmética de Peano. Equivalentemente, X es aritmético si X es o para algún número natural n . Un conjunto X es aritmético en un conjunto Y , denotado , si X es definible como alguna fórmula en el lenguaje de la aritmética de Peano extendida por un predicado para la pertenencia de Y. Equivalentemente, X es aritmético en Y si X está en o para algún número natural n . Un sinónimo de es: X es aritméticamente reducible a Y. ${\displaystyle \Sigma _{n}^{0}}$ ${\displaystyle \Pi _{n}^{0}}$ ${\displaystyle X\leq _{A}Y}$ ${\displaystyle \Sigma _{n}^{0,Y}}$ ${\displaystyle \Pi _{n}^{0,Y}}$ ${\displaystyle X\leq _{A}Y}$

La relación es reflexiva y transitiva , y por tanto la relación definida por la regla ${\displaystyle X\leq _{A}Y}$ ${\displaystyle \equiv _{A}}$

${\displaystyle X\equiv _{A}Y\iff X\leq _{A}Y\land Y\leq _{A}X}$

es una relación de equivalencia . Las clases de equivalencia de esta relación se denominan grados aritméticos ; están parcialmente ordenadas según . ${\displaystyle \leq _{A}}$

La jerarquía aritmética de subconjuntos del espacio de Cantor y Baire

El espacio de Cantor , denotado como , es el conjunto de todas las sucesiones infinitas de 0 y 1; el espacio de Baire , denotado como , es el conjunto de todas las sucesiones infinitas de números naturales. Nótese que los elementos del espacio de Cantor pueden identificarse con conjuntos de números naturales y los elementos del espacio de Baire con funciones de números naturales a números naturales. ${\displaystyle 2^{\omega }}$ ${\displaystyle \omega ^{\omega }}$ ${\displaystyle {\mathcal {N}}}$

La axiomatización ordinaria de la aritmética de segundo orden utiliza un lenguaje basado en conjuntos en el que los cuantificadores de conjuntos pueden verse naturalmente como cuantificadores sobre el espacio de Cantor. A un subconjunto del espacio de Cantor se le asigna la clasificación si es definible por una fórmula. Al conjunto se le asigna la clasificación si es definible por una fórmula. Si el conjunto es ambos y entonces se le da la clasificación adicional . Por ejemplo, sea el conjunto de todas las cadenas binarias infinitas que no son todas 0 (o equivalentemente el conjunto de todos los conjuntos no vacíos de números naturales). Como vemos, se define por una fórmula y, por lo tanto, es un conjunto. ${\displaystyle \Sigma _{n}^{0}}$ ${\displaystyle \Sigma _{n}^{0}}$ ${\displaystyle \Pi _{n}^{0}}$ ${\displaystyle \Pi _{n}^{0}}$ ${\displaystyle \Sigma _{n}^{0}}$ ${\displaystyle \Pi _{n}^{0}}$ ${\displaystyle \Delta _{n}^{0}}$ ${\displaystyle O\subseteq 2^{\omega }}$ ${\displaystyle O=\{X\in 2^{\omega }|\exists n(X(n)=1)\}}$ ${\displaystyle O}$ ${\displaystyle \Sigma _{1}^{0}}$ ${\displaystyle \Sigma _{1}^{0}}$

Nótese que, si bien tanto los elementos del espacio de Cantor (considerados conjuntos de números naturales) como los subconjuntos del espacio de Cantor se clasifican en jerarquías aritméticas, no se trata de la misma jerarquía. De hecho, la relación entre las dos jerarquías es interesante y no trivial. Por ejemplo, los elementos del espacio de Cantor no son (en general) los mismos que los elementos del espacio de Cantor, por lo que este último es un subconjunto del espacio de Cantor. Sin embargo, muchos resultados interesantes relacionan las dos jerarquías. ${\displaystyle \Pi _{n}^{0}}$ ${\displaystyle X}$ ${\displaystyle \{X\}}$ ${\displaystyle \Pi _{n}^{0}}$

Hay dos formas en que un subconjunto del espacio de Baire puede clasificarse en la jerarquía aritmética.

• Un subconjunto del espacio de Baire tiene un subconjunto correspondiente del espacio de Cantor bajo la función que toma cada función de a a la función característica de su gráfico. A un subconjunto del espacio de Baire se le asigna la clasificación , , o si y solo si el subconjunto correspondiente del espacio de Cantor tiene la misma clasificación. ${\displaystyle \omega }$ ${\displaystyle \omega }$ ${\displaystyle \Sigma _{n}^{0}}$ ${\displaystyle \Pi _{n}^{0}}$ ${\displaystyle \Delta _{n}^{0}}$
• Una definición equivalente de la jerarquía aritmética en el espacio de Baire se da definiendo la jerarquía aritmética de fórmulas utilizando una versión funcional de la aritmética de segundo orden; luego, la jerarquía aritmética en subconjuntos del espacio de Cantor se puede definir a partir de la jerarquía en el espacio de Baire. Esta definición alternativa proporciona exactamente las mismas clasificaciones que la primera definición.

Se utiliza una definición paralela para definir la jerarquía aritmética en potencias cartesianas finitas del espacio de Baire o del espacio de Cantor, utilizando fórmulas con varias variables libres. La jerarquía aritmética se puede definir en cualquier espacio polaco efectivo ; la definición es particularmente simple para el espacio de Cantor y el espacio de Baire porque se ajustan al lenguaje de la aritmética ordinaria de segundo orden.

Nótese que también podemos definir la jerarquía aritmética de los subconjuntos de los espacios de Cantor y Baire en relación con algún conjunto de números naturales. De hecho, negrita es simplemente la unión de para todos los conjuntos de números naturales Y . Nótese que la jerarquía en negrita es simplemente la jerarquía estándar de los conjuntos de Borel . ${\displaystyle \mathbf {\Sigma } _{n}^{0}}$ ${\displaystyle \Sigma _{n}^{0,Y}}$

Extensiones y variaciones

Es posible definir la jerarquía aritmética de fórmulas utilizando un lenguaje extendido con un símbolo de función para cada función recursiva primitiva . Esta variación cambia ligeramente la clasificación de , ya que el uso de funciones recursivas primitivas en la aritmética de Peano de primer orden requiere, en general, un cuantificador existencial ilimitado y, por lo tanto, algunos conjuntos que están en según esta definición están estrictamente en según la definición dada al principio de este artículo. La clase y, por lo tanto, todas las clases superiores en la jerarquía no se ven afectadas. ${\displaystyle \Sigma _{0}^{0}=\Pi _{0}^{0}=\Delta _{0}^{0}}$ ${\displaystyle \Sigma _{0}^{0}}$ ${\displaystyle \Sigma _{1}^{0}}$ ${\displaystyle \Sigma _{1}^{0}}$

Se puede definir una variación más semántica de la jerarquía en todas las relaciones finitas de los números naturales; se utiliza la siguiente definición. Toda relación computable se define como . Las clasificaciones y se definen inductivamente con las siguientes reglas. ${\displaystyle \Sigma _{0}^{0}=\Pi _{0}^{0}=\Delta _{0}^{0}}$ ${\displaystyle \Sigma _{n}^{0}}$ ${\displaystyle \Pi _{n}^{0}}$

• Si la relación es entonces la relación se define como ${\displaystyle R(n_{1},\ldots ,n_{l},m_{1},\ldots ,m_{k})\,}$ ${\displaystyle \Sigma _{n}^{0}}$ ${\displaystyle S(n_{1},\ldots ,n_{l})=\forall m_{1}\cdots \forall m_{k}R(n_{1},\ldots ,n_{l},m_{1},\ldots ,m_{k})}$ ${\displaystyle \Pi _{n+1}^{0}}$
• Si la relación es entonces la relación se define como ${\displaystyle R(n_{1},\ldots ,n_{l},m_{1},\ldots ,m_{k})\,}$ ${\displaystyle \Pi _{n}^{0}}$ ${\displaystyle S(n_{1},\ldots ,n_{l})=\exists m_{1}\cdots \exists m_{k}R(n_{1},\ldots ,n_{l},m_{1},\ldots ,m_{k})}$ ${\displaystyle \Sigma _{n+1}^{0}}$

Esta variación cambia ligeramente la clasificación de algunos conjuntos. En particular, , como una clase de conjuntos (definible por las relaciones en la clase), es idéntica a como se definió anteriormente. Puede extenderse para cubrir relaciones finitas en los números naturales, el espacio de Baire y el espacio de Cantor. ${\displaystyle \Sigma _{0}^{0}=\Pi _{0}^{0}=\Delta _{0}^{0}}$ ${\displaystyle \Delta _{1}^{0}}$

Propiedades

Las siguientes propiedades son válidas para la jerarquía aritmética de conjuntos de números naturales y la jerarquía aritmética de subconjuntos del espacio de Cantor o de Baire.

• Las colecciones y están cerradas bajo uniones finitas e intersecciones finitas de sus respectivos elementos. ${\displaystyle \Pi _{n}^{0}}$ ${\displaystyle \Sigma _{n}^{0}}$
• Un conjunto es si y solo si su complemento es . Un conjunto es si y solo si el conjunto es tanto como , en cuyo caso su complemento también será . ${\displaystyle \Sigma _{n}^{0}}$ ${\displaystyle \Pi _{n}^{0}}$ ${\displaystyle \Delta _{n}^{0}}$ ${\displaystyle \Sigma _{n}^{0}}$ ${\displaystyle \Pi _{n}^{0}}$ ${\displaystyle \Delta _{n}^{0}}$
• Las inclusiones y son válidas para todos los . Por lo tanto, la jerarquía no colapsa. Esta es una consecuencia directa del teorema de Post . ${\displaystyle \Pi _{n}^{0}\subsetneq \Pi _{n+1}^{0}}$ ${\displaystyle \Sigma _{n}^{0}\subsetneq \Sigma _{n+1}^{0}}$ ${\displaystyle n}$
• Las inclusiones y se mantienen durante . ${\displaystyle \Delta _{n}^{0}\subsetneq \Pi _{n}^{0}}$ ${\displaystyle \Delta _{n}^{0}\subsetneq \Sigma _{n}^{0}}$ ${\displaystyle \Sigma _{n}^{0}\cup \Pi _{n}^{0}\subsetneq \Delta _{n+1}^{0}}$ ${\displaystyle n\geq 1}$

• Por ejemplo, para una máquina de Turing universal T , el conjunto de pares ( n , m ) tales que T se detiene en n pero no en m , está en (siendo computable con un oráculo para el problema de detención) pero no en . ${\displaystyle \Delta _{2}^{0}}$ ${\displaystyle \Sigma _{1}^{0}\cup \Pi _{1}^{0}}$
• ${\displaystyle \Sigma _{0}^{0}=\Pi _{0}^{0}=\Delta _{0}^{0}=\Sigma _{0}^{0}\cup \Pi _{0}^{0}\subseteq \Delta _{1}^{0}}$La inclusión es estricta según la definición dada en este artículo, pero una identidad con se cumple bajo una de las variaciones de la definición dada anteriormente. ${\displaystyle \Delta _{1}^{0}}$

Relación con las máquinas de Turing

Conjuntos computables

Si S es un conjunto computable de Turing , entonces tanto S como su complemento son enumerables recursivamente (si T es una máquina de Turing que da 1 para las entradas en S y 0 en caso contrario, podemos construir una máquina de Turing que se detenga solo en el primero, y otra que se detenga solo en el segundo).

Por el teorema de Post , tanto S como su complemento están en . Esto significa que S está tanto en como en , y por lo tanto está en . ${\displaystyle \Sigma _{1}^{0}}$ ${\displaystyle \Sigma _{1}^{0}}$ ${\displaystyle \Pi _{1}^{0}}$ ${\displaystyle \Delta _{1}^{0}}$

De manera similar, para cada conjunto S en , tanto S como su complemento están en y son por lo tanto (por el teorema de Post ) recursivamente enumerables por algunas máquinas de Turing T ₁ y T ₂ , respectivamente. Para cada número n , exactamente uno de estos se detiene. Por lo tanto, podemos construir una máquina de Turing T que alterne entre T ₁ y T ₂ , deteniéndose y devolviendo 1 cuando el primero se detiene o deteniéndose y devolviendo 0 cuando el segundo se detiene. Por lo tanto, T se detiene en cada n y devuelve si está en S ; por lo tanto, S es computable. ${\displaystyle \Delta _{1}^{0}}$ ${\displaystyle \Sigma _{1}^{0}}$

Resumen de los principales resultados

Los conjuntos de números naturales computables según el método de Turing son exactamente los conjuntos en el nivel de la jerarquía aritmética. Los conjuntos enumerables recursivamente son exactamente los conjuntos en el nivel . ${\displaystyle \Delta _{1}^{0}}$ ${\displaystyle \Sigma _{1}^{0}}$

Ninguna máquina oráculo es capaz de resolver su propio problema de detención (se aplica una variación de la prueba de Turing). El problema de detención de un oráculo se encuentra, de hecho, en . ${\displaystyle \Delta _{n}^{0,Y}}$ ${\displaystyle \Sigma _{n+1}^{0,Y}}$

El teorema de Post establece una estrecha relación entre la jerarquía aritmética de los conjuntos de números naturales y los grados de Turing . En particular, establece los siguientes hechos para todo n ≥ 1:

• El conjunto (el n -ésimo salto de Turing del conjunto vacío) es completo en muchos-uno en . ${\displaystyle \emptyset ^{(n)}}$ ${\displaystyle \Sigma _{n}^{0}}$
• El conjunto es muchos-uno completo en . ${\displaystyle \mathbb {N} \setminus \emptyset ^{(n)}}$ ${\displaystyle \Pi _{n}^{0}}$
• El conjunto es Turing completo en . ${\displaystyle \emptyset ^{(n-1)}}$ ${\displaystyle \Delta _{n}^{0}}$

La jerarquía polinómica es una versión "viable y limitada en cuanto a recursos" de la jerarquía aritmética en la que se establecen límites de longitud polinómica para los números involucrados (o, de manera equivalente, se establecen límites de tiempo polinómico para las máquinas de Turing involucradas). Proporciona una clasificación más precisa de algunos conjuntos de números naturales que se encuentran en el nivel de la jerarquía aritmética. ${\displaystyle \Delta _{1}^{0}}$

Relación con otras jerarquías

Esta caja:

• vista
• hablar
• editar

Véase también

• Jerarquía analítica
• Jerarquía de Lévy
• Jerarquía (matemáticas)
• Lógica de interpretabilidad
• Jerarquía polinómica

Referencias

1. PG Hinman, Jerarquías teóricas de la recursión (p.89), Perspectivas en lógica, 1978. Springer-Verlag Berlín Heidelberg, ISBN 3-540-07904-1.

• Japaridze, Giorgie (1994), "La lógica de la jerarquía aritmética", Anales de lógica pura y aplicada , 66 (2): 89–112, doi :10.1016/0168-0072(94)90063-9, Zbl  0804.03045.
• Moschovakis, Yiannis N. (1980), Teoría descriptiva de conjuntos , Estudios de lógica y fundamentos de las matemáticas, vol. 100, Holanda Septentrional, ISBN 0-444-70199-0, Zbl0433.03025 ​.
• Nies, André (2009), Computabilidad y aleatoriedad , Oxford Logic Guides, vol. 51, Oxford: Oxford University Press, ISBN 978-0-19-923076-1, Zbl1169.03034 ​.
• Rogers, H. Jr. (1967), Teoría de funciones recursivas y computabilidad efectiva , Maidenhead: McGraw-Hill, Zbl  0183.01401.