Conjuntos recursivamente enumeráveis: diferenças entre revisões

Conteúdo apagado Conteúdo adicionado
Linha 61:
 
== Propridedades ==
Se ''A'' e ''B'' são conjunto recursivamente enumeráveis então ''A'' ∩ ''B'', ''A'' ∪ ''B'' and ''A'' × ''B'' (com o par ordenado de números naturais mapeado para um só número natural com a função de emparelhamento de Cantor) são conjuntos recursivamente enumeráveis.
A imagem de um conjunto recursivamente enumerável sob uma função parcial recursiva é um conjunto recursivamente enumerável.
Um conjuntos é recursivamente enumerável se e somente se está no nível <math>\Sigma^0_1</math> da hierarquia aritmética.
 
Um conjunto <math>T</math> é chamado co-recursivamente enumerável se seu complemento é recursivamente enumerável. Equivalentemente, um conjunto é co-recursivamente enumerável se e somente se éestá ou um intervalo de umno funçãonível crescente<math>\Pi^0_1</math> totalmente recursivada ouhierarquia finitoaritmética.
 
Um conjunto ''A'' é recursivo (sinônimo: computável) se e somente se ambos ''A'' e o complemento de ''A'' são recursivamente enumeráveis. ''A'' é recursivo se e seomente se é ou um intervalo de um função crescente totalmente recursiva ou finito.
Alguns pares de conjuntos recursivamente enumeráveis são efetivamente separáveis e outros não.