Teoria hiperaritmética - Hyperarithmetical theory

Na teoria da recursão , a teoria hiperaritmética é uma generalização da computabilidade de Turing . Ele tem conexões estreitas com a definibilidade na aritmética de segunda ordem e com sistemas fracos de teoria dos conjuntos , como a teoria dos conjuntos de Kripke-Platek . É uma ferramenta importante na teoria de conjuntos descritivos eficaz .

O foco central da teoria hiperaritmética são os conjuntos de números naturais conhecidos como conjuntos hiperaritméticos . Existem três maneiras equivalentes de definir essa classe de conjuntos; o estudo das relações entre essas diferentes definições é uma motivação para o estudo da teoria hiperaritmética.

Conjuntos hiperaritméticos e definibilidade

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

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

A definição de conjuntos hiperaritméticos 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 infinitamente iterados . Esta segunda definição também mostra que os conjuntos hiperaritméticos podem ser classificados em uma hierarquia que estende a hierarquia aritmética ; os conjuntos hiperaritméticos são exatamente os conjuntos aos quais é atribuída uma classificação nesta hierarquia. ${\ displaystyle \ Delta _ {1} ^ {1}}$

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 descrição concreta e efetiva 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 é necessário para definir a hierarquia hiperaritmética. A propriedade fundamental que uma notação ordinal deve ter é que ela descreve o ordinal em termos de ordinais pequenos de uma maneira eficaz. A seguinte definição indutiva é típica; ele usa uma função de emparelhamento . ${\ displaystyle \ langle \ cdot, \ cdot \ rangle}$

O número 0 é uma notação para o 0 ordinal.
Se n é uma notação para um ordinal λ então é uma notação para λ + 1; ${\ displaystyle \ langle 1, n \ rangle}$
Suponha que δ seja um ordinal limite . Uma notação para δ é um número da forma , onde e é o índice de uma função computável total tal que, para cada n , é uma notação para um ordinal λ _n menor que δ e δ é o sup do conjunto . ${\ displaystyle \ langle 2, e \ rangle}$ ${\ displaystyle \ phi _ {e}}$ ${\ displaystyle \ phi _ {e} (n)}$ ${\ displaystyle \ {\ lambda _ {n} \ mid n \ in \ mathbb {N} \}}$

Existem apenas numerosas notações ordinais, uma vez que cada notação é um número natural; assim, há um ordinal contável que é o supremo de todos os ordinais que possuem uma notação. Esse ordinal é conhecido como ordinal Church-Kleene e é denotado . Observe que esse ordinal ainda é contável, o símbolo sendo apenas uma analogia com o primeiro ordinal incontável ,. O conjunto de todos os números naturais que são notações ordinais é denotado e denominado de Kleene . ${\ displaystyle \ omega _ {1} ^ {CK}}$ ${\ displaystyle \ omega _ {1}}$ ${\ displaystyle {\ mathcal {O}}}$ ${\ displaystyle {\ mathcal {O}}}$

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

Se δ = 0, então é o conjunto vazio. ${\ displaystyle 0 ^ {(\ delta)} = 0}$
Se δ = λ + 1, então é o salto de Turing de . As notações e são comumente usadas para e , respectivamente. ${\ displaystyle 0 ^ {(\ delta)}}$ ${\ displaystyle 0 ^ {(\ lambda)}}$ ${\ displaystyle 0 '}$ ${\ displaystyle 0 ''}$ ${\ displaystyle 0 ^ {(1)}}$ ${\ displaystyle 0 ^ {(2)}}$
Se δ é um ordinal limite, seja a seqüência de ordinais menores que δ dada pela notação e . O conjunto é dado pela regra . Esta é a junção efetiva dos conjuntos . ${\ displaystyle \ langle \ lambda _ {n} \ mid n \ in \ mathbb {N} \ rangle}$ ${\ displaystyle 0 ^ {(\ delta)}}$ ${\ displaystyle 0 ^ {(\ delta)} = \ {\ langle n, i \ rangle \ mid i \ in 0 ^ {(\ lambda _ {n})} \}}$ ${\ displaystyle 0 ^ {(\ lambda _ {n})}}$

Embora a construção de dependa de ter uma notação fixa para δ, e cada ordinal infinito tenha muitas notações, um teorema de Spector mostra que o grau de Turing de depende apenas de δ, não da notação particular usada e, portanto, está bem definido até Grau de Turing. ${\ displaystyle 0 ^ {(\ delta)}}$ ${\ displaystyle 0 ^ {(\ delta)}}$ ${\ displaystyle 0 ^ {(\ delta)}}$

A hierarquia hiperaritmética é definida a partir desses saltos de Turing iterados. Um conjunto X de números naturais é classificado no nível δ da hierarquia hiperaritmética, pois , se X for Turing redutível a . Sempre haverá pelo menos tal δ se houver; é este δ menos que mede o nível de uncomputability de X . ${\ displaystyle \ delta <\ omega _ {1} ^ {CK}}$ ${\ displaystyle 0 ^ {(\ delta)}}$

Conjuntos hiperaritméticos e recursão em tipos superiores

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

{\ displaystyle {} ^ {2} E (f) = 1 \ quad}

se houver um i tal que f ( i )> 0,

{\ displaystyle {} ^ {2} E (f) = 0 \ quad}

se não houver i tal que f ( i )> 0.

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

Exemplo: o conjunto de verdade da aritmética

Todo conjunto aritmético é hiperaritmético, mas existem muitos outros conjuntos hiperaritméticos. Um exemplo de conjunto hiperaritmético e não aritmético é o conjunto T de números de Gödel de fórmulas da aritmética de Peano que são verdadeiros nos números naturais padrão . O conjunto T é Turing equivalente ao conjunto e, portanto, não é alto na hierarquia hiperaritmética, embora não seja aritmeticamente definível pelo teorema da indefinibilidade de Tarski . ${\ displaystyle \ mathbb {N}}$ ${\ displaystyle 0 ^ {(\ omega)}}$

Resultados fundamentais

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

Os resultados de completude também são fundamentais para a teoria. Um conjunto de números naturais está completo se estiver no nível da hierarquia analítica e cada conjunto de números naturais for muitos-um redutível a ele. A definição de um subconjunto completo de espaço Baire ( ) é semelhante. Vários conjuntos associados à teoria hiperaritmética estão completos: ${\ displaystyle \ Pi _ {1} ^ {1}}$ ${\ displaystyle \ Pi _ {1} ^ {1}}$ ${\ displaystyle \ Pi _ {1} ^ {1}}$ ${\ displaystyle \ Pi _ {1} ^ {1}}$ ${\ displaystyle \ mathbb {N} ^ {\ mathbb {N}}}$ ${\ displaystyle \ Pi _ {1} ^ {1}}$

Kleene , o conjunto de números naturais que são notações para números ordinais ${\ displaystyle {\ mathcal {O}}}$
O conjunto de números naturais e tal que a função computável calcula a função característica de uma boa ordenação dos números naturais. Esses são os índices de ordinais recursivos . ${\ displaystyle \ phi _ {e} (x, y)}$
O conjunto de elementos do espaço de Baire que são as funções características de uma boa ordenação dos números naturais (usando um isomorfismo efetivo . ${\ displaystyle \ mathbb {N} ^ {\ mathbb {N}} \ cong \ mathbb {N} ^ {\ mathbb {N} \ times \ mathbb {N}})}$

Os resultados conhecidos como delimitadores decorrem desses resultados de integridade. Para qualquer conjunto S de notações ordinais, existe um tal que cada elemento de S é uma notação para um ordinal menor que . Para qualquer subconjunto T do espaço de Baire consistindo apenas em funções características de ordenações de poços, existe um tal que cada ordinal representado em T é menor que . ${\ displaystyle \ Sigma _ {1} ^ {1}}$ ${\ displaystyle \ Sigma _ {1} ^ {1}}$ ${\ displaystyle \ alpha <\ omega _ {1} ^ {CK}}$ ${\ displaystyle \ alpha}$ ${\ displaystyle \ Sigma _ {1} ^ {1}}$ ${\ displaystyle \ alpha <\ omega _ {1} ^ {CK}}$ ${\ displaystyle \ alpha}$

Hiperaritmeticidade relativizada e hiperdegraus

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

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

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

A função que leva um conjunto X até é conhecida como hipersalto por analogia com o salto de Turing. Muitas propriedades do hiper-salto e hiperdegraus foram estabelecidas. Em particular, sabe-se que o problema de Post para hiperdogramas tem uma resposta positiva: para cada conjunto X de números naturais existe um conjunto Y de números naturais tal que . ${\ displaystyle {\ mathcal {O}} ^ {X}}$ ${\ displaystyle X <_ {HYP} Y <_ {HYP} {\ mathcal {O}} ^ {X}}$

Generalizações

A teoria hiperaritmética é generalizada pela teoria α-recursão , que é o estudo de subconjuntos definíveis de ordinais admissíveis . A teoria hiperaritmética é o caso especial em que α é . ${\ displaystyle \ omega _ {1} ^ {CK}}$

Relação com outras hierarquias

Lightface		Negrito
Σ⁰ ₀ = Π⁰ ₀ = Δ⁰ ₀ (às vezes o mesmo que Δ⁰ ₁)		Σ⁰ ₀= Π⁰ ₀= Δ⁰ ₀ (se definido)
Δ⁰ ₁= recursivo		Δ⁰ ₁= clopen
Σ⁰ ₁= recursivamente enumerável	Π⁰ ₁ = co-recursivamente enumerável	Σ⁰ ₁= G = aberto	Π⁰ ₁= F = fechado
Δ⁰ ₂		Δ⁰ ₂
Σ⁰ ₂	Π⁰ ₂	Σ⁰ ₂= F _σ	Π⁰ ₂= G _δ
Δ⁰ ₃		Δ⁰ ₃
Σ⁰ ₃	Π⁰ ₃	Σ⁰ ₃= G _δσ	Π⁰ ₃= F _σδ
⋮		⋮
Σ⁰ _<ω = Π⁰ _<ω = Δ⁰ _<ω = Σ¹ ₀ = Π¹ ₀ = Δ¹ ₀= aritmético		Σ⁰ _<ω= Π⁰ _<ω= Δ⁰ _<ω= Σ¹ ₀= Π¹ ₀= Δ¹ ₀ = aritmética em negrito
⋮		⋮
Δ⁰ _α(α recursivo )		Δ⁰ _α(α contável )
Σ⁰ _α	Π⁰ _α	Σ⁰ _α	Π⁰ _α
⋮		⋮
Σ⁰ _ω^CK ₁ = Π⁰ _ω^CK ₁ = Δ⁰ _ω^CK ₁ = Δ¹ ₁= hiperaritmético		Σ⁰ _{ω ₁}= Π⁰ _{ω ₁}= Δ⁰ _{ω ₁}= Δ¹ ₁= B = Borel
Σ¹ ₁ = lightface analítico	Π¹ ₁ = lightface coanalytic	Σ¹ ₁= A = analítico	Π¹ ₁= CA = coanalítico
Δ¹ ₂		Δ¹ ₂
Σ¹ ₂	Π¹ ₂	Σ¹ ₂ = PCA	Π¹ ₂ = CPCA
Δ¹ ₃		Δ¹ ₃
Σ¹ ₃	Π¹ ₃	Σ¹ ₃ = PCPCA	Π¹ ₃ = CPCPCA
⋮		⋮
Σ¹ _<ω = Π¹ _<ω = Δ¹ _<ω = Σ² ₀ = Π² ₀ = Δ² ₀= analítico		Σ¹ _<ω= Π¹ _<ω= Δ¹ _<ω= Σ² ₀= Π² ₀= Δ² ₀= P = projetivo
⋮		⋮

Referências

H. Rogers, Jr., 1967. The Theory of Recursive Functions and Effective Computability , segunda edição 1987, MIT Press. ISBN 0-262-68052-1 (brochura), ISBN 0-07-053522-1
G. Sacks, 1990. Teoria da Recursão Superior , Springer-Verlag. ISBN 3-540-19305-7
S. Simpson, 1999. Subsystems of Second Order Arithmetic , Springer-Verlag.
CJ Ash, JF Knight , 2000. Computable Structures and the Hyperarithmetical Hierarchy , Elsevier. ISBN 0-444-50072-3

links externos

Teoria descritiva dos conjuntos . Anotações de David Marker, Universidade de Illinois em Chicago. 2002
Lógica matemática II . Notas de Dag Normann, Universidade de Oslo. 2005.

Languages

In other projects