Hierarquia analítica

Predefinição:Mais notas 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, $\mathbb{N}$, quanto sobre as funções de $\mathbb{N}$ em $\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 hierarquia analítica de fórmulas

A notação ${\mathrm{\Sigma }}_0^1={\mathrm{\Pi }}_0^1={\mathrm{\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 ${\mathrm{\Sigma }}_{n+1}^1$ se é logicamente equivalente a uma fórmula da forma $\mathrm{\exists }{X}_1\cdots \mathrm{\exists }{X}_k\psi$ onde $\psi$ é ${\mathrm{\Pi }}_n^1$. Uma fórmula é definida como sendo ${\mathrm{\Pi }}_{n+1}^1$ se é logicamente equivalente a uma fórmula da forma $\mathrm{\forall }{X}_1\cdots \mathrm{\forall }{X}_k\psi$ onde $\psi$ é ${\mathrm{\Sigma }}_n^1$. Esta definição indutiva define as classes ${\mathrm{\Sigma }}_n^1$ e ${\mathrm{\Pi }}_n^1$ para cada número natural $n$.

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

A hierarquia analítica dos conjuntos de números naturais

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

Os conjuntos ${\mathrm{\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 em subconjuntos dos espaços de Cantor e de Baire

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 ${\mathrm{\Sigma }}_n^1$ se isto for definido por uma fórmula ${\mathrm{\Sigma }}_n^1$. Ao conjunto é atribuída a classificação ${\mathrm{\Pi }}_n^1$ se este for definido por uma fórmula ${\mathrm{\Pi }}_n^1$. Se o conjunto for tanto ${\mathrm{\Sigma }}_n^1$ como ${\mathrm{\Pi }}_n^1$ então ele recebe a classificação adicional ${\mathrm{\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 $\omega$ para $\omega$ para a função característica de seu gráfico . Ao subconjunto de espaço de Baire é dada a classificação ${\mathrm{\Sigma }}_n^1$, ${\mathrm{\Pi }}_n^1$, ou ${\mathrm{\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.

Extensões

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 ${\mathrm{\Sigma }}_n^{1,A}$ ou ${\mathrm{\Pi }}_n^{1,A}$ usando a mesma definição indutiva como acima. Dado um conjunto de $Y$, um grupo é definido como ${\mathrm{\Sigma }}_n^{1,Y}$ se for definido por uma fórmula ${\mathrm{\Sigma }}_n^{1,A}$ na qual o símbolo $A$ é interpretado como $Y$; definições similares para ${\mathrm{\Pi }}_n^{1,Y}$ e ${\mathrm{\Delta }}_n^{1,Y}$ se aplicam. Os conjuntos que são ${\mathrm{\Sigma }}_n^{1,Y}$ ou ${\mathrm{\Pi }}_n^{1,Y}$, para algum parâmetro Y, são classificados na hierarquia projetiva.

Exemplos

• O conjunto de todos os números naturais que são índices de números ordinais computáveis ​​é um ${\mathrm{\Pi }}_1^1$ que não é ${\mathrm{\Sigma }}_1^1$.
• O conjunto de elementos de espaço de Cantor , que são as funções características bem ordenadas $\omega$ é um conjunto ${\mathrm{\Pi }}_1^1$ que não é ${\mathrm{\Sigma }}_1^1$. Na verdade, este conjunto não é ${\mathrm{\Sigma }}_1^{1,Y}$ para nenhum elemento $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 é ${\mathrm{\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 ${\mathrm{\Delta }}_2^1$ sobre o espaço de Cantor.

Propriedades

Para cada $n$ temos as seguintes propriedades estritas:

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

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

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

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

Um conjunto que está em ${\mathrm{\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.

Ligações externas

• PlanetMath page

Referências

• Predefinição:Citar livro
• Predefinição:Citar livro