teoria descritiva de conjuntos eficaz - Effective descriptive set theory

Teoria descritiva de conjuntos eficaz é o ramo da teoria descritiva de conjuntos lidar com conjuntos de reais com lightface definições; isto é, definições que não exigem uma verdadeira arbitrária parâmetro (Moschovakis 1980). Assim teoria descritiva de conjuntos eficaz combina teoria descritiva de conjuntos com teoria da recursão .

construções

espaço Polish eficaz

Um espaço Polish eficaz é um completo separável espaço métrico que tem uma apresentação computável . Tais espaços são estudados na teoria eficaz conjunto descritivo e análise construtiva . Em particular, os exemplos padrão de espaços poloneses como a verdadeira linha , o conjunto de Cantor e o espaço de Baire são todos os espaços poloneses eficazes.

hierarquia aritmética

A hierarquia aritmética , hierarquia aritmética ou hierarquia Kleene-Mostowski classifica determinados conjuntos com base na complexidade de fórmulas que as definem. Qualquer conjunto que recebe uma classificação é chamado de "aritmética".

Mais formalmente, a hierarquia aritmética atribui classificações para as fórmulas na linguagem da aritmética de primeira ordem . As classificações estão indicadas e para os números naturais n (incluindo 0). As letras gregas aqui são lightface símbolos, o que indica que as fórmulas não contêm parâmetros definidos. ${\ Displaystyle \ Sigma _ {n} ^ {0}}$${\ Displaystyle \ Pi _ {n} ^ {0}}$

Se uma fórmula é logicamente equivalente a uma fórmula com apenas quantificadores delimitadas em seguida, é atribuída a classificação e . ${\ Displaystyle \ phi}$${\ Displaystyle \ phi}$${\ Displaystyle \ Sigma _ {0} ^ {0}}$${\ Displaystyle \ Pi _ {0} ^ {0}}$

As classificações e são definidos indutivamente para cada número natural n usando as seguintes regras: ${\ Displaystyle \ Sigma _ {n} ^ {0}}$${\ Displaystyle \ Pi _ {n} ^ {0}}$

• Se é logicamente equivalente a uma fórmula de forma , onde é , em seguida, é atribuída a classificação .${\ Displaystyle \ phi}$${\ Displaystyle \ existe {1} \ existe n_ n_ {2} \ cdots \ existe n_ {k} \ psi}$${\ Displaystyle \ psi}$${\ Displaystyle \ Pi _ {n} ^ {0}}$${\ Displaystyle \ phi}$${\ Displaystyle \ Sigma _ {n + 1} ^ {0}}$
• Se é logicamente equivalente a uma fórmula de forma , onde é , em seguida, é atribuída a classificação .${\ Displaystyle \ phi}$${\ Displaystyle \ forall n_ {1} \ forall n_ {2} \ cdots \ forall n_ {k} \ psi}$${\ Displaystyle \ psi}$${\ Displaystyle \ Sigma _ {n} ^ {0}}$${\ Displaystyle \ phi}$${\ Displaystyle \ Pi _ {n + 1} ^ {0}}$

Referências

• Mansfield, Richard; Weitkamp, Galen (1985). Aspectos recursiva de descritiva Teoria dos Conjuntos . Imprensa da Universidade de Oxford. pp. 124-38. ISBN  978-0-19-503602-2 . MR  0.786.122 .
• Moschovakis, Yiannis N. (1980). Descritiva Teoria dos Conjuntos . Holanda do Norte. ISBN  0-444-70199-0 .Segunda edição disponível on-line

Esta teoria dos conjuntos relacionados com artigo é um esboço . Você pode ajudar a Wikipédia expandindo-o . v t e