Artificial intelligent assistant

Computability text emphasizing the arithmetical point of view? I learned here that > A set is _recursively enumerable_ if and only if it is at level $\Sigma^0_1$ of the arithmetical hierarchy. Is there an introductory text in computability theory that takes this as the definition of recursively enumerable, or at least emphasizes this (very elegant) characterization?

Every nontrivial recursion theory book will prove that fact, which is just one part of Post's theorem. Rather than just saying that an r.e. set is $\Sigma^0_1$, in later proofs they will often use the fact that they can specify the formula; a set $A$ is r.e. if and only if there is an $e$ such that, for all $n$, $n \in A$ if and only if $\phi_e(n)$ halts. The formula "$\phi_e(n)$ halts" is $\Sigma^0_1$ by Kleene's normal form theorem.

Computability theorists will automatically think "$\Sigma^0_1$" when they see "$\phi_e(n)$ halts", but it's such a routine fact that it's not always worth mentioning. Conversely, our intuitive understanding of $\Sigma^0_1$ formulas is increased because we know they give r.e. sets.

xcX3v84RxoQ-4GxG32940ukFUIEgYdPy ca2ff67c3fa363372b6cbabd11553c2e