I am looking for an alternative yet rigorous proof to a theorem about recursively enumerable sets.
Let $A \subseteq \mathbb{N}_0$ for the purposes of this question. Here is the version of recursive enumerability I am using:
Definition. A set $A$ is recursively enumerable if either $A = \varnothing$ or there exists a total $\mu$-recursive function $\varphi$ such that $\operatorname{Im}(\varphi) = A$.
A theorem posits the equivalence of the above definition with another criterion.
Theorem. $A$ is recursively enumerable $\Longleftrightarrow$ $A$ is the domain of a $\mu$-recursive function $\Omega$.
Assume henceforth that $A \neq \varnothing$.
The $\Longrightarrow$-direction is quite clear and easy to prove formally: taking $\Omega (x) \equiv \mu z[\varphi(z) - x = 0]$ suffices. The converse $\Longleftarrow$-direction is more difficult for me. I have seen two types of arguments so far.
- One of them relies heavily on Church's thesis. This is not rigorous, so is undesirable.
- Both of them make heavy direct or indirect use of the equivalence of the sets of $\mu$-recursive and Turing computable functions. This is not covered in the course I'm taking.
I have thought about putting in the work to rigorously prove the equivalence of these two formulations but it is probably pages of relatively tedious work. Therefore, I thought it would be a good idea to ask before going down that road:
Q: Is there and do you know of a rigorous proof without Turing machines of the statement
$$\text{$A$ is the domain of a $\mu$-recursive function $\Omega \Longrightarrow A$ is recursively enumerable}$$
by, e.g., a direct construction of a total $\mu$-recusive $\varphi$ such that $\operatorname{Im}(\varphi) = A$?