Hierarquia analítica

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa

Na lógica matemática e teoria dos conjuntos descritivos 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 de análise 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[editar | editar código-fonte]

A notação \Sigma^1_0 = \Pi^1_0 = \Delta^1_0 indica a classe de fórmulas na linguagem da aritmética de segunda ordem com nenhum conjunto de quantificadores. Esta linguagem não contém parâmetros definidos. 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 \Sigma^1_{n+1} se é logicamente equivalente a uma fórmula da forma \exists X_1\cdots \exists X_k \psi where \psi é \Pi^1_{n}. Uma fórmula é definida como sendo \Pi^1_{n+1} se é logicamente equivalente a uma fórmula de forma \forall  X_1\cdots \forall X_k \psi where \psi is \Sigma^1_{n}. Esta definição indutiva define as classes\Sigma^1_n e \Pi^1_n 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 é \Sigma^1_n ou \Pi^1_n para algum n. Se quantificadores de sentido podem serem adicionados a qualquer fórmula, uma vez que uma fórmula é dada a classificação \Sigma^1_n ou \Pi^1_n para algum n será dada as classificações \Sigma^1_m e \Pi^1_m para todo m maior que n.

A hierarquia analítica dos conjuntos de números naturais[editar | editar código-fonte]

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

Os conjuntos \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 de espaço de Cantor e Baire[editar | editar código-fonte]

A hierarquia analítica pode ser definida em qualquer espaço polonês eficaz , a definição é particularmente simples para o espaço de Cantor e 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 ; espaço de Baire é o conjunto de todas as seqüências infinitas de números naturais . Estes são os dois 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 a classificação \Sigma^1_n se isto for definido por uma fórmula \Sigma^1_n. Ao conjunto é atribuída a classificação \Pi^1_n se este for definido pela fórmula \Pi^1_n. Se o conjunto for tanto \Sigma^1_n como \Pi^1_n então ele pode ter uma classificação adicional \Delta^1_n.

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 \Sigma^1_n, \Pi^1_n, ou \Delta^1_nse 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 pelo qual o espaço de Cantor é homeomórfico a qualquer potência cartesiana finita própria, e que o espaço de Baire é homeomórfica a qualquer potência cartesiana finito de si mesma , é que a hierarquia analítica se aplica igualmente bem a energia finita cartesiana desses espaços. A extensão semelhante é possível para aquisições contáveis ​​e para os produtos de potências de espaço de Cantor e ganhos do espaço de Baire.

Extensões[editar | editar código-fonte]

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

Exemplos[editar | editar código-fonte]

  • O conjunto de todos os números naturais que são índices de números ordinais computáveis ​​é um \Pi^1_1 que não é \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 \Pi^1_1 que não é \Sigma^1_1. Na verdade, este conjunto não é \Sigma^{1,Y}_1 para nenhum elemento Y do espaço de Baire.
  • Se o axioma da construtibilidade é impedido então há um subconjunto do produto do espaço de Baire com ele, que é \Delta^1_2 e é o gráfico de um poço ordenado do espaço de Baire. Se o axioma é impedido então exixte também um \Delta^1_2 ordenando bem o espaço de Cantor.

Propriedades[editar | editar código-fonte]

Para cada n temos as seguintes propriedades estritas:

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

Um conjunto que está em \Sigma^1_n 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.

Links Externos[editar | editar código-fonte]

Referências[editar | editar código-fonte]

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