Hierarquia aritmética

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

A hierarquia aritmética atribui classificações à fórmulas na aritmética de primeira ordem. As classificações são denotadas ${\displaystyle \Sigma _{n}^{0}}$ e ${\displaystyle \Pi _{n}^{0}}$ 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 ${\displaystyle \phi }$ é logicamente equivalente a uma fórmula com apenas quantificadores limitados então ${\displaystyle \phi }$ é classificada como ${\displaystyle \Sigma _{0}^{0}}$ e ${\displaystyle \Pi _{0}^{0}}$.

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

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

Além disso, uma fórmula ${\displaystyle \Sigma _{n}^{0}}$ é 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 ${\displaystyle \Pi _{n}^{0}}$ é 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 ${\displaystyle \Sigma _{n}^{0}}$ ou ${\displaystyle \Pi _{n}^{0}}$, ela também estará nas classificações ${\displaystyle \Sigma _{m}^{0}}$ e ${\displaystyle \Pi _{m}^{0}}$ 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

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

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

onde ${\displaystyle {\underline {n}}}$ é o numeral correspondente a ${\displaystyle 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 ${\displaystyle \Sigma _{n}^{0}}$, ${\displaystyle \Pi _{n}^{0}}$, e ${\displaystyle \Delta _{n}^{0}}$, onde ${\displaystyle n}$ é um número natural. Se X é definível por uma fórmula ${\displaystyle \Sigma _{n}^{0}}$ então X é classificado como ${\displaystyle \Sigma _{n}^{0}}$. O mesmo vale para ${\displaystyle \Pi _{n}^{0}}$. Finalmente, se X está em ambos ${\displaystyle \Sigma _{n}^{0}}$ e ${\displaystyle \Pi _{n}^{0}}$, então X está na classificação adicional ${\displaystyle \Delta _{n}^{0}}$.

Note que raramente faz sentido falar de fórmulas do tipo ${\displaystyle \Delta _{n}^{0}}$; o primeiro quantificador de uma fórmula só pode ser existencial ou universal. Logo, um conjunto ${\displaystyle \Delta _{n}^{0}}$. não é definido por uma fórmula ${\displaystyle \Delta _{n}^{0}}$; ao invés disso, ambas fórmulas ${\displaystyle \Sigma _{n}^{0}}$ e ${\displaystyle \Pi _{n}^{0}}$ 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

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 ${\displaystyle \Sigma _{n}^{0}}$, ${\displaystyle \Delta _{n}^{0}}$ ou ${\displaystyle \Pi _{n}^{0}}$ em Y, denotado respectivamente ${\displaystyle \Sigma _{n}^{0,Y}}$, ${\displaystyle \Delta _{n}^{0,Y}}$ e ${\displaystyle \Pi _{n}^{0,Y}}$. 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 ${\displaystyle \Sigma _{n}^{0,Y}}$ se este é definido por uma fórmula ${\displaystyle \Sigma _{n}^{0}}$ nesta linguagem expandida. Em outras palavras X está em ${\displaystyle \Sigma _{n}^{0,Y}}$ se for definido por uma fórmula ${\displaystyle \Sigma _{n}^{0}}$ autorizada a perguntar sobre adesão em Y. Alternativamente, conjuntos ${\displaystyle \Sigma _{n}^{0,Y}}$ 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 ${\displaystyle \phi (n)=\exists m\exists t(Y(m)\land m\times t=n)}$ logo X está em ${\displaystyle \Sigma _{1}^{0,Y}}$ (na verdade X está em ${\displaystyle \Delta _{0}^{0,Y}}$ pois podemos limitar ambos quantificadores por n).

Redutibilidade aritmética e graus

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 ${\displaystyle \Sigma _{n}^{0}}$ ou ${\displaystyle \Pi _{n}^{0}}$ para algum inteiro n. Um conjunto X é aritmético em Y, denotado ${\displaystyle 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 ${\displaystyle \Sigma _{n}^{0,Y}}$ ou ${\displaystyle \Pi _{n}^{0,Y}}$ para algum inteiro n. Um sinônimo para ${\displaystyle X\leq _{A}Y}$ é: X é aritmeticamente redutível a Y.

A relação ${\displaystyle X\leq _{A}Y}$ é reflexiva e transitiva, e portanto, a relação ${\displaystyle \equiv _{A}}$ definida pela regra

${\displaystyle X\equiv _{A}Y\Leftrightarrow X\leq _{A}Y\land 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 ${\displaystyle \leq _{A}}$.

A hieraquia aritmética de subconjuntos dos espaços de Cantor e Baire

O Espaço de Cantor, denotado ${\displaystyle 2^{\omega }}$, é o conjunto de todas as sequências infinitas de 0s e 1s; o espaço de Baire, ${\displaystyle \omega ^{\omega }}$ ou ${\displaystyle {\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 ${\displaystyle \Sigma _{n}^{0}}$ se este é definido por uma fórmula ${\displaystyle \Sigma _{n}^{0}}$. Ao conjunto é atribuida a classificação ${\displaystyle \Pi _{n}^{0}}$ se este é definido por uma fórmula ${\displaystyle \Pi _{n}^{0}}$. Se o conjunto está em ambas ${\displaystyle \Sigma _{n}^{0}}$ e ${\displaystyle \Pi _{n}^{0}}$, então lhe é dada a classificação adicional ${\displaystyle \Delta _{n}^{0}}$. Por exemplo, sendo ${\displaystyle O\subset 2^{\omega }}$ o conjunto de todas as cadeias binárias infinitas que não são compostas apenas de 0. Como ${\displaystyle O=\{X\in 2^{\omega }|\exists n(X(n)=1)\}}$, vemos que ${\displaystyle O}$ é definido por uma fórmula ${\displaystyle \Sigma _{1}^{0}}$ e por isso está no conjunto ${\displaystyle \Sigma _{1}^{0}}$.

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 ${\displaystyle \Pi _{n}^{0}}$ do espaço de Cantor não são (em geral) os mesmos que os elementos X do espaço de Cantor, logo ${\displaystyle \{X\}}$ é um subconjunto ${\displaystyle \Pi _{n}^{0}}$ 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 ${\displaystyle \omega }$ para ${\displaystyle \omega }$ para a função característica de seu gráfico. A um subconjunto do espaço de Baire é dada a classificação ${\displaystyle \Sigma _{n}^{1}}$, ${\displaystyle \Pi _{n}^{1}}$, ou ${\displaystyle \Delta _{n}^{1}}$ 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 ${\displaystyle \mathbf {\Sigma } _{n}^{0}}$ em negrito é apenas a união de ${\displaystyle \Sigma _{n}^{0,Y}}$ 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

É 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 ${\displaystyle \Sigma _{0}^{0}}$ e ${\displaystyle \Pi _{0}^{0}}$. As classificações ${\displaystyle \Sigma _{n}^{0}}$ e ${\displaystyle \Pi _{n}^{0}}$ são definidas indutivamente pelas seguintes regras.

• Se a relação ${\displaystyle R(n_{1},\ldots ,n_{l},m_{1},\ldots ,m_{k})\,}$ é ${\displaystyle \Sigma _{n}^{0}}$ então a relação ${\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})}$ é definida como ${\displaystyle \Pi _{n+1}^{0}}$
• Se a relação ${\displaystyle R(n_{1},\ldots ,n_{l},m_{1},\ldots ,m_{k})\,}$ é ${\displaystyle \Pi _{n}^{0}}$ então a relação ${\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})}$ é definida como ${\displaystyle \Sigma _{n+1}^{0}}$

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

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

O índice subescrito ${\displaystyle n}$ nos símbolos ${\displaystyle \Sigma _{n}^{0}}$ e ${\displaystyle \Pi _{n}^{0}}$ 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 ${\displaystyle \Sigma _{n}^{0}}$ e universal em fórmulas ${\displaystyle \Pi _{n}^{0}}$.

O índice sobrescrito ${\displaystyle 0}$ nos símbolos ${\displaystyle \Sigma _{n}^{0}}$, ${\displaystyle \Pi _{n}^{0}}$, e ${\displaystyle \Delta _{n}^{0}}$ indica o tipo de objetos que estão sendo quantificados. Objetos do tipo 0 são números naturais e objetos do tipo ${\displaystyle i+1}$ são funções que mapeiam o conjunto de objetos do tipo ${\displaystyle 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

• Os conjuntos ${\displaystyle \Sigma _{1}^{0}}$ de números são aqueles definíveis por uma fórmula na forma ${\displaystyle \exists n_{1}\cdots \exists n_{k}\psi (n_{1},\ldots ,n_{k},m)}$ onde ${\displaystyle \psi }$ tem apenas quantificadores limitados. Estes são exatamente os conjuntos recursivamente enumeráveis.

• O conjunto dos números naturais que são índices para máquinas de Turing que computam funções totais é ${\displaystyle \Pi _{2}^{0}}$. Intuitivamente, um índice ${\displaystyle e}$ cai neste conjunto se e somente se para todo ${\displaystyle m}$ "existe um ${\displaystyle s}$ tal que a máquina de Turing com índice ${\displaystyle e}$ para na entrada ${\displaystyle m}$ após ${\displaystyle 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 ${\displaystyle \Sigma _{1}^{0}}$.

• Cada subconjunto ${\displaystyle \Sigma _{1}^{0}}$ 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 ${\displaystyle \Sigma _{1}^{0}}$ são por vezes chamados efetivamente abertos. Da mesma forma, cada conjunto ${\displaystyle \Pi _{1}^{0}}$ é fechado e os conjuntos ${\displaystyle \Pi _{1}^{0}}$ 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 ${\displaystyle \Pi _{2}^{0}}$ dos espaços de Cantor ou Baire é um conjunto ${\displaystyle G_{\delta }}$ (isto é, um conjunto que é igual a interseção dos muitos conjuntos abertos contáveis). Além disso, cada um desses conjuntos abertos é ${\displaystyle \Sigma _{1}^{0}}$ e a lista de números de Gödel destes conjuntos abertos tem uma enumeração computável. Se ${\displaystyle \phi (X,n,m)}$ é uma fórmula ${\displaystyle \Sigma _{0}^{0}}$ com um conjunto de variáveis livres X e variáveis livres de números ${\displaystyle n,m}$ então o conjunto ${\displaystyle \Pi _{2}^{0}}$ ${\displaystyle \{X\mid \forall n\exists m\phi (X,n,m)\}}$ é a interseção dos conjuntos ${\displaystyle \Sigma _{1}^{0}}$ da forma ${\displaystyle \{X\mid \exists m\phi (X,n,m)\}}$ com n variando ao longo do conjunto dos números naturais.

Propriedades

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

Relações com máquinas de Turing

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

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 ${\displaystyle \Delta _{n}^{0,Y}}$ na verdade fica em ${\displaystyle \Sigma _{n+1}^{0,Y}}$.

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:

• O conjunto ${\displaystyle \emptyset ^{(n)}}$ (o n-ésimo salto de Turing do conjunto vazio) é um mapeamento completo em ${\displaystyle \Sigma _{n}^{0}}$.
• O conjunto ${\displaystyle \mathbb {N} \setminus \emptyset ^{(n)}}$ é um mapeamento completo em ${\displaystyle \Pi _{n}^{0}}$.
• O conjunto ${\displaystyle \emptyset ^{(n-1)}}$ é Turing completo em ${\displaystyle \Delta _{n}^{0}}$.

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 ${\displaystyle \Delta _{1}^{0}}$ da hierarquia aritmética.

Ver também

• Lógica da Interpretabilidade (em inglês)
• Hierarquia (matemática) (em inglês)

Bibliografia

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