Jerarquía aritmética

En lógica matemática , la jerarquía aritmética , también conocida como jerarquía de Kleene-Mostowski (en honor a los matemáticos Stephen Cole Kleene y Andrzej Mostowski ), clasifica ciertos conjuntos según 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 descriptiva efectiva 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 el 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 asigna clasificaciones a las fórmulas en el lenguaje de la aritmética de primer orden . Las clasificaciones se denotan${\displaystyle \Sigma _{n}^{0}}$y${\displaystyle \Pi _{n}^{0}}$para números naturales n (incluido el 0). Las letras griegas que aparecen aquí son símbolos de tipo lightface , lo que indica que las fórmulas no contienen parámetros fijos.

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

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

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

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

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

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 los símbolos "0" para cero, "S" para la función sucesora, "+" para la suma, " × " 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}}),}$

dónde${\displaystyle {\underline {n}}}$es el numeral en el lenguaje de la aritmética que corresponde a${\displaystyle n}$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.

A cada conjunto X de números naturales que se puede definir en aritmética de primer orden se le asignan clasificaciones de la forma${\displaystyle \Sigma _{n}^{0}}$,${\displaystyle \Pi _{n}^{0}}$, y${\displaystyle \Delta _{n}^{0}}$, dónde${\displaystyle n}$es un número natural, como sigue. Si X se puede definir mediante un${\displaystyle \Sigma _{n}^{0}}$Luego, a X se le asigna la clasificación.${\displaystyle \Sigma _{n}^{0}}$. Si X es definible por un${\displaystyle \Pi _{n}^{0}}$Luego, a X se le asigna la clasificación.${\displaystyle \Pi _{n}^{0}}$. Si X es ambos${\displaystyle \Sigma _{n}^{0}}$y${\displaystyle \Pi _{n}^{0}}$entonces${\displaystyle X}$se le asigna la clasificación adicional${\displaystyle \Delta _{n}^{0}}$.

Rara vez tiene sentido hablar de${\displaystyle \Delta _{n}^{0}}$fórmulas ; el primer cuantificador de una fórmula es existencial o universal. Por lo tanto, una${\displaystyle \Delta _{n}^{0}}$un conjunto no está necesariamente definido por un${\displaystyle \Delta _{n}^{0}}$fórmula en el sentido de una fórmula que es ambas${\displaystyle \Sigma _{n}^{0}}$y${\displaystyle \Pi _{n}^{0}}$; más bien, hay ambos${\displaystyle \Sigma _{n}^{0}}$ y ${\displaystyle \Pi _{n}^{0}}$fórmulas que definen el conjunto. Por ejemplo, el conjunto de los números naturales impares.${\displaystyle n}$es definible por cualquiera de las dos${\displaystyle \forall k(n\neq 2\times k)}$o${\displaystyle \exists k(n=2\times k+1)}$.

Se utiliza una definición paralela para definir la jerarquía aritmética en potencias cartesianas finitas del conjunto de los 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 en conjuntos de k - tuplas de números naturales. Estas están relacionadas mediante el uso de una función de emparejamiento .

Los siguientes significados pueden atribuirse a la notación de la jerarquía aritmética en las fórmulas.

El subíndice${\displaystyle n}$en los símbolos${\displaystyle \Sigma _{n}^{0}}$y${\displaystyle \Pi _{n}^{0}}$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${\displaystyle \Sigma _{n}^{0}}$fórmulas y universales en${\displaystyle \Pi _{n}^{0}}$fórmulas.

El superíndice${\displaystyle 0}$en los símbolos${\displaystyle \Sigma _{n}^{0}}$,${\displaystyle \Pi _{n}^{0}}$, y${\displaystyle \Delta _{n}^{0}}$indica el tipo de objetos que se están cuantificando. Los objetos de tipo 0 son números naturales y los objetos de tipo${\displaystyle i+1}$son funciones que mapean el conjunto de objetos de tipo${\displaystyle i}$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 la cuantificación sobre funciones que toman un objeto de tipo 1 y devuelven un número, y así sucesivamente.

• El${\displaystyle \Sigma _{1}^{0}}$Los conjuntos de números son aquellos que se pueden definir mediante una fórmula de la forma${\displaystyle \exists n_{1}\cdots \exists n_{k}\psi (n_{1},\ldots ,n_{k},m)}$dónde${\displaystyle \psi }$tiene solo cuantificadores acotados. Estos son precisamente los conjuntos recursivamente enumerables .
• El conjunto de números naturales que son índices para las máquinas de Turing que calculan funciones totales es${\displaystyle \Pi _{2}^{0}}$Intuitivamente, un índice${\displaystyle e}$entra en este conjunto si y solo si para cada${\displaystyle m}$"hay un${\displaystyle s}$de tal manera que la máquina de Turing con índice${\displaystyle e}$se detiene en la entrada${\displaystyle m}$después${\displaystyle s}$pasos". Una prueba completa demostraría que la propiedad mostrada entre comillas en la oración anterior es definible en el lenguaje de la aritmética de Peano mediante un${\displaystyle \Sigma _{1}^{0}}$fórmula.
• Cada${\displaystyle \Sigma _{1}^{0}}$Un 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 los números de Gödel de conjuntos abiertos básicos cuya unión es el conjunto original. Por esta razón,${\displaystyle \Sigma _{1}^{0}}$Los conjuntos a veces se denominan efectivamente abiertos . De manera similar, cada${\displaystyle \Pi _{1}^{0}}$El conjunto está cerrado y el${\displaystyle \Pi _{1}^{0}}$A veces se dice que los conjuntos son efectivamente cerrados .
• Todo subconjunto aritmético del espacio de Cantor o del espacio de Baire es un conjunto de Borel . La jerarquía de Borel lightface extiende la jerarquía aritmética para incluir conjuntos de Borel adicionales. Por ejemplo, todo${\displaystyle \Pi _{2}^{0}}$un subconjunto del espacio de Cantor o Baire es un${\displaystyle G_{\delta }}$conjunto , es decir, un conjunto que es igual a la intersección de una cantidad numerable de conjuntos abiertos. Además, cada uno de estos conjuntos abiertos es${\displaystyle \Sigma _{1}^{0}}$y la lista de números de Gödel de estos conjuntos abiertos tiene una enumeración computable.${\displaystyle \phi (X,n,m)}$es un${\displaystyle \Sigma _{0}^{0}}$fórmula con una variable de conjunto libre${\displaystyle X}$y variables numéricas libres${\displaystyle n,m}$entonces el${\displaystyle \Pi _{2}^{0}}$colocar${\displaystyle \{X\mid \forall n\exists m\phi (X,n,m)\}}$es la intersección de la${\displaystyle \Sigma _{1}^{0}}$conjuntos de la forma${\displaystyle \{X\mid \exists m\phi (X,n,m)\}}$como${\displaystyle n}$abarca el conjunto de los números naturales.
• El${\displaystyle \Sigma _{0}^{0}=\Pi _{0}^{0}=\Delta _{0}^{0}}$Las fórmulas se pueden comprobar revisando todos los casos uno por uno, lo cual es posible porque todos sus cuantificadores están acotados. El tiempo para esto es polinomial en sus argumentos (por ejemplo, polinomial en${\displaystyle n}$para${\displaystyle \varphi (n)}$); por lo tanto, sus problemas de decisión correspondientes se incluyen en E (como${\displaystyle n}$es exponencial en su número de bits). Esto ya no se cumple bajo definiciones alternativas de${\displaystyle \Sigma _{0}^{0}=\Pi _{0}^{0}=\Delta _{0}^{0}}$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.
• El${\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${\displaystyle \{n:f(n)=0\}}$para una función recursiva primitiva${\displaystyle f}$. Esto se debe a que permitir un cuantificador acotado no agrega nada a la definición: para una recursión primitiva${\displaystyle f}$,${\displaystyle \forall k<n:f(k)=0}$es lo mismo que ${\displaystyle f(0)+f(1)+...+f(n-1)=0}$, y${\displaystyle \exists k<n:f(k)=0}$es lo mismo que ${\displaystyle f(0)\cdot f(1)\cdot \ldots \cdot f(n-1)=0}$; con la recursión de curso de valores, cada uno de ellos puede definirse mediante una única función recursiva primitiva.

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 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 recursivo .${\displaystyle \Sigma _{n}^{0}}$,${\displaystyle \Delta _{n}^{0}}$o${\displaystyle \Pi _{n}^{0}}$en Y , denotado respectivamente${\displaystyle \Sigma _{n}^{0,Y}}$,${\displaystyle \Delta _{n}^{0,Y}}$y${\displaystyle \Pi _{n}^{0,Y}}$Para ello, fijamos un conjunto de números naturales Y y añadimos un predicado de pertenencia de Y al lenguaje de la aritmética de Peano. Entonces decimos que X está en${\displaystyle \Sigma _{n}^{0,Y}}$si se define por un${\displaystyle \Sigma _{n}^{0}}$fórmula en este lenguaje expandido. En otras palabras, X es${\displaystyle \Sigma _{n}^{0,Y}}$si se define por un${\displaystyle \Sigma _{n}^{0}}$La fórmula permitió hacer preguntas sobre la pertenencia a Y. Alternativamente, se puede ver la${\displaystyle \Sigma _{n}^{0,Y}}$conjuntos como aquellos conjuntos que se pueden construir comenzando con conjuntos recursivamente en Y y tomando alternativamente uniones e intersecciones de estos conjuntos hasta n veces.

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${\displaystyle \phi (n)=\exists m\exists t(Y(m)\land m\times t=n)}$entonces X está en${\displaystyle \Sigma _{1}^{0,Y}}$(en realidad está en${\displaystyle \Delta _{0}^{0,Y}}$Además, ya que podríamos acotar ambos cuantificadores por n ).

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 se define mediante alguna fórmula en el lenguaje de la aritmética de Peano. De forma equivalente, X es aritmético si X es${\displaystyle \Sigma _{n}^{0}}$o${\displaystyle \Pi _{n}^{0}}$para algún número natural n . Un conjunto X es aritmético en un conjunto Y , denotado${\displaystyle X\leq _{A}Y}$, si X es definible como alguna fórmula en el lenguaje de la aritmética de Peano extendida por un predicado para la pertenencia a Y. Equivalentemente, X es aritmético en Y si X está en${\displaystyle \Sigma _{n}^{0,Y}}$o${\displaystyle \Pi _{n}^{0,Y}}$para algún número natural n . Un sinónimo de ${\displaystyle X\leq _{A}Y}$es : X es aritméticamente reducible a Y.

La relación${\displaystyle X\leq _{A}Y}$es reflexivo y transitivo , y por lo tanto la relación${\displaystyle \equiv _{A}}$definido por la regla

${\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 llaman grados aritméticos ; están parcialmente ordenadas según${\displaystyle \leq _{A}}$.

El espacio de Cantor , denotado${\displaystyle 2^{\omega }}$, es el conjunto de todas las secuencias infinitas de 0s y 1s; el espacio de Baire , denotado${\displaystyle \omega ^{\omega }}$o${\displaystyle {\mathcal {N}}}$es el conjunto de todas las sucesiones infinitas de números naturales. Cabe destacar 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.

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

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

Existen dos maneras de clasificar un subconjunto del espacio de Baire en la jerarquía aritmética.

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

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, mediante fórmulas con varias variables libres. La jerarquía aritmética puede definirse en cualquier espacio polaco efectivo ; la definición es particularmente sencilla para el espacio de Cantor y el espacio de Baire, ya que 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 subconjuntos de los espacios de Cantor y Baire en relación con algún conjunto de números naturales. De hecho, en negrita${\displaystyle \mathbf {\Sigma } _{n}^{0}}$es simplemente la unión de${\displaystyle \Sigma _{n}^{0,Y}}$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 conjuntos de Borel .

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${\displaystyle \Sigma _{0}^{0}=\Pi _{0}^{0}=\Delta _{0}^{0}}$, ya que el uso de funciones recursivas primitivas en la aritmética de Peano de primer orden requiere, en general, un cuantificador existencial no acotado y, por lo tanto, algunos conjuntos que están en${\displaystyle \Sigma _{0}^{0}}$por esta definición están estrictamente en${\displaystyle \Sigma _{1}^{0}}$por la definición dada al principio de este artículo. La clase${\displaystyle \Sigma _{1}^{0}}$y, por lo tanto, todas las clases superiores en la jerarquía permanecen inalteradas.

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

• Si la relación${\displaystyle R(n_{1},\ldots ,n_{l},m_{1},\ldots ,m_{k})\,}$es${\displaystyle \Sigma _{n}^{0}}$entonces la relación${\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})}$se define como${\displaystyle \Pi _{n+1}^{0}}$
• Si la relación${\displaystyle R(n_{1},\ldots ,n_{l},m_{1},\ldots ,m_{k})\,}$es${\displaystyle \Pi _{n}^{0}}$entonces la relación${\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})}$se define como${\displaystyle \Sigma _{n+1}^{0}}$

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

Las siguientes propiedades se cumplen 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${\displaystyle \Pi _{n}^{0}}$y${\displaystyle \Sigma _{n}^{0}}$son cerrados bajo uniones finitas e intersecciones finitas de sus respectivos elementos.
• Un conjunto es${\displaystyle \Sigma _{n}^{0}}$si y solo si su complemento es${\displaystyle \Pi _{n}^{0}}$. Un conjunto es${\displaystyle \Delta _{n}^{0}}$si y solo si el conjunto es ambos${\displaystyle \Sigma _{n}^{0}}$y${\displaystyle \Pi _{n}^{0}}$, en cuyo caso su complemento también será${\displaystyle \Delta _{n}^{0}}$.
• Las inclusiones${\displaystyle \Pi _{n}^{0}\subsetneq \Pi _{n+1}^{0}}$y${\displaystyle \Sigma _{n}^{0}\subsetneq \Sigma _{n+1}^{0}}$mantener para todos${\displaystyle n}$Por lo tanto, la jerarquía no se derrumba. Esto es una consecuencia directa del teorema de Post .
• Las inclusiones${\displaystyle \Delta _{n}^{0}\subsetneq \Pi _{n}^{0}}$,${\displaystyle \Delta _{n}^{0}\subsetneq \Sigma _{n}^{0}}$y${\displaystyle \Sigma _{n}^{0}\cup \Pi _{n}^{0}\subsetneq \Delta _{n+1}^{0}}$esperar por${\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${\displaystyle \Delta _{2}^{0}}$(siendo computable con un oráculo al problema de la parada) pero no en${\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${\displaystyle \Delta _{1}^{0}}$se ajusta a una de las variantes de la definición dada anteriormente .

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