Si $L \notin RE$ y $L' \notin RE$ entonces $L \cup L' \notin RE$

Question

Pregunta: si $L \notin RE$ y $L' \notin RE$ entonces $L \cup L' \notin RE

Necesito probar o dar un contraejemplo.

Primero que nada, quiero entender si estoy en lo correcto:

(1) Si $L \notin RE$, ¿puedo concluir que $L \in co-RE$? Porque por mi entendimiento, si $L \notin RE$, significa para mí que para cada entrada $x$ que no está en $L$ la máquina dice no. De lo contrario, no dice no. Lo cual es exactamente como en $co-RE$.

Si me equivoqué arriba,

(2) ¿puedo concluir que si $L \notin RE$ entonces $L^{c} \in RE$?

Aquí está 'mi prueba' si $L \notin RE$ entonces $L^c \notin co-RE$ lo cual es $L^c \in (co-RE)^c$ lo cual es $L^c \in RE

Si la respuesta es sí en (2), entonces necesito probar que si $L^c \in RE$ y $L'^c \in RE$ entonces $(L \cup L')^c \in RE$ lo cual es $ L^c \cap L'^c \in RE $ - lo cual es cierto porque tienen clausura en $\cap$.

Ahora, si estoy correcto en (1) o en (2) entonces sabemos que hay clausura para la Unión para lenguajes que están en $RE$ o en $co-RE$, así que es verdadero por su definición.

Me encantaría saber si estoy correcto en (1) o en (2).

Acá hay una lista de preguntas con las que estoy luchando, por lo tanto no puedo contestar la pregunta eficientemente:

1. si $L \notin RE$ ¿puedo concluir $L \in co-RE$?

2. ¿Cuál es la definición de $L \notin RE$?

3. si $L \notin RE$ entonces $L^c \notin co-RE$?

4. si $L \notin RE$ entonces $L^c \notin RE$?

Answer 1

Sea $H$ el conjunto de parada en una forma razonable. De manera similar, vamos a denotar $L' = \mathbb{N} - L$. Además, puedes buscar "join" en esta página: https://en.wikipedia.org/wiki/Turing_degree.

Pregunta: si $L_1 \notin RE$ y $L_2 \notin RE$ entonces $L_1 \cup L_2 \notin RE

Esto es incorrecto. En particular, toma $L_1 = H \oplus H'$ y $L_2 = H' \oplus H$. Ninguno de los dos son r.e. Sin embargo, tenemos que $L_1 \cup L_2 = \mathbb{N}$. Por supuesto, $\mathbb{N} \in RE

(1) $L \notin RE$ implica $L \in coRE

Esto es incorrecto. Define $X = RE \cup coRE$. Ahora, si tomas cualquier conjunto $L$ tal que $L \notin X$, claramente $L \notin RE. Sin embargo, $L \notin coRE$ también sería cierto por razones obvias.

(2) $L \notin RE$ implica $L' \in RE

Esto también es incorrecto. Una opción es definir $L = H \oplus H'$. Entonces $L \notin RE. Pero luego tenemos que $L' = H' \oplus H$ (y $L' \notin RE

Una segunda opción es definir un conjunto $L$ tal que $H \leq_T L$ pero $L \nleq_T H$. En ese caso, también $L \notin RE$ (ya que $L \in RE$ implicaría $L \leq_T H). Pero también tenemos que $L' \notin RE. Es verdad porque si asumimos por contradicción que $L' \in RE$, entonces tendríamos que $L \in coRE. Sin embargo, $L \in coRE$ implicaría $L \leq_T H

Answer 2

Supongo que $L$ es un conjunto de números naturales, $L'$ es el salto de Turing de $L$, también un conjunto de números naturales, y $L^c$ es su complemento. Entonces, si $L$ y $L'$ no son RE, $L \cup L'$ puede ser RE, pero típicamente no lo es.

Pista para un ejemplo de sí: Intenta definir un conjunto infinito $A$ tal que $A$ esté contenido en $M'$ para cada lenguaje $M$. Entonces, siempre y cuando $L^c$ esté contenido en $A, siempre tendrás $L \cup L' = \mathbb{N}$, que es RE.

Pista para un ejemplo de no: Intenta obtener un conjunto computable infinito $B$ que esté contenido en $M^{\prime c}$ para cada lenguaje $M$. Entonces, siempre y cuando $L$ esté contenido en $B, la unión $L \cup L'$ es uno a uno equivalente a la unión $L \oplus L'$, y en particular es RE solo si $L$ lo es.