Determining whether a language $L_{a}$ is recursively enumerable. I'm trying to determine whether a language $L_{a}$ is recursively enumerable, but first I'm having trouble deciphering the definition $L_{a}$ given the following question:
Given an recursively enumerable language $L$, we can define $L_{a} = \{ x : \exists\langle M\rangle \in L \text{ such that } x \in L(M)\}$. Prove $L_{a}$ is recursively enumerable.
I understand it as the language $L_{a}$ is searching for a Turing Machine encoding $\langle M \rangle$ that exists in $L$, but I'm not sure this is correct.
Furthermore, when trying to prove a language is recursively enumerable is generally easier to prove this through some sort of contradiction or by using the property of decidability?
 A: There are two equivalent criteria for a set $A$ to be r.e.: (1) the existence of an algorithm $M$ that implements a total function whose domain is $\Bbb{N}_+$ and whose range is $A$. (2) the existence of an algorithm $M$ that implement a partial function whose domain is $A$ (i.e., $M$ terminates iff its input belongs to $A$). Here "algorithm" means a Turing machine or any equivalent notion.
In your example, it is convenient to use both of these characterizations (quite a common occurrence). We are given an r.e. set $L$ that we view as comprising codes defining Turing machines. I will write $\{e\}$ for the function computed by the Turing machine with code $e$. By characterization (1) there is an algorithm $M$ that implements a total function $f$ say $\Bbb{N}_+ \to A$ whose range is $L$. We want to show that the set $L_a$ of $x$ such that $x \in \mathrm{dom}(\{e\})$, for some $e \in L$, is r.e.. To do this we use characterization (2) and design an algorithm $N$ that terminates on input $x$ iff $x \in L_a$. Given an input $x$, $N$ works in stages. At stage $n$, $N$ has a list of states $s_1, \ldots, s_n$ resulting from partial executions of the Turing machines coded by $f(1), \ldots, f(n)$. At stage $0$, we have an empty list of states. To get from stage $n$ to stage $n+1$, $N$ simulates one extra step for the execution of the machines coded by $f(1), \ldots, f(n)$ in the states $s_1 \ldots, s_n$ giving a new list of states $s_1', \ldots, s_n'$ and sets $s_{n+1}'$ to be  the initial state of the machine coded by $f(n+1)$ on input $x$. $N$ terminates the computation as soon as one of the $s_i$ is a terminating state for the machine coded by $f(i)$ (meaning that $x \in \mathrm{dom}(\{f(i)\})$. It should be clear that $N$ terminates on input $x$ iff $x$ is in the $\mathrm{dom}\{e\}$ for some $e \in L$, i.e., iff $x \in L_a$.
