Jerarquía aritmética

Jerarquía aritmética

En lógica matemática, la jerarquía aritmética, o jerarquía de Kleene clasifica ciertos conjuntos basándose en la complejidad de las fórmulas que los definen. Todo conjunto que recibe una clasificación es llamado aritmético.

La jerarquía aritmética es importante en la teoría de recursión, teoría de conjunto descriptivos eficientes, y el estudio de teorías formales tales como aritmética de Peano.

El algoritmo de Tarski-Kuratowski da una forma fácil de obtener un límite superior sobre las clasificaciones que se asignan a una fórmula y al conjunto que la misma define.

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

Contenido

Jerarquía aritmética de fórmulas

La jerarquía aritmética asigna clasificaciones a las fórmulas en el lenguaje de axiomas de Peano (aritmética de primer orden). Las clasificaciones son identificadas como \Sigma^0_n y \Pi^0_n para números naturales n. Las letras griegas son aquí símbolos sin resaltar, que indica que las fórmulas no contienen parámetros de conjunto.

Si una fórmula ϕ es lógicamente equivalente a una fórmula que posee solo cuantificadores acotados entonces ϕ se asigna a las clasificaciones \Sigma^0_0 y \Pi^0_0.

Las clasificaciones \Sigma^0_n y \Pi^0_n se definen en forma inductiva para todo número natural n utilizando las siguientes reglas:

  • Si ϕ es lógicamente equivalente a una fórmula del tipo \exists n_1 \cdots \exists n_k \psi, donde ψ es \Pi^0_n, entonces a ϕ se le asigna la clasificación \Sigma^0_{n+1}.
  • Si ϕ es lógicamente equivalente a una fórmula del tipo \forall n_l \cdots \forall n_k \psi, donde ψ es \Sigma^0_n, entonces a ϕ se le asigna la clasificación \Pi^0_{n+1}.

Dado que cada fórmula es equivalente a una fórmula en forma normal prenex, a cada fórmula que no posee cuantificadores de grupo se le asigna por lo menos una clasificación. Como es posible agregar cuantificadores irrelevantes a toda fórmula, una vez que a una fórmula se le asigna una clasificación \Sigma^0_n o \Pi^0_n se le asignarán las clasificaciones \Sigma^0_m y \Pi^0_m para todo m mayor que n. La clasificación más importante asignada a una fórmula es por lo tanto aquella con menor n, porque a partir de ello se determinan todas las otras clasificaciones.

Jerarquía aritmética de conjuntos de números naturales

Sea un conjunto X definido por la fórmula φ(n) en el lenguaje de aritmética de Peano si n \in X \leftrightarrow \mathbb{N} \models \phi(n). Lo que significa que los elementos de X son exactamente los números que satisfacen φ. Un conjunto es definible mediante aritmética de primer orden si el mismo es definido por alguna fórmula en el lenguaje de la aritmética de Peano.

A cada conjunto X de números naturales que es definible mediante aritmética de primer orden se les asignan clasificaciones del tipo \Sigma^0_n, \Pi^0_n, y \Delta^0_n, donde n es un número natural, según se indica a continuación. Si X es definible por una fórmula \Sigma^0_n entonces a X se le asigna la clasificación \Sigma^0_n. Si X es definible por una fórmula \Pi^0_n entonces a X se le asigna la clasificación \Pi^0_n. Si X es \Sigma^0_n y \Pi^0_n entonces a X se le asigna la clasificación adicional \Delta^0_n.

Notar que casi no tiene sentido referirse a fórmulas del tipo \Delta^0_n; el primer cuantificador de una fórmula es o bien existencial o universal. Por lo tanto un conjunto \Delta^0_n no se encuentra definido por una fórmula del tipo \Delta^0_n; más bien, son las fórmulas \Sigma^0_n y \Pi^0_n las que definen el conjunto.

Se utiliza una definición paralela para definir la jerarquía aritmética en potencias finitas cartesianas de números naturales. En vez de fórmulas con una variable libre, se utilizan fórmulas con k variables libres para definir la jerarquía aritmética sobre conjuntos de k-tuplos de números naturales.

Jerarquías aritméticas relativizadas

De la misma manera como se puede definir que es lo que significa que un conjunto X sea recursivo con relación a otro conjunto Y permitiendo que el cálculo que define a X consulte a Y como si fuera un oráculo, podemos extender este concepto a toda la jerarquía aritmética y definir lo que significa que X sea \Sigma^0_n, \Delta^0_n o \Pi^0_n en Y, lo que se indica respectivamente como \Sigma^{0,Y}_n \Delta^{0,Y}_n y \Pi^{0,Y}_n. Para hacer esto fijamos un conjunto de enteros Y y sumamos un predicado de pertenencia en Y al lenguaje de la aritmética de Peano. Luego afirmamos que X se encuentra en \Sigma^{0,Y}_n si está definido por una fórmula \Sigma^0_n en este lenguaje expandido. Es decir, X es \Sigma^{0,Y}_n si se encuentra definido por una fórmula \Sigma^{0}_n que está habilitada a formular preguntas sobre pertenencia en Y. Alternativamente, se pueden interpretar los conjuntos \Sigma^{0,Y}_n como aquellos conjuntos que pueden ser construidos comenzando a partir de conjuntos recursivos en Y y alternativamente proyectando y tomando complementos de estos conjuntos hasta n veces.

Por ejemplo sea Y un conjunto de enteros. Y sea X el conjunto de números enteros divisibles por un elemento de Y. Entonces X queda definida por la fórmula \phi(n)=\exists m \exists t (Y(m)\and m\times t = n) por lo que X se encuentra en \Sigma^{0,Y}_1 (en realidad se encuentra también en \Delta^{0,Y}_0 dado que podemos acotar ambos cuantificadores con n).

Reducibilidad y grados de la aritmética

La reducibilidad aritmética es un concepto intermedio entre la reducibilidad de Turing y la reducibilidad hiperaritmética. Un conjunto es aritmético (o definible aritméticamente) si es definido por alguna fórmula en el lenguaje de aritmética de Peano. En forma equivalente se dice que X es aritmético si X es \Sigma^0_n o \Pi^0_n para algún entero n. Un conjunto X es aritmético en un conjunto Y, lo que se expresa como X \leq_A Y, si X es definible por alguna fórmula en el lenguaje de aritmética de Peano extendido por un predicado de pertenencia en Y. En forma equivalente, X es aritmético en Y si X se encuentra en \Sigma^{0,Y}_n o \Pi^{0,Y}_n para algún entero n. Un sinónimo de X \leq_A Yes: X es aritméticamente reducible a Y

La relación X \leq_A Y es reflexiva y transitiva, y por lo tanto la relación \equiv_A definida por la regla

X \equiv_A Y \Leftrightarrow X \leq_A Y \and Y \leq_A X

es una relación de equivalencia. Las clases de equivalencia de esta relación son llamadas los grados aritméticos; los mismos se encuentran parcialmente ordenados en \leq_A.

La jerarquía aritmética de los subconjuntos de espacios de Cantor y Baire

El espacio de Cantor, expresado por 2ω, es el conjunto de todas las infinitas sucesiones de 0s y 1s; el espacio de Baire, expresado por ωω or \mathcal{N}, es el conjunto de todas las infinitas sucesiones de números naturales. Notar que elementos del espacio de Cantor pueden ser identificados con conjuntos de enteros y elementos del espacio de Baire con funciones de enteros en enteros.

La axiomatización ordinaria de aritmética de segundo orden utiliza un lenguaje basado en conjuntos en el cual los cuantificadores de conjunto pueden ser interpretados como cuantificando sobre el espacio de Cantor. A un subconjunto del espacio de Cantor se le asigna la clasificación \Sigma^0_n si es definible por una fórmula del tipo \Sigma^0_n. Al conjunto se le asigna la clasificación \Pi^0_n si es definible por una fórmula del tipo \Pi^0_n. Si el conjunto satisface simultáneamente \Sigma^0_n y \Pi^0_n entonces se le da la clasificación adicional \Delta^0_n. Por ejemplo sea O\subset 2^{\omega} el conjunto de todas las cadenas binarias que no son todos 0 (o en forma equivalente el conjunto de todos los conjuntos de enteros no vacíos). Como O=\{ X\in 2^\omega | \exists n (X(n)=1) \} se observa que O es definido por una fórmula \Sigma^0_1 y por lo tanto es un conjunto \Sigma^0_1.

Es de destacar que si bien ambos elementos del espacio de Cantor (que son conjuntos de enteros) y subconjuntos del espacio de Cantor son clasificados en jerarquías aritméticas, estas no poseen la misma jerarquía. De hecho las relaciones entre estas dos jerarquías son interesantes y no triviales. Por ejemplo los elementos \Pi^0_n del espacio de Cantor en general no son los mismos elementos X del espacio de Cantor, de forma tal que {X} es un subconjunto \Pi^0_n del espacio de Cantor. Sin embargo, numerosos resultados interesantes relacionan estas dos jerarquías.

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

  • Un subconjunto del espacio de Baire tiene un subconjunto correspondiente del espacio de Cantor según el mapa que va desde cada función de ω a ω a la función característica de su grafo. A un subconjunto del espacio de Baire se le da la clasificación \Sigma^1_n, \Pi^1_n, o \Delta^1_n si y solo si el correspondiente subconjunto del espacio de Cantor posee la misma clasificación.
  • Una definición equivalente de la jerarquía analítica en un espacio de Baire es si se define la jerarquía analítica de las fórmulas usando una versión funcional de aritmética de segundo orden; entonces la jerarquía analítica en subconjuntos del espacio de Cantor puede ser definida a partir de la jerarquía en el espacio de Baire. Esta definición alternativa arroja exactamente las mismas clasificaciones que la primera definición.

Una definición similar se utiliza para definir la jerarquía aritmética en potencias cartesianas finitas del espacio de Baire o espacio de Cantor, utilizando fórmulas con varias variables libres. La jerarquía aritmética puede ser definida en todo espacio polaco efectivo; la definición es particularmente simple para espacios de Cantor y de Baire porque ellos se ajustan al lenguaje de la ordinario de la aritmética de segundo orden.

Notar que también podemos definir la jerarquía aritmética de subconjuntos de espacios de Cantor y Baire en forma relativa a algunos conjuntos de enteros. De hecho \bold{\Sigma}^0_n en letras negritas es la unión de \Sigma^{0,Y}_n para todos los conjuntos de enteros Y. Notar que la jeraquía en negritas es la jerarquía estandard de los conjuntos de Borel.

Véase también

Referencias

  • G.Japaridze, "The logic of the arithmetical hierarchy", Annals of Pure and Applied Logic 66 (1994), pp.89-112.
  • Moschovakis, Yiannis N. (1980). Descriptive Set Theory. North Holland. ISBN 0-444-70199-0. 
  • Rogers, H. (1967). Theory of recursive functions and effective computability. McGraw-Hill. 

Wikimedia foundation. 2010.

Игры ⚽ Нужно сделать НИР?

Mira otros diccionarios:

  • Jerarquía analítica — En lógica matemática y teoría descriptiva de conjuntos, la jerarquía analítica es un análogo de alto nivel de la jerarquía aritmética. Por lo tanto constituye la clasificación de los conjuntos mediante las fórmulas que los definen. Contenido 1 La …   Wikipedia Español

  • Décimo problema de Hilbert — Saltar a navegación, búsqueda El décimo problema de Hilbert es uno de los veintitrés que David Hilbert propuso al término del siglo XIX. Su enunciado original es: Dada una ecuación diofántica con cualquier número de incógnitas y con coeficientes… …   Wikipedia Español

  • Máquina oracle — Este artículo o sección necesita referencias que aparezcan en una publicación acreditada, como revistas especializadas, monografías, prensa diaria o páginas de Internet fidedignas. Puedes añadirlas así o avisar …   Wikipedia Español

  • Visitor (patrón de diseño) — Visitor: diagrama de clases UML. En programación orientada a objetos, el patrón visitor es una forma de separar el algoritmo de la estructura de un objeto. La idea básica es que se tiene un conjunto de clases elemento que conforman la estructura… …   Wikipedia Español

  • Ciencia — La ciencia (del latín scientia conocimiento ) es el conjunto de conocimientos sistemáticamente estructurados, y susceptibles de ser articulados unos con otros. El árbol de la ciencia. Interpretación bíblica Contenido …   Wikipedia Español

  • Notación polaca — Notación polaca. La notación polaca, también conocida como notación de prefijo o notación prefija, es una forma de notación para la lógica, la aritmética, y el álgebra. Su característica distintiva es que coloca los operadores a la izquierda de… …   Wikipedia Español

  • Unidad de selección — Una unidad de selección (también llamada objeto de selección o individuo evolutivo) es una entidad biológica dentro de la jerarquía de la organización biológica (genes, células, organismos, grupos, especies) que está sujeta a selección natural.… …   Wikipedia Español

  • Edad Media — Santa Sofía de Constantinopla (532 537). Los cuatro minaretes son una adición correspondiente a su transformación en mezquita, a raíz de la …   Wikipedia Español

  • Joseph Smith (hijo) — Joseph Smith, Jr. Nacimiento …   Wikipedia Español

  • Lenguaje de programación Java — Saltar a navegación, búsqueda Java Paradigma: Orientado a objetos Apareció en: 1991 Diseñado por: Sun Microsystems Tipo de dato: Fuerte, Estático Implementacion …   Wikipedia Español

Compartir el artículo y extractos

Link directo
… Do a right-click on the link above
and select “Copy Link”