mostre que este conjunto decidível $ C $ existe

Question

Eu me deparei com este problema que diz que dado conjuntos de disjuntos $ a $ e $ B $ st $ \ bar {A} $ e $ \ bar {b} $ são ambos computableamente enumeráveis (CE)existe um conjunto decidível $ c $ st $ a \ subseteq c $ e $ c \ tampa b=esvazie $ .

Eu acho que uma maneira de construir $ c $ é mostrar que $ \ bar {a} - \ bar {a} - \ barB} $ é ce, mas é a diferença definida $ \ bar {a} - \ bar {b} $ para este caso particular CE?

.

Answer 1

Não, não é necessariamente recursivamente enumerável.Há idiomas que são recursivamente enumeráveis, mas não recursivas.Assim, seu complemento não é recursivamente enumerável.A partir disso, você deve ser capaz de provar que a resposta para a pergunta na frase final do seu post é (eu vou deixar você preencher os detalhes daí).