A Hierarquia Aritmética

A hierarquia aritmética classifica conjuntos de números naturais pelo número de quantificadores alternados necessários para defini-los, ligando a complexidade lógica a graus de incomputabilidade.

Definition

A hierarquia aritmética estratifica os conjuntos definíveis na aritmética de primeira ordem contando as alternâncias de quantificadores ilimitados na frente de uma matriz computável, com conjuntos sigma-n definidos por um bloco que começa com um quantificador existencial e conjuntos pi-n por um que começa com um quantificador universal.

Scope

Este tópico abrange a classificação de conjuntos definíveis nos níveis sigma, pi e delta pela alternância de quantificadores sobre relações computáveis, o teorema de Post que relaciona a hierarquia ao problema da parada iterado e aos saltos de Turing, a estrita hierarquia e sua extensão para a hierarquia analítica.

Core questions

• Como a alternância de quantificadores mede a complexidade de um conjunto?
• Como as classes sigma, pi e delta em cada nível se relacionam entre si?
• Como a hierarquia corresponde à iteração do problema da parada?
• Por que a hierarquia é estrita, com cada nível sendo propriamente maior que o anterior?

Key theories

Classificação de quantificadores

Um conjunto é sigma-n se definível por n blocos de quantificadores alternados começando existencialmente sobre uma relação computável, e pi-n se começando universalmente; os conjuntos computavelmente enumeráveis são exatamente os conjuntos sigma-um.

Teorema de Post

Um conjunto é sigma-(n+1) exatamente quando é computavelmente enumerável em relação ao n-ésimo salto de Turing, ligando os níveis da hierarquia a problemas de parada relativizados iterados.

Estrita hierarquia

Cada salto de Turing é estritamente mais complexo que o anterior, de modo que cada nível da hierarquia aritmética contém propriamente os níveis abaixo dele e a hierarquia não colapsa.

Clinical relevance

A hierarquia aritmética é a medida padrão para a complexidade de problemas definíveis em lógica e ciência da computação: ela localiza problemas como a totalidade, finitude e cofinitude de conjuntos computáveis em níveis precisos, e enquadra a fronteira entre o que é computavelmente enumerável e o que requer recursos não computáveis mais fortes.

History

Kleene e Mostowski introduziram independentemente a hierarquia aritmética por volta de 1943, classificando conjuntos pela complexidade de quantificadores sobre predicados computáveis. O teorema de Post conectou a hierarquia ao salto de Turing, unificando as perspectivas baseadas em definibilidade e em computabilidade, e a estrutura foi posteriormente estendida para a hierarquia analítica.

Key figures

• Stephen Cole Kleene
• Andrzej Mostowski
• Emil Post

Seminal works

• rogers1987
• soare1987
• cutland1980

Frequently asked questions

O que significa um nível mais alto na hierarquia?

Mais quantificadores alternados significam uma definição mais complexa e, pelo teorema de Post, um problema que requer mais iterações do problema da parada para ser decidido. Conjuntos mais altos na hierarquia são estritamente menos acessíveis à computação do que aqueles abaixo deles.

Onde se situam os conjuntos computavelmente enumeráveis?

Eles ocupam o nível sigma-um, definíveis por um único quantificador existencial sobre uma relação computável. Seus complementos ocupam o nível pi-um, e os conjuntos que são ambos, os conjuntos delta-um, são exatamente os conjuntos computáveis.