Teoria hiperaritmética

Na Teoria da Computabilidade, a Teoria hiperaritmética é uma generalização da Computabilidade de Turing. Possui ligações estreitas com definibilidade na aritmética de segunda ordem e com sistemas fracos da teoria dos conjuntos, como a Teoria dos Conjuntos Kripke-Platek.

Conjuntos hiperaritméticos

O foco central da Teoria hiperaritmética é o conjunto de número naturais conhecidos como Conjuntos hiperaritméticos. Existem três maneiras equivalentes de definir essa classe de conjuntos; o estudo do relacionamento entre essas diferentes definições é uma motivação para o estudo da Teoria hiperaritmética.

Conjunto hiperaritmético e definibilidade

A primeira definição dos conjuntos hiperaritméticos usa a hierarquia analítica. Um conjunto de números naturais é classificado a nível $\Sigma _{1}^{1}$dessa hierarquia se ela é definível por uma fórmula aritmética de segunda ordem, com apenas quantificadores existenciais sobre conjuntos e nenhum outro quantificador sobre conjuntos. Um conjunto é classificado a nível $\Pi _{1}^{1}$ da hierarquia analítica se é definível por uma fórmula aritmética de segunda ordem, com apenas quantificadores universais sobre conjuntos e nenhum outro. Um conjunto é $\Delta _{1}^{1}$ se ele é $\Sigma _{1}^{1}$ e $\Pi _{1}^{1}$. Os conjuntos hiperaritméticos são exatamente os conjuntos $\Delta _{1}^{1}$.

Conjuntos hiperaritméticos e saltos de Turing Iterados: a hierarquia hiperaritmética

A definição de conjuntos hiperaritméticos como $\Delta _{1}^{1}$ não depende diretamente dos resultados de computabilidade. Uma segunda definição equivalente mostra que os conjuntos hiperaritméticos podem ser definidos usando saltos de Turing iterados infinitamente. Essa segunda definição também mostra que os conjuntos hiperaritméticos podem ser classificados em uma hierarquia além da hierarquia aritmética; os conjuntos hiperaritméticos são exatamente os conjuntos aos quais são atribuídos um ranking dessa hierarquia.

Cada nível da hierarquia hiperaritmética corresponde a um número ordinal contável (ordinal), mas nem todos os ordinais contáveis correspondem a um nível da hierarquia. Os ordinais usados pela hierarquia são aqueles com uma notação ordinal, que é uma definição concreta e eficaz do ordinal.

Uma notação ordinal é uma descrição eficaz de um ordinal contável por um número natural. Um sistema de notações ordinais é requerido a fim de definir a hierarquia hiperaritmética. A propriedade fundamental na notação ordinal deve ser que ela descreva o ordinal em termos de ordinais menores, de uma maneira eficaz. A seguinte definição indutiva é típica; ela usa uma função de emparelhamento $\langle .,.\rangle$.

• O número 0 é uma notação para o ordinal 0;

• Se $n$ é uma notação para um ordinal $\lambda$, então $\langle 1,n\rangle$ é uma notação para $\lambda +1$;

• Suponha que $\delta$ é um ordinal limite. Uma notação para $\delta$ é um número da forma $\langle 2,e\rangle$, onde $e$ é o índice de uma função computável total $\phi _{e}$, de tal modo que para cada $n$, $\phi _{e}(n)$ é uma notação para um ordinal $\lambda _{n}$ menor que $\delta$ e $\delta$ é o sup do conjunto $\{\lambda _{n}\mid n\in \mathbb {N} \}$.

Existem apenas algumas contáveis notação ordinais, desde que cada notação é um número natural; então existe um ordinal contável que é o supremo de todo ordinal que tem uma notação. Esse ordinal é conhecido como o ordinal de Church-Kleene e é denotado por $\omega _{1}^{CK}$. Note que esse ordinal ainda é contável, o símbolo sendo apenas uma analogia com o primeiro ordinal não contável, $\omega _{1}$. O conjunto de numeros naturais que são notações ordinais é denotado como ${\mathcal {O}}$ e chamado de ${\mathcal {O}}$ de Kleene.

Notações ordinais são usadas para definir saltos de Turing iterados. Esses são conjuntos de números naturais denotados $0^{(\delta )}$ para cada $\delta <\omega _{1}^{CK}$. Suponha que δ tem notação e. O conjunto $0^{(\delta )}$ é definido usando e como a seguir:

• Se $\delta =0$ então $0^{(\delta )}=0$ é o conjunto vazio.

• Se $\delta =\lambda +1$, então $0^{(\delta )}$ é o salto de Turing de $0^{(\lambda )}$. A notação $0'$ e $0''$ são frequentemente usadas para $0^{(1)}$ e $0^{(2)}$, respectivamente.

• Se $\delta$ é um ordinal limite, seja $\langle \lambda _{n}\mid n\in \mathbb {N} \rangle$ a sequência de ordinais menores que $\delta$ dado pela notação $e$. O conjunto $0^{(\delta )}$ é dado pela regra $0^{(\delta )}=\{\langle n,i\rangle \mid i\in 0^{(\lambda _{n})}\}$. Esse é a combinação eficiente dos conjuntos $0^{(\lambda _{n})}$.

Apesar da construção de $0^{(\delta )}$ depender da existência uma notação fixada por $\delta$, e cada ordinal infinito ter muitas notações, um Teorema de Spector mostra que o grau de Turing de $0^{(\delta )}$ depende apenas de $\delta$, não de uma notação particular usada, e então $0^{(\delta )}$ é bem definido até um grau de Turing.

A hierarquia hiperaritmética é definida a partir desses saltos de Turing iterados. Um conjunto $X$ de números naturais é classificado como nível $\delta$ da hierarquia hiperaritmética, para $\delta <\omega _{1}^{CK}$, se $X$ é Turing redutível a $0^{(\delta )}$. Haverá sempre um mínimo tal $\delta$ se houver qualquer; ele é o menor $\delta$ que mede o nível de não computabilidade de $X$.

Conjuntos hiperaritméticos e recursão em tipos mais elevados

Uma terceira caracterização dos conjuntos hiper aritméticos, devido a Kleene, usa funcionais computáveis de alto tipo. Um funcional de tipo 2 ${}^{2}E\colon \mathbb {N} ^{\mathbb {N} }\to \mathbb {N}$ é definido pelas seguintes regras:

${}^{2}E(f)=1\quad$ se existe um $i$ tal que $f(i)>0$,

${}^{2}E(f)=0\quad$ se não existe um $i$ tal que $f(i)>0$.

Usando uma definição precisa de computabilidade com relação a um funcional do tipo 2, Kleene mostrou que um conjunto de números naturais é hiperaritmético se e somente se é computável em relação a ${}^{2}E$.

Exemplo: o conjunto de verdades da aritmética

Todo conjunto aritmético é hiperaritmético, mas existem vários outros conjuntos hiperaritméticos. Um exemplo de um conjunto hiperaritmético e não aritmético é o conjunto $T$ dos números de Gödel de fórmulas da aritmética de Peano, que são verdadeiras nos números naturais padrão $\mathbb {N}$. O conjunto $T$ é Turing equivalente ao conjunto $0^{(\omega )}$, e então não está numa posição elevada na hierarquia hiperaritmética, embora não seja aritmeticamente definível pela Teorema de indefinibilidade de Tarski.

Resultados fundamentais

Os resultados fundamentais da teoria hiper aritmética mostram que as três definições acima definem a mesma coleção de conjuntos dos números naturais. Essas equivalências são devidas a Kleene.

Resultados completos são fundamentais para a teoria. Um conjunto de números naturais é $\Pi _{1}^{1}$-completo se está a um nível $\Pi _{1}^{1}$ da hierarquia analítica, e cada $\Pi _{1}^{1}$ conjunto de números naturais é redutível a ele. A definição de um subconjunto $\Pi _{1}^{1}$-completo do espaço de Baire ($\mathbb {N} ^{\mathbb {N} }$) é similar. Diversos conjuntos associados com a teoria hiper aritmética são $\Pi _{1}^{1}$ completo:

• ${\mathcal {O}}$ de Kleene, o conjunto dos números naturais que são notações para números ordinais.

• O conjuntos de números naturais $e$, tal que a função computável $\phi _{e}(x,y)$ calcula a função característica de uma boa ordenação dos números naturais. Esses são os índices dos ordinais recursivos.

• O conjuntos dos elementos do espaço de Baire que são funções características de uma boa ordenação dos números naturais (usando um isomorfismo efetivo $\mathbb {N} ^{\mathbb {N} }\cong \mathbb {N} ^{\mathbb {N} \times \mathbb {N} }$).

Resultados conhecidos como $\Sigma _{1}^{1}$-limitante seguem dos resultados de completude. Para qualquer conjunto $\Sigma _{1}^{1}$ $S$ de notações ordinais, existe um $\alpha <\omega _{1}^{CK}$ tal que todo elemento de $S$ é uma notação para um ordinal menor que $\alpha$. Para qualquer subconjunto $T$ do espaço de Baire consistindo apenas de funções características de boa ordenação, existe um $\alpha <\omega _{1}^{CK}$ tal que cada ordinal representado em $S$ é menor que $\alpha$.

Hiperaritmética relativizada e hipergraus

A definição de ${\mathcal {O}}$ pode ser relativizada para um conjunto $X$ de números naturais: na definição de uma notação ordinal, a cláusula para ordinais limites é mudada de modo que a enumeração computável de uma sequência de notações ordinais é permitida para usar $X$ como um oráculo. O conjunto de números que são notações ordinais relativas a $X$  é denotado ${\mathcal {O}}^{X}$. O supremo dos ordinais representado em ${\mathcal {O}}^{X}$ é denotado $\omega _{1}^{X}$; esse é um ordinal contável não menor que $\omega _{1}^{CK}$.

A definição de $0^{(\delta )}$ pode também ser relativizada para um conjunto arbitrário $X$ de números naturais. A única mudança na definição é que $X^{(0)}$ é definido para ser $X$, ao invés do conjunto vazio, de modo que $X^{(1)}=X'$ é o salto de Turing de $X$, e assim por diante. Ao invés de terminar em $\omega _{1}^{CK}$, a hierarquia relativa a $X$ passa por todos os ordinais menores que $\omega _{1}^{X}$.

A hierarquia hiperaritmética relativizada é usada para definir a redutibilidade hiperaritmética. Dados conjuntos $X$ e $Y$ dizemos que $X\leq _{HYP}Y$ se e somente se existe um $\delta <\omega _{1}^{Y}$ tal que $X$ é Turing redutível a $Y^{(\delta )}$. Se $X\leq _{HYP}Y$ e $Y\leq _{HYP}X$, então a notação $X\equiv _{HYP}Y$ é usada para indicar que $X$ e $Y$ são hiperaritmeticamente equivalentes. Essa é uma relação de equivalência tão grosseira quanto a equivalência de Turing; por exemplo, cada conjunto de números naturais é hiperaritmeticamente equivalente ao salto de Turing, mas não Turing equivalente ao mesmo. As classes equivalentes à equivalência hiperaritmética são conhecidas como hipergraus.

A função que toma um conjunto $X$ para ${\mathcal {O}}^{X}$ é conhecido como o hipersalto, em analogia ao salto de Turing. Muitas propriedades do hipersalto e dos hipergraus tem sido estabelecidas. Em particular, é sabido que o problema de Post para hipergraus possui uma resposta positiva: para cada conjunto $X$ de números naturais, existe um conjunto $Y$ de números naturais tal que $X<_{HYP}Y<_{HYP}{\mathcal {O}}^{X}$.

Generalizações

A teoria hiperaritmética é generalizada por uma teoria de recursão-α, que é o estudo de subconjuntos definidos por ordinais admissíveis. A teoria hiperaritmética é um caso especial quando $\alpha$ é $\omega _{1}^{CK}$.

References

• H. Rogers, Jr., 1967. The Theory of Recursive Functions and Effective Computability, second edition 1987, MIT Press. ISBN 0-262-68052-1 (paperback), ISBN 0-07-053522-1
• G Sacks, 1990. Higher Recursion Theory, Springer-Verlag. ISBN 3-540-19305-7
• S Simpson, 1999. Subsystems of Second Order Arithmetic, Springer-Verlag.
• C.J. Ash, J.F. Knight, 2000. Computable Structures and the Hyperarithmetical Hierarchy, Elsevier. ISBN 0-444-50072-3

Ligações externas

• Descriptive set theory. Notes by David Marker, University of Illinois at Chicago. 2002.
• Mathematical Logic II. Notes by Dag Normann, The University of Oslo. 2005.