Computability text emphasizing the arithmetical point of view?

110 Views Asked by At

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?

1

There are 1 best solutions below

0
On BEST ANSWER

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.