$L_1$ is a recursively enumerable language over some alphabet $\Sigma$. An algorithm effectively enumerates its words as $w_1, w_2, ...$.
$L_2$ is another language over $\Sigma \cup \{\#\}$ as $\{w_i\#w_j : w_i, w_j \in L_1, i < j\}$
Consider the following assertions.
- $L_1$ is recursive implies $L_2$ is recursive
- $L_2$ is recursive implies $L_1$ is recursive
Which statements is/are true?
I reasoned both the statements to be true.
Statement 1 is true. $L_1$ is recursive means it can lexicographically enumerate its strings. The membership question for $L_2$ can be easily settled using the decider and lexicographic enumerator of $L_1$.
Statement 2 is true. The algorithm which decides $L_2$ can be modified to accept if the input string matches either $w_i$ or $w_j$. This settles the membership question for $L_1$.
The given solution to this question however says that statement 2 is false. Could you let me know if my reasoning has gone wrong someplace?