En la lógica matemática , la jerarquía aritmética , jerarquía aritmética o jerarquía de Kleene-Mostowski (después matemáticos Stephen Cole Kleene y Andrzej Mostowski ) clasifica ciertos conjuntos basados en la complejidad de las fórmulas que los definen. Cualquier conjunto que reciba una clasificación se llama aritmético .
La jerarquía aritmética es importante en la teoría de la recursividad , la teoría descriptiva de conjuntos efectiva y el estudio de teorías formales como la aritmética de Peano .
El algoritmo de Tarski-Kuratowski proporciona una manera fácil de obtener un límite superior en 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 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 indican y para números naturales n (incluido 0). Las letras griegas aquí son símbolos de cara clara , lo que indica que las fórmulas no contienen parámetros establecidos.
Si una formula es lógicamente equivalente a una fórmula con solo cuantificadores acotados, entonces se le asignan las clasificaciones y .
Las clasificaciones y se definen inductivamente para cada número natural n usando las siguientes reglas:
- Si es lógicamente equivalente a una fórmula de la forma , dónde es , luego se le asigna la clasificación .
- Si es lógicamente equivalente a una fórmula de la forma , dónde es , luego se le asigna la clasificación .
A fórmula es equivalente a una fórmula que comienza con algunos cuantificadores existenciales y se alternatiempos entre series de cuantificadores existenciales y universales ; mientras que un fórmula es equivalente a una fórmula que comienza con algunos cuantificadores universales y se alterna de forma análoga.
Debido a que cada fórmula de primer orden tiene una forma normal prenex , 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 se asigna una fórmula, la clasificación o se le asignarán las clasificaciones y por cada r> n . La única clasificación relevante asignada a una fórmula es, por tanto, la que tiene el mínimo de n ; todas las demás clasificaciones se pueden determinar a partir de él.
La jerarquía aritmética de conjuntos de números naturales.
Un conjunto X de números naturales se define mediante la 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 suma, "×" para 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 ,
dónde es el numeral en el lenguaje de la aritmética correspondiente a . Un conjunto es definible en aritmética de primer orden si está definido por 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, , y , dónde es un número natural, como sigue. Si X es definible por unfórmula, entonces X se le asigna la clasificación. Si X es definible por unfórmula, entonces X se le asigna la clasificación. Si X es ambos y luego se le asigna la clasificación adicional .
Tenga en cuenta que rara vez tiene sentido hablar de fórmulas; el primer cuantificador de una fórmula es existencial o universal. Entonces un el conjunto no está definido por un fórmula; más bien, hay ambos y fórmulas que definen el conjunto.
Se utiliza una definición paralela para definir la jerarquía aritmética de las 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 de números libres 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 para un conjunto X sea recursiva en relación con otro conjunto Y permitiendo que el cálculo definiendo X consultar Y como un oráculo podemos extender esta noción a toda la jerarquía aritmética y definir lo que significa para X a ser, o en Y , denotado respectivamente y . Para hacerlo, corrija un conjunto de enteros Y y agregue un predicado para la pertenencia a Y al lenguaje de la aritmética de Peano. Luego decimos que X está en si está definido por un fórmula en este lenguaje expandido. En otras palabras, X es si está definido por un fórmula permitió hacer preguntas acerca de la pertenencia a Y . Alternativamente, uno puede ver elconjuntos como aquellos conjuntos que se pueden construir comenzando con conjuntos recursivos en Y y alternando uniones e intersecciones de estos conjuntos hasta n veces.
Por ejemplo, sea Y un conjunto de números enteros. Sea X el conjunto de números divisibles por un elemento de Y. Entonces X se define mediante la fórmulaentonces X está en (en realidad está en también ya que podríamos unir ambos cuantificadores por n).
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 entero n . Un conjunto X es aritmético en un conjunto Y , denotado, Si X es definible como una fórmula en el lenguaje de la aritmética de Peano ampliado por un predicado para ser miembro de Y . De manera equivalente, X es aritmética en Y si X está en o para algún número entero n . Sinónimo dees: X es aritméticamente reducible a Y .
La relación es reflexiva y transitiva, y por tanto la relación definido por la regla
es una relación de equivalencia. Las clases de equivalencia de esta relación se denominan grados aritméticos ; están parcialmente ordenados bajo.
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 enteros y los elementos del espacio de Baire con funciones de enteros a enteros.
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 en el espacio de Cantor. A un subconjunto del espacio de Cantor se le asigna la clasificación si es definible por un fórmula. Al conjunto se le asigna la clasificación si es definible por un fórmula. Si el conjunto es a la vez y entonces se le da la clasificación adicional . Por ejemplo, dejaser el conjunto de todas las cadenas binarias infinitas que no son todas 0 (o, de manera equivalente, el conjunto de todos los conjuntos de enteros no vacíos). Como vemos eso está definido por un fórmula y por lo tanto es una colocar.
Tenga en cuenta que aunque tanto los elementos del espacio de Cantor (considerados como conjuntos de números enteros) como los subconjuntos del espacio de Cantor se clasifican en jerarquías aritméticas, estos no son la misma jerarquía. De hecho, la relación entre las dos jerarquías es interesante y no trivial. Por ejemplo, el Los elementos del espacio de Cantor no son (en general) los mismos que los elementos del espacio Cantor para que es un subconjunto del espacio Cantor. Sin embargo, muchos resultados interesantes relacionan las dos jerarquías.
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 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 da la clasificación, , o si y solo si el subconjunto correspondiente del espacio de Cantor tiene la misma clasificación.
- Se da una definición equivalente de la jerarquía analítica en el espacio de Baire definiendo la jerarquía analítica de fórmulas utilizando una versión funcional de la aritmética de segundo orden; entonces la jerarquía analí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 da 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 enteros. De hecho, negrita es solo la unión de para todos los conjuntos de números enteros Y . Tenga en cuenta que la jerarquía en negrita es solo la jerarquía estándar de los conjuntos de Borel .
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 por esta definición están en por la definición dada al comienzo de este artículo. y así todas las clases superiores de la jerarquía no se ven afectadas.
Se puede definir una variación más semántica de la jerarquía en todas las relaciones finitarias 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.
- Si la relación es entonces la relación se define como
- Si la relación es entonces la relación se define como
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 este último. Puede extenderse para cubrir relaciones finitarias sobre los números naturales, el espacio de Baire y el espacio de Cantor.
Significado de la notación
Los siguientes significados se pueden adjuntar a la notación de la jerarquía aritmética en fórmulas.
El subíndice en los simbolos y indica el número de alternancias de bloques de cuantificadores numéricos universales y existenciales que se utilizan en una fórmula. Además, el bloque más externo es existencial en fórmulas y universal en fórmulas.
El superíndice en los simbolos , , y indica el tipo de objetos sobre los que se cuantifica. Los objetos de tipo 0 son números naturales y objetos de tipo son funciones que mapean 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 con 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.
Ejemplos de
- La conjuntos de números son aquellos definibles por una fórmula de la forma dónde solo tiene cuantificadores acotados. Estos son exactamente los conjuntos enumerables de forma recursiva .
- 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 "hay un tal que la máquina de Turing con índice se detiene en la entrada después 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 un fórmula.
- Cada El subconjunto del espacio de Baire o el espacio de Cantor es un conjunto abierto en la topología habitual del espacio. Además, para cualquier conjunto de este tipo hay 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,los conjuntos a veces se denominan efectivamente abiertos . Del mismo modo, cada el set está cerrado y el los conjuntos a veces se denominan efectivamente cerrados .
- 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 amplía la jerarquía aritmética para incluir conjuntos de Borel adicionales. Por ejemplo, cada subconjunto del espacio Cantor o Baire es un conjunto (es decir, un conjunto que es igual a la intersección de innumerables conjuntos abiertos). Además, cada uno de estos conjuntos abiertos esy la lista de números de Gödel de estos conjuntos abiertos tiene una enumeración computable. Si es un fórmula con una variable X de conjunto libre y variables de número libre entonces el colocar es la intersección de la conjuntos de la forma como n se extiende sobre el conjunto de números naturales.
- La Las fórmulas se pueden verificar repasando todos los casos uno por uno, lo cual es posible porque todos sus cuantificadores están acotados. El tiempo para esto es polinomio en sus argumentos (por ejemplo, polinomio en n para); por tanto, sus problemas de decisión correspondientes se incluyen en E (ya que n es exponencial en su número de bits). Esto ya no es válido para 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.
- La fórmulas bajo una definición alternativa, que permite el uso de funciones recursivas primitivas con cuantificadores acotados, corresponden a conjuntos de enteros de la forma para una función recursiva primitiva f . Esto se debe a que permitir un cuantificador acotado no agrega nada a la definición: para una f recursiva primitiva , es lo mismo que , y es lo mismo que ; con la recursividad de curso de valores, cada uno de estos se puede definir mediante una única función de recursión primitiva.
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 cerrados bajo uniones finitas e intersecciones finitas de sus respectivos elementos.
- Un conjunto es si y solo si su complemento es . Un conjunto es si y solo si el conjunto es a la vez y , en cuyo caso su complemento también será .
- Las inclusiones y espera para todos . Por tanto, la jerarquía no se derrumba. Ésta es una consecuencia directa del teorema de Post .
- Las inclusiones , y mantener durante .
- Por ejemplo, para una máquina de Turing universal T, el conjunto de pares (n, m) tal que T se detiene en n pero no en m, está en (siendo computable con un oráculo para el problema de la detención) pero no en ,.
- . La inclusión es estricta por la definición dada en este artículo, pero una identidad conse mantiene bajo una de las variaciones de la definición dada arriba .
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 solo en el primero y otra que se detenga solo en este último).
Según el teorema de Post , tanto S como su complemento están en. Esto significa que S está tanto en y en , y por lo tanto está en .
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 ) recursivamente enumerables por algunas máquinas de Turing T 1 y T 2 , respectivamente. Para cada número n, exactamente uno de estos se detiene. Por lo tanto, podemos construir una máquina de Turing T que alterna entre T 1 y T 2 , deteniéndose y devolviendo 1 cuando el primero se detiene o deteniéndose y devolviendo 0 cuando el último se detiene. Por lo tanto, T se detiene en cada ny devuelve si está en S, por lo que S es calculable.
Resumen de los principales resultados
Los conjuntos computables de Turing de números naturales son exactamente los conjuntos a nivel de la jerarquía aritmética. Los conjuntos recursivamente enumerables son exactamente los conjuntos a nivel.
Ninguna máquina de 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 la detención para un oráculo de hecho se encuentra en .
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 n- ésimo salto de Turing del conjunto vacío) es muchos-uno completo en.
- El conjunto es muchos-uno completo en .
- El conjunto ¿ Turing está completo en.
La jerarquía polinomial es una versión "factible limitada por recursos" de la jerarquía aritmética en la que los límites de longitud polinomial se colocan en los números involucrados (o, de manera equivalente, los límites de tiempo polinomial se colocan en las máquinas de Turing involucradas). Da una clasificación más fina de algunos conjuntos de números naturales que están al nivel de la jerarquía aritmética.
Relación con otras jerarquías
Lightface | Negrita | ||
Σ0 0 = Π0 0 = Δ0 0 (a veces lo mismo que Δ0 1) | Σ0 0= Π0 0= Δ0 0 (si está definido) | ||
Δ0 1= recursivo | Δ0 1= abierto | ||
Σ0 1= recursivamente enumerable | Π0 1 = recursivamente enumerable | Σ0 1= G = abierto | Π0 1= F = cerrado |
Δ0 2 | Δ0 2 | ||
Σ0 2 | Π0 2 | Σ0 2= F σ | Π0 2= G δ |
Δ0 3 | Δ0 3 | ||
Σ0 3 | Π0 3 | Σ0 3= G δσ | Π0 3= F σδ |
⋮ | ⋮ | ||
Σ0 <ω = Π0 <ω = Δ0 <ω = Σ1 0 = Π1 0 = Δ1 0= aritmético | Σ0 <ω= Π0 <ω= Δ0 <ω= Σ1 0= Π1 0= Δ1 0 = aritmética en negrita | ||
⋮ | ⋮ | ||
Δ0 α(α recursivo ) | Δ0 α(α contable ) | ||
Σ0 α | Π0 α | Σ0 α | Π0 α |
⋮ | ⋮ | ||
Σ0 ωCK 1 = Π0 ωCK 1 = Δ0 ωCK 1 = Δ1 1= hiperaritmético | Σ0 ω 1= Π0 ω 1= Δ0 ω 1= Δ1 1= B = Borel | ||
Σ1 1 = analítica de cara clara | Π1 1 = coanalítico de cara clara | Σ1 1= A = analítico | Π1 1= CA = coanalítico |
Δ1 2 | Δ1 2 | ||
Σ1 2 | Π1 2 | Σ1 2 = PCA | Π1 2 = CPCA |
Δ1 3 | Δ1 3 | ||
Σ1 3 | Π1 3 | Σ1 3 = PCPCA | Π1 3 = CPCPCA |
⋮ | ⋮ | ||
Σ1 <ω = Π1 <ω = Δ1 <ω = Σ2 0 = Π2 0 = Δ2 0= analítico | Σ1 <ω= Π1 <ω= Δ1 <ω= Σ2 0= Π2 0= Δ2 0= P = proyectiva | ||
⋮ | ⋮ |
Ver también
- Jerarquía de Lévy
- Jerarquía (matemáticas)
- Lógica de interpretabilidad
- Jerarquía polinomial
Referencias
- 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 de conjuntos descriptivos , Estudios en lógica y fundamentos de las matemáticas, 100 , Holanda del Norte, ISBN 0-444-70199-0, Zbl 0433.03025.
- Nies, André (2009), Computabilidad y aleatoriedad , Oxford Logic Guides, 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.