Hierarquia analítica

Na lógica matemática e na Teoria descritiva de conjuntos, a hierarquia analítica é uma extensão da hierarquia aritmética. A hierarquia analítica de fórmulas inclui fórmulas na linguagem da aritmética de segunda ordem, que podem ter quantificadores tanto sobre o conjunto dos números naturais, ${\displaystyle \mathbb {N} }$, quanto sobre as funções de ${\displaystyle \mathbb {N} }$ em ${\displaystyle \mathbb {N} }$. A hierarquia analítica de conjuntos classifica-se pelas fórmulas que podem ser utilizadas para defini-las, que é a versão lightface da projeção hierárquica.

A notação ${\displaystyle \Sigma _{0}^{1}=\Pi _{0}^{1}=\Delta _{0}^{1}}$ indica a classe de fórmulas na linguagem da aritmética de segunda ordem sem quantificadores sobre conjuntos. Esta linguagem não contém conjuntos como parâmetros. As letras gregas aqui são símbolos lightface, que indicam a escolha da linguagem. Cada símbolo em negrito denota a classe correspondente de fórmulas na linguagem estendida com um parâmetro para cada Número real.

A fórmula na linguagem da aritmética de segunda ordem é definido como ${\displaystyle \Sigma _{n+1}^{1}}$ se é logicamente equivalente a uma fórmula da forma ${\displaystyle \exists X_{1}\cdots \exists X_{k}\psi }$ onde ${\displaystyle \psi }$ é ${\displaystyle \Pi _{n}^{1}}$. Uma fórmula é definida como sendo ${\displaystyle \Pi _{n+1}^{1}}$ se é logicamente equivalente a uma fórmula da forma ${\displaystyle \forall X_{1}\cdots \forall X_{k}\psi }$ onde ${\displaystyle \psi }$ é ${\displaystyle \Sigma _{n}^{1}}$. Esta definição indutiva define as classes ${\displaystyle \Sigma _{n}^{1}}$ e ${\displaystyle \Pi _{n}^{1}}$ para cada número natural ${\displaystyle n}$.

Se cada fórmula tem uma forma normal prenex , cada fórmula na linguagem da aritmética de segunda ordem é ${\displaystyle \Sigma _{n}^{1}}$ ou ${\displaystyle \Pi _{n}^{1}}$ para algum ${\displaystyle n}$. Dado que quantificadores inúteis podem ser adicionados a qualquer fórmula, uma vez que uma fórmula recebe a classificação ${\displaystyle \Sigma _{n}^{1}}$ ou ${\displaystyle \Pi _{n}^{1}}$ para algum ${\displaystyle n}$ ela também receberá as classificações ${\displaystyle \Sigma _{m}^{1}}$ e ${\displaystyle \Pi _{m}^{1}}$ para todo ${\displaystyle m}$ maior que ${\displaystyle n}$.

Ao conjunto dos números naturais é atribuída a classificação ${\displaystyle \Sigma _{n}^{1}}$se é definido pela fórmula ${\displaystyle \Sigma _{n}^{1}}$. Ao conjunto é atribuída a classificação ${\displaystyle \Pi _{n}^{1}}$ se for definido pela fórmula ${\displaystyle \Pi _{n}^{1}}$. Se o conjunto for tanto ${\displaystyle \Sigma _{n}^{1}}$ como ${\displaystyle \Pi _{n}^{1}}$ então lhe é dada a classificação adicional ${\displaystyle \Delta _{n}^{1}}$.

Os conjuntos ${\displaystyle \Delta _{1}^{1}}$ são chamados Hiper aritméticos. Uma classificação alternativa para esses conjuntos por meio de de funções computacionais é fornecida pela Teoria Hiper aritmética. Ver Hiperoperação.

A hierarquia analítica pode ser definida em qualquer espaço efetivo polonês que admite uma apresentação computável, a definição é particularmente simples para os espaços de Cantor e de Baire, porque eles se encaixam com a linguagem da aritmética de segunda ordem comum. O espaço de Cantor é o conjunto de todas as seqüências infinitas de 0s e 1s; o espaço de Baire é o conjunto de todas as seqüências infinitas de números naturais. Estes são ambos espaços poloneses.

A axiomatização ordinária de segunda ordem aritmética utiliza uma linguagem baseada em conjunto no qual o conjunto de quantificadores, naturalmente, pode ser visto como a quantificação ao longo do espaço de Cantor. Um subconjunto do espaço de Cantor é atribuído à classificação ${\displaystyle \Sigma _{n}^{1}}$ se isto for definido por uma fórmula ${\displaystyle \Sigma _{n}^{1}}$. Ao conjunto é atribuída a classificação ${\displaystyle \Pi _{n}^{1}}$ se este for definido por uma fórmula ${\displaystyle \Pi _{n}^{1}}$. Se o conjunto for tanto ${\displaystyle \Sigma _{n}^{1}}$ como ${\displaystyle \Pi _{n}^{1}}$ então ele recebe a classificação adicional ${\displaystyle \Delta _{n}^{1}}$.

Um subconjunto do espaço de Baire tem um subconjunto correspondente do espaço 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 . Ao subconjunto de espaço de Baire é dada a classificação ${\displaystyle \Sigma _{n}^{1}}$, ${\displaystyle \Pi _{n}^{1}}$, ou ${\displaystyle \Delta _{n}^{1}}$se e só se o subconjunto correspondente do espaço de Cantor tem a mesma classificação. Uma definição equivalente da hierarquia analítica em espaço de Baire é dada pela definição da hierarquia analítica de fórmulas utilizando uma versão funcional da aritmética de segunda ordem, logo a hierarquia analítica em subconjuntos de 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.

A razão pela qual o espaço de Cantor é homeomórfico a qualquer potência cartesiana finita própria, e que o espaço de Baire é homeomórfico a qualquer potência cartesiana finita de si mesma, é que a hierarquia analítica se aplica igualmente bem a potência finita cartesiana desses espaços. A extensão semelhante é possível para potências contáveis ​​e para os produtos de potências de espaço de Cantor e potências do espaço de Baire.

Assim como a hierarquia aritmética, uma versão relativizada da hierarquia analítica pode ser definida. A linguagem é estendida para incluir um conjunto de símbolos constantes A. Uma fórmula na linguagem estendida é definida indutivamente como sendo ${\displaystyle \Sigma _{n}^{1,A}}$ ou ${\displaystyle \Pi _{n}^{1,A}}$ usando a mesma definição indutiva como acima. Dado um conjunto de ${\displaystyle Y}$, um grupo é definido como ${\displaystyle \Sigma _{n}^{1,Y}}$ se for definido por uma fórmula ${\displaystyle \Sigma _{n}^{1,A}}$ na qual o símbolo ${\displaystyle A}$ é interpretado como ${\displaystyle Y}$; definições similares para ${\displaystyle \Pi _{n}^{1,Y}}$ e ${\displaystyle \Delta _{n}^{1,Y}}$ se aplicam. Os conjuntos que são ${\displaystyle \Sigma _{n}^{1,Y}}$ ou ${\displaystyle \Pi _{n}^{1,Y}}$, para algum parâmetro Y, são classificados na hierarquia projetiva.

• O conjunto de todos os números naturais que são índices de números ordinais computáveis ​​é um ${\displaystyle \Pi _{1}^{1}}$ que não é ${\displaystyle \Sigma _{1}^{1}}$.
• O conjunto de elementos de espaço de Cantor , que são as funções características bem ordenadas ${\displaystyle \omega }$ é um conjunto ${\displaystyle \Pi _{1}^{1}}$ que não é ${\displaystyle \Sigma _{1}^{1}}$. Na verdade, este conjunto não é ${\displaystyle \Sigma _{1}^{1,Y}}$ para nenhum elemento ${\displaystyle Y}$ do espaço de Baire.
• Se o axioma da construtibilidade vale então existe um subconjunto do produto do espaço de Baire com ele, que é ${\displaystyle \Delta _{2}^{1}}$ e é o gráfico de uma boa ordenação do espaço de Baire. Se o axioma vale então exixte também uma boa ordenação ${\displaystyle \Delta _{2}^{1}}$ sobre o espaço de Cantor.

Para cada ${\displaystyle n}$ temos as seguintes propriedades estritas:

${\displaystyle \Pi _{n}^{1}\subset \Sigma _{n+1}^{1}}$,

${\displaystyle \Pi _{n}^{1}\subset \Pi _{n+1}^{1}}$,

${\displaystyle \Sigma _{n}^{1}\subset \Pi _{n+1}^{1}}$,

${\displaystyle \Sigma _{n}^{1}\subset \Sigma _{n+1}^{1}}$.

Um conjunto que está em ${\displaystyle \Sigma _{n}^{1}}$ para algum n é dito ser analítico. O cuidado é necessário para distinguir este uso do termo conjunto analítico, que tem um significado diferente.

• PlanetMath page

• Rogers, H. (1967). Theory of recursive functions and effective computability. [S.l.]: McGraw-Hill 
• Kechris, A. (1995). Classical Descriptive Set Theory Graduate Texts in Mathematics 156 ed. [S.l.]: Springer. ISBN 0-387-94374-9