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 básicas 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 basándose en la complejidad de las fórmulas que los definen . Cualquier conjunto que recibe una clasificación se llama aritmético . La jerarquía aritmética fue inventada de forma independiente por Kleene (1943) y Mostowski (1946). ^[1]

La jerarquía aritmética es importante en la teoría de la computabilidad , la teoría descriptiva efectiva de conjuntos 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 amplían la jerarquía aritmética para clasificar fórmulas y conjuntos adicionales.

La jerarquía aritmética de las 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 y para números naturales n (incluido 0). Las letras griegas aquí son símbolos claros , lo que indica que las fórmulas no contienen parámetros establecidos. ${\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 asignan las clasificaciones y . ${\displaystyle \phi }$ ${\displaystyle \phi }$ ${\displaystyle \Sigma _{0}^{0}}$ ${\displaystyle \Pi _{0}^{0}}$

Las clasificaciones y se definen inductivamente para todo 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 está , 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 está , 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 equivale a una fórmula que comienza con algunos cuantificadores existenciales y alterna tiempos entre series de cuantificadores existenciales y universales ; mientras que una fórmula equivale a una fórmula que comienza con algunos cuantificadores universales y se alterna de manera análoga. ${\displaystyle \Sigma _{n}^{0}}$ ${\displaystyle n-1}$ ${\displaystyle \Pi _{n}^{0}}$

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 o se le asignarán las clasificaciones y para cada m > n . La única clasificación relevante asignada a una fórmula es, por tanto, la que tiene el menor n ; todas las demás clasificaciones se pueden determinar a partir de él. ${\displaystyle \Sigma _{n}^{0}}$ ${\displaystyle \Pi _{n}^{0}}$ ${\displaystyle \Sigma _{m}^{0}}$ ${\displaystyle \Pi _{m}^{0}}$

Significado de la notación

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

El subíndice en los símbolos e 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 entre los símbolos , y indica el tipo de objetos que se están cuantificando. 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 de 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 tipo 1), el superíndice 2 correspondería a cuantificación sobre funciones que toman un objeto 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 tiene cuantificadores acotados. Estos son exactamente los conjuntos recursivamente enumerables . ${\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 de las máquinas de Turing que calculan funciones totales es . Intuitivamente, un índice cae en este conjunto si y sólo si para cada "hay algo tal que la máquina de Turing con índice se detiene al ingresar después de los pasos". Una prueba completa mostraría que la propiedad mostrada 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}}$
• Cada subconjunto del espacio de Baire o del espacio de Cantor es un conjunto abierto en la topología habitual 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 los conjuntos a veces se les llama efectivamente abiertos . De manera similar, todo conjunto es cerrado y, a veces, los conjuntos se denominan efectivamente cerrados . ${\displaystyle \Sigma _{1}^{0}}$ ${\displaystyle \Sigma _{1}^{0}}$ ${\displaystyle \Pi _{1}^{0}}$ ${\displaystyle \Pi _{1}^{0}}$
• Todo subconjunto aritmético del espacio de Cantor o del espacio de Baire es un conjunto de Borel . La jerarquía de Lightface Borel extiende la jerarquía aritmética para incluir conjuntos de Borel adicionales. Por ejemplo, cada subconjunto del espacio de Cantor o 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úmeros libres, 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 repasando todos los casos uno por uno, lo cual es posible porque todos sus cuantificadores están acotados. El tiempo para esto es polinómico en sus argumentos (por ejemplo, polinomio en for ); por tanto, sus correspondientes problemas de decisión se incluyen en E (como es exponencial en su número de bits). Esto ya no es válido en definiciones alternativas de que permiten el uso de funciones recursivas primitivas , ya que ahora los cuantificadores pueden estar vinculados 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 un cuantificador acotado no agrega nada a la definición: para un recursivo primitivo , es lo mismo que y es lo mismo que ; con la recursividad del curso de valores, cada uno de estos 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}$

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 suma, "×" para multiplicación y "=" para 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 está el numeral en el lenguaje de la aritmética correspondiente a . Un conjunto es definible en aritmética de primer orden si está definido 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 puede 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 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}}$

Tenga en cuenta 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 está necesariamente definido por una fórmula en el sentido de una fórmula que sea a la vez y ; más bien, existen fórmulas tanto 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 en 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 en conjuntos de k - tuplas de números naturales. De hecho, estos están relacionados mediante el uso de una función de emparejamiento .

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 ser , o en Y , denotado respectivamente , y . Para hacerlo, fije un conjunto de números naturales Y y agregue un predicado de pertenencia a Y al lenguaje de la aritmética de Peano. Entonces decimos que X está dentro si está definido por una fórmula en este lenguaje expandido. En otras palabras, X lo es si está definido por una fórmula que permite hacer preguntas sobre la pertenencia a Y. Alternativamente, se pueden ver los conjuntos como aquellos conjuntos que se pueden construir comenzando con conjuntos recursivos en Y y alternativamente tomando 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. De manera equivalente, 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 de pertenencia a Y. De manera equivalente, 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 ordenados bajo . ${\displaystyle \leq _{A}}$

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

El espacio de Cantor , denotado , es el conjunto de todas las secuencias infinitas de 0 y 1; el espacio de Baire , denotado o , es el conjunto de todas las secuencias infinitas de números naturales. Tenga en cuenta que los elementos del espacio de Cantor se pueden identificar con conjuntos de números naturales y elementos del espacio de Baire con funciones desde números naturales hasta 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, naturalmente, se puede considerar que los cuantificadores de conjuntos cuantifican el espacio de Cantor. A un subconjunto del espacio de Cantor se le asigna la clasificación si se puede definir mediante una fórmula. Al conjunto se le asigna la clasificación si es definible mediante 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, de manera equivalente, el conjunto de todos los conjuntos no vacíos de números naturales). Como vemos, está definido por una fórmula y, por 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}}$

Tenga en cuenta 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 son 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 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 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 debajo del mapa que lleva cada función de a a la función característica de su gráfica. A un subconjunto del espacio de Baire se le da la clasificación , o si y sólo 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; entonces la jerarquía aritmética de subconjuntos del espacio de Cantor se puede definir a partir de la jerarquía del espacio de Baire. Esta definición alternativa ofrece 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 encajan con el lenguaje de la aritmética ordinaria de segundo orden.

Tenga en cuenta 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, la negrita es solo la unión de todos los conjuntos de números naturales Y. Tenga en cuenta que la jerarquía en negrita es sólo 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 dentro de esta definición están estrictamente dentro de la definición dada al comienzo de Este artículo. La clase y, por tanto, todas las clases superiores de 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. Cada 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 clase de conjuntos (definible por las relaciones en la clase), es idéntico a como se definió anteriormente este último. Puede ampliarse 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 Baire.

• Las colecciones y están cerradas bajo uniones finitas y intersecciones finitas de sus respectivos elementos. ${\displaystyle \Pi _{n}^{0}}$ ${\displaystyle \Sigma _{n}^{0}}$
• Un conjunto es si y sólo si su complemento es . Un conjunto es si y sólo si el conjunto es a la vez y , en cuyo caso su complemento también lo 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 la espera para todos . Así, 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 aguantar 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 se mantiene 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 recursivamente enumerables (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 sólo en la primera, y otra que se detenga sólo en sobre este último).

Según el teorema de Post , tanto S como su complemento están en . Esto significa que S es tanto in como in y, por tanto, es in . ${\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 por lo tanto (según el teorema de Post ) son recursivamente enumerables por algunas máquinas de Turing T ₁ y T ₂ , respectivamente. Por 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 la primera se detiene o deteniéndose y devolviendo 0 cuando la segunda se detiene. Por tanto, T se detiene en cada n y devuelve si está en S ; entonces S es computable. ${\displaystyle \Delta _{1}^{0}}$ ${\displaystyle \Sigma _{1}^{0}}$

Resumen de resultados principales

Los conjuntos computables de números naturales de Turing son exactamente los conjuntos al nivel de la jerarquía aritmética. Los conjuntos recursivamente enumerables 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). De hecho, el problema de la detención de un oráculo reside en . ${\displaystyle \Delta _{n}^{0,Y}}$ ${\displaystyle \Sigma _{n+1}^{0,Y}}$

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

• El conjunto (el enésimo salto de Turing del conjunto vacío) es muchos uno completo en . ${\displaystyle \emptyset ^{(n)}}$ ${\displaystyle \Sigma _{n}^{0}}$
• El conjunto está completo en muchos uno . ${\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 limitada por recursos" de la jerarquía aritmética en la que se colocan límites de longitud polinomiales en los números involucrados (o, de manera equivalente, se colocan límites de tiempo polinomiales en las máquinas de Turing involucradas). Proporciona una clasificación más detallada 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

Ver también

• Jerarquía analítica
• Jerarquía de Levy
• Jerarquía (matemáticas)
• Lógica de interpretabilidad
• Jerarquía polinomial

Referencias

1. PG Hinman, Jerarquías teóricas de recursión (p.89), Perspectives in Logic, 1978. Springer-Verlag Berlin Heidelberg, ISBN 3-540-07904-1.

• Japaridze, Giorgie (1994), "La lógica de la jerarquía aritmética", Annals of Pure and Applied Logic , 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, Zbl  0433.03025.
• Nies, André (2009), Computabilidad y aleatoriedad , Oxford Logic Guides, vol. 51, Oxford: Oxford University Press, ISBN 978-0-19-923076-1, Zbl  1169.03034.
• Rogers, H. Jr. (1967), Teoría de funciones recursivas y computabilidad efectiva , Maidenhead: McGraw-Hill, Zbl  0183.01401.