GATE CS 2010 Q17 — Undecidability

To determine which statement is not necessarily true, we analyze the closure properties of Recursive (REC) and Recursively Enumerable (RE) languages.

Given:

• $L_1$ is a Recursive (REC) language.
• $L_2$ and $L_3$ are Recursively Enumerable (RE) but not recursive.

Analyzing the Options:

1. $L_2 - L_1$ is RE:
   We can rewrite this as $L_2 - L_1 = L_2 \cap \overline{L_1}$.
   Since $L_1$ is REC, its complement $\overline{L_1}$ is also REC (and therefore RE).
   Since RE languages are closed under intersection, the intersection of $L_2$ (RE) and $\overline{L_1}$ (RE) is always RE.
   (This statement is always true)
2. $L_1 - L_3$ is RE:
   We can rewrite this as $L_1 - L_3 = L_1 \cap \overline{L_3}$.
   Since $L_3$ is RE but not REC, its complement $\overline{L_3}$ is not RE.
   The intersection of a recursive language $L_1$ and a non-RE language $\overline{L_3}$ is not guaranteed to be RE.
   Counterexample: Let $L_1 = \Sigma^*$ (which is REC). Then, $L_1 - L_3 = \Sigma^* - L_3 = \overline{L_3}$, which is not RE.
   (This statement is not necessarily true)
3. $L_2 \cap L_3$ is RE:
   RE languages are closed under intersection. Since both $L_2$ and $L_3$ are RE, their intersection is always RE.
   (This statement is always true)
4. $L_2 \cup L_3$ is RE:
   RE languages are closed under union. Since both $L_2$ and $L_3$ are RE, their union is always RE.
   (This statement is always true)