Muestra que este conjunto decidible existe $ C $

Question

Me encontré con este problema, lo que dice que se le dio los conjuntos de disjoint $ a $ y $ b $ st $ \ bar {a} $ y $ \ bar {b} $ son computables enumerables (CE), existe un conjunto decidible $ C $ st $ A \ subespeteq C $ y $ c \ cap b=vacioset $ .

Creo que una forma de construir $ c $ es mostrar que $ \ bar {a} - \ bar {B} $ es CE, pero es la diferencia establecida $ \ bar {a} - \ bar {b} $ para este caso particular CE?

Answer 1

No, no es necesariamente recursivamente enumerable.Hay idiomas que son recursivamente enumerables pero no recursivos.Por lo tanto, su complemento no es recursivamente enumerable.A partir de eso, debería poder demostrar que la respuesta a la pregunta en la oración final de su publicación es no (le permitiré completar los detalles desde allí).