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

* Dada uma função parcial '''f''' dos números naturais para os naturais, '''f''' é uma função parcialmente recursiva se e somente se o grafo de '''f''', isto é, o conjunto de todos os pares <math>\langle x,f(x)\rangle</math> tais que '''f(x)''' é definido, é recursivamente enumerável.

 

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.