Hierarquia aritmética

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa

Em Lógica matemática, a hierarquia aritmética, ou hierarquia de Kleene-Mostowski classifica certos conjuntos baseada na complexidade das formulas que o definem. Qualquer conjunto que recebe uma classificação é chamado aritmético.

A hierarquia aritmética é importante em teoria da recursão, teoria descritiva efetiva de conjuntos, e no estudo de teorias formais como a aritmética de Peano.

O algoritmo de Tarski-Kuratowski fornece um caminho simples para obter um limite superior nas classificações atribuídas a uma fórmula e o conjunto que ela define.

A hierarquia hiperaritmética e a hierarquia analítica estendem a hierarquia aritmética para classificar formulas e conjuntos adicionais.

A hierarquia aritmética das fórmulas[editar | editar código-fonte]

A hierarquia aritmética atribui classificações à fórmulas na aritmética de primeira ordem. As classificações são denotadas \Sigma^0_n e \Pi^0_n para números naturais n (incluindo 0). As letras gregas utilizadas indicam que as fórmulas não contêm parâmetros definidos.

Se uma fórmula \phi é logicamente equivalente a uma fórmula com apenas quantificadores limitados então \phi é classificada como \Sigma^0_0 e \Pi^0_0.

As classificações \Sigma^0_n e \Pi^0_n são definidas indutivamente para cada número natural n usando as seguintes regras:

  • Se \phi é logicamente equivalente a uma fórmula na forma \exists n_1 \exists n_2\cdots \exists n_k \psi, onde \psi é \Pi^0_n, então \phi é classificada \Sigma^0_{n+1}.
  • Se \phi é logicamente equivalente a uma fórmula na forma \forall n_1 \forall n_2\cdots \forall n_k  \psi, onde \psi é \Sigma^0_n, então \phi é classificada como \Pi^0_{n+1}.

Além disso, uma fórmula \Sigma^0_n é equivalente a uma fórmula que começa com alguns quantificadores existenciais e alterna n-1 vezes entre séries de quantificadores universais e existenciais; enquanto uma fórmula \Pi^0_n é equivalente a uma fórmula que começa com alguns quantificadores universais e alterna de maneira similar à Sigma.

Por toda fórmula ser equivalente a uma outra na forma normal Prenex, cada fórmula sem quantificadores tem pelo menos uma classificação. Como quantificadores redundantes podem ser adicionados a qualquer fórmula, uma vez que ela está na classificação \Sigma^0_n ou \Pi^0_n, ela também estará nas classificações \Sigma^0_m e \Pi^0_m para todo m maior que n. A mais importante classificação atribuída a uma fórmula passa a ser a que possui pelo menos n, pois é o mínimo suficiente para determinar todas as outras classificações.

A hierarquia aritmética dos conjuntos de números naturais[editar | editar código-fonte]

Um conjunto de números naturais X é definido pela fórmula \phi na linguagem da aritmética de Peano se os elementos de X são exatamente os números que satisfazem \phi. Isto é, para todos os números naturais n,

n \in X \Leftrightarrow \mathbb{N} \models \phi(\underline n),

onde \underline n é o numeral correspondente a n em linguagem de aritmética. Um conjunto é definido em aritmética de primeira ordem se for definido por alguma fórmula na linguagem da aritmética de Peano.

Cada conjunto X de números naturais que é definível em aritmética de primeira ordem é classificado nas formas \Sigma^0_n, \Pi^0_n, e \Delta^0_n, onde n é um número natural. Se X é definível por uma fórmula \Sigma^0_n então X é classificado como \Sigma^0_n. O mesmo vale para \Pi^0_n. Finalmente, se X está em ambos \Sigma^0_n e \Pi^0_n, então X está na classificação adicional \Delta^0_n.

Note que raramente faz sentido falar de fórmulas do tipo \Delta^0_n; o primeiro quantificador de uma fórmula só pode ser existencial ou universal. Logo, um conjunto \Delta^0_n. não é definido por uma fórmula \Delta^0_n; ao invés disso, ambas fórmulas \Sigma^0_n e \Pi^0_n definem o conjunto.

Uma definição paralela é utilizada para definir a hierarquia aritmética em potências Cartesianas finitas de números naturais. Ao invés de fórmulas com uma variável livre, fórmulas com k variáveis livres são utilizadas para definir hieraquia aritmética em conjuntos de k-tuplas de números naturais.

Hierarquias aritméticas relativizadas[editar | editar código-fonte]

Da mesma maneira que podemos definir o que significa para o conjunto X ser recursivo em relação a um conjunto Y, permitindo a computação definindo X consultar Y como um oráculo, podemos estender essa noção para toda hierarquia aritmética e mostrar o que significa para X ser \Sigma^0_n, \Delta^0_n ou \Pi^0_n em Y, denotado respectivamente \Sigma^{0,Y}_n,  \Delta^{0,Y}_n e \Pi^{0,Y}_n. Para fazê-lo, fixe um conjunto Y e adicione um predicado para a adesão em Y para a linguagem da aritmética de Peano. Dizemos então que X está em \Sigma^{0,Y}_n se este é definido por uma fórmula \Sigma^0_n nesta linguagem expandida. Em outras palavras X está em \Sigma^{0,Y}_n se for definido por uma fórmula \Sigma^{0}_n autorizada a perguntar sobre adesão em Y. Alternativamente, conjuntos \Sigma^{0,Y}_n podem ser vistos como aqueles que são construídos começando com conjuntos recursivos em Y e alternadamente projetando e pegando os complementos destes até n vezes.

Por exemplo, sendo Y um conjunto de inteiros. E X o conjunto dos números divisíveis por um elemento em Y. Então X é definido pela fórmula \phi(n)=\exists m \exists t (Y(m)\and m\times t = n) logo X está em \Sigma^{0,Y}_1 (na verdade X está em \Delta^{0,Y}_0 pois podemos limitar ambos quantificadores por n).

Redutibilidade aritmética e graus[editar | editar código-fonte]

Redutibilidade aritmética é uma noção intermediária entre redutibilidade de Turing e redutibilidade hiperaritmética.

Um conjunto é aritmético (ou aritmeticamente definível) se for definido por alguma fórmula na linguagem da aritmética de Peano. O que é equivalente a dizer que X é aritmético se X está em \Sigma^0_n ou \Pi^0_n para algum inteiro n. Um conjunto X é aritmético em Y, denotado X \leq_A Y, se X for definível por alguma fórmula na linguagem da aritmética de Peano estendida por um predicado para adesão em Y. Ou seja, X é aritmético em Y se X está em \Sigma^{0,Y}_n ou \Pi^{0,Y}_n para algum inteiro n. Um sinônimo para X \leq_A Y é: X é aritmeticamente redutível a Y.

A relação X \leq_A Y é reflexiva e transitiva, e portanto, a relação \equiv_A definida pela regra

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

é uma relação de equivalência. As classes de equivalência desta relação são chamadas graus aritméticos; elas são parcialmente ordenadas sob \leq_A.

A hieraquia aritmética de subconjuntos dos espaços de Cantor e Baire[editar | editar código-fonte]

O Espaço de Cantor, denotado 2^{\omega}, é o conjunto de todas as sequências infinitas de 0s e 1s; o espaço de Baire, \omega^{\omega} ou \mathcal{N}, é o conjunto de todas as sequências infinitas de números naturais. note que elementos do espaço de Cantor podem ser identificados com conjuntos de inteiros e elementos do espaço de Baire com funções de inteiros para inteiros.

A axiomatização comum da aritmética de segunda ordem utiliza uma linguagem baseada-em-conjunto no qual os quantificadores definidos podem naturalmente ser vistos como a quantificação ao longo do espaço de Cantor. A um subconjunto do espaço de Cantor é atribuida a classificação \Sigma^0_n se este é definido por uma fórmula \Sigma^0_n. Ao conjunto é atribuida a classificação \Pi^0_n se este é definido por uma fórmula \Pi^0_n. Se o conjunto está em ambas \Sigma^0_n e \Pi^0_n, então lhe é dada a classificação adicional \Delta^0_n. Por exemplo, sendo O\subset 2^{\omega} o conjunto de todas as cadeias binárias infinitas que não são compostas apenas de 0. Como O=\{ X\in 2^\omega | \exists n (X(n)=1) \}, vemos que O é definido por uma fórmula \Sigma^0_1 e por isso está no conjunto \Sigma^0_1.

Note que enquanto ambos os elementos do espaço de Cantor (vistos como conjuntos de inteiros) e subconjuntos do espaço de Cantor são classificados em hierarquias aritméticas, mas não na mesma hierarquia. Na verdade o relacionamento entre as duas hierarquias é interesante e não-trivial. Por exemplo os elementos \Pi^0_n do espaço de Cantor não são (em geral) os mesmos que os elementos X do espaço de Cantor, logo \{X\} é um subconjunto \Pi^0_n do espaço de Cantor. Entretanto, muitos resultados interessantes relacionam as duas hierarquias.

Existem duas maneiras nas quais um subconjunto do espaço de Baire pode ser classificado na hierarquia aritmética.

  • Um subconjunto de espaço de Baire tem um subconjunto correspondente do espaço de Cantor sob o mapa que leva cada função de \omega para \omega para a função característica de seu gráfico. A um subconjunto do espaço de Baire é dada a classificação \Sigma^1_n, \Pi^1_n, ou \Delta^1_n se e somente se o subconjunto correspondente do espaço de Cantor tem a mesma classificação.
  • Um definição equivalente da hierarquia analítica em um espaço de Baire é dada pela definição de hierarquia analítica de fórmulas utilizando uma versão funcional da aritmética de segunda ordem. então a hierarquia analítica em subconjuntos do espaço de Cantor pode ser definida a partir da hierarquia no espaço de Baire. Esta definição alternativa dá exatamente as mesmas classificações, como a primeira definição.

Uma definição paralela é utilizada para definir a hierarquia aritmética em potências cartesianas finitas dos espaços de Baire ou de Cantor, usando fórmulas com diversas variáveis livres. A hierarquia aritmética pode ser definida em qualquer espaço polônes eficaz, a definição é particularmente simples para espaços de Cantor e Baire, porque eles se encaixam na linguagem da aritmética de segunda ordem comum.

Note que também podemos definir a hierarquia aritmética dos subconjuntos dos espaços de Cantor e Baire relativos a um conjunto de números inteiros. Na verdade \bold{\Sigma}^0_n em negrito é apenas a união de \Sigma^{0,Y}_n para todos os conjuntos de números inteiros Y. Note que a hierarquia em negrito é apenas a hierarquia padrão dos conjuntos de Borel.

Extensões e variações[editar | editar código-fonte]

É possível definir a hierarquia aritmética das fórmulas que utilizam uma linguagem estendida com um símbolo para cada função recursiva primitiva. Esta variação altera ligeiramente a classificação de alguns conjuntos.

Uma variação mais semântica da hierarquia pode ser definida em todas as relações finitárias sobre os números naturais; a seguinte definição é usada. Toda relação computável é definida como \Sigma^0_0 e \Pi^0_0. As classificações \Sigma^0_n e \Pi^0_n são definidas indutivamente pelas seguintes regras.

  • Se a relação R(n_1,\ldots,n_l,m_1,\ldots, m_k)\, é \Sigma^0_n então a relação S(n_1,\ldots, n_l) = \forall m_1\cdots \forall m_k R(n_1,\ldots,n_l,m_1,\ldots,m_k) é definida como \Pi^0_{n+1}
  • Se a relação R(n_1,\ldots,n_l,m_1,\ldots, m_k)\, é \Pi^0_n então a relação S(n_1,\ldots,n_l) = \exists m_1\cdots \exists m_k R(n_1,\ldots,n_l,m_1,\ldots,m_k) é definida como \Sigma^0_{n+1}

Esta variação altera ligeiramente a classificação de alguns conjuntos. Ela pode ser estendida para cobrir as relações finitárias sobre os números naturais, espaço de Baire e espaço de Cantor.

Significado da notação[editar | editar código-fonte]

Os seguintes significados podem ser ligados à notação para a hierarquia aritmética em fórmulas.

O índice subescrito n nos símbolos \Sigma^0_n e \Pi^0_n indica o número de alternâncias de blocos de quantificadores de número universais e existenciais que são usados em uma formula. Além disso, o bloco mais externo é existencial em fórmulas \Sigma^0_n e universal em fórmulas \Pi^0_n.

O índice sobrescrito 0 nos símbolos \Sigma^0_n, \Pi^0_n, e \Delta^0_n indica o tipo de objetos que estão sendo quantificados. Objetos do tipo 0 são números naturais e objetos do tipo i + 1 são funções que mapeiam o conjunto de objetos do tipo i para os números naturais. Quantificação sobre tipos de objetos mais elevados, tais como funções de números naturais aos números naturais, são descritas por um sobrescrito superior a 0, tal como na hierarquia analítica. O sobrescrito 0 indica quantificadores sobre números, o sobrescrito 1 indicaria quantificação das funções de números para números (Objetos tipo 1), o expoente 2 corresponderia a quantificação das funções que recebem um objeto tipo 1 e retornam um número, e assim por diante.

Exemplos[editar | editar código-fonte]

  • O conjunto dos números naturais que são índices para máquinas de Turing que computam funções totais é \Pi^0_2. Intuitivamente, um índice e cai neste conjunto se e somente se para todo m "existe um s tal que a máquina de Turing com índice e para na entrada m após s passos". Uma prova completa mostraria que a propriedade exibida entre aspas na frase anterior é definível na linguagem da aritmética de Peano por uma fórmula \Sigma^0_1.
  • Cada subconjunto \Sigma^0_1 do espaço de Baire ou do espaço de Cantor é um conjunto aberto na topologia habitual do espaço. Além disso, para qualquer conjunto, há uma enumeração computável de números de Gödel de conjuntos abertos básicos cuja união é o conjunto original. Por esta razão, conjuntos \Sigma^0_1 são por vezes chamados efetivamente abertos. Da mesma forma, cada conjunto \Pi^0_1 é fechado e os conjuntos \Pi^0_1 são chamados efetivamente fechados.
  • Cada subconjunto aritmético do espaço de Cantor ou espaço de Baire é um conjunto de Borel. A hierarquia leve de Borel estende a hierarquia aritmética para incluir conjuntos de Borel adicionais. Por exemplo, cada subconjunto \Pi^0_2 dos espaços de Cantor ou Baire é um conjunto G_\delta (isto é, um conjunto que é igual a interseção dos muitos conjuntos abertos contáveis). Além disso, cada um desses conjuntos abertos é \Sigma^0_1 e a lista de números de Gödel destes conjuntos abertos tem uma enumeração computável. Se \phi(X,n,m) é uma fórmula \Sigma^0_0 com um conjunto de variáveis livres X e variáveis livres de números n,m então o conjunto \Pi^0_2 \{X \mid \forall n \exists m \phi(X,n,m)\} é a interseção dos conjuntos \Sigma^0_1 da forma \{ X \mid \exists m \phi(X,n,m)\} com n variando ao longo do conjunto dos números naturais.

Propriedades[editar | editar código-fonte]

As propriedades a seguir são válidas para a hierarquia aritmética de conjuntos de números naturais e de subconjuntos dos espaços de Cantor e de Baire.

  • As coleções \Pi^0_n e \Sigma^0_n são fechadas sob uniões finitas e interseções finitas dos seus respectivos elementos.
  • Um conjunto é \Sigma^0_n se e somente se seu complemento é \Pi^0_n. Um conjunto é \Delta^0_n se e somente se este conjunto é \Sigma^0_n e \Pi^0_n, caso em que o seu complemento será também \Delta^0_n.
  • As inclusões \Delta^0_n \subsetneq \Pi^0_n e \Delta^0_n \subsetneq \Sigma^0_n são válidas para n \geq 1.
  • As inclusões \Pi^0_n \subsetneq \Pi^0_{n+1} e \Sigma^0_n \subsetneq \Sigma^0_{n+1} são válidas para todo n e a inclusão \Sigma^0_n \cup \Pi^0_n \subsetneq \Delta^0_{n+1} é válida para n \geq 1. assim, a hierarquia não se quebra.

Relações com máquinas de Turing[editar | editar código-fonte]

Os conjuntos Turing-computáveis de números naturais são exatamente os conjuntos no nível \Delta^0_1 da hierarquia aritmética. Os conjuntos recursivos enumeráveis são exatamente os conjuntos no nível \Sigma^0_1.

Nenhuma máquina oráculo é capaz de resolver seu próprio problema da parada (uma variação da prova de Turing se aplica). O problema da parada para um oráculo \Delta^{0,Y}_n na verdade fica em \Sigma^{0,Y}_{n+1}.

O teorema de Post estabelece uma estreita ligação entre a hierarquia aritmética dos conjuntos de números naturais e graus de Turing. Em particular, estabelece os seguintes fatos para todo n = 1:

A hierarquia polinomial é uma versão viável, de recursos limitados, da hierarquia aritmética em que os limites de comprimento polinomiais são colocados sobre os números envolvidos (ou, equivalentemente, limites de tempo polinomial são colocados nas máquinas de Turing envolvidas). Isto dá uma classificação mais fina de alguns conjuntos de números naturais que são do nível \Delta^0_1 da hierarquia aritmética.

Ver também[editar | editar código-fonte]

Referências[editar | editar código-fonte]

  • Japaridze, Giorgie (1994), "The logic of arithmetical hierarchy", Annals of Pure and Applied Logic 66 (2): 89–112, doi:10.1016/0168-0072(94)90063-9 .
  • Moschovakis, Yiannis N. (1980), Descriptive Set Theory, Studies in Logic and the Foundations of Mathematics, 100, North Holland, ISBN 0-444-70199-0 .
  • Nies, André (2009), Computability and randomness, Oxford Logic Guides, 51, Oxford: Oxford University Press, ISBN 978-0-19-923076-1 .
  • Rogers, H., jr (1967), Theory of recursive functions and effective computability, Maidenhead: McGraw-Hill .