Analytic sets vs recursively enumerable sets

Question

I have long thought (due to my limited knowledge in both subjects) that analytic sets of reals are analogous to recursively enumerable sets of natural numbers:

1. Analytic sets are images of continuous functions, and r.e. sets are images of computable functions.
2. $A\subseteq\mathbb{R}$ is Borel iff both $A$ and $A^c$ are analytic. $A\subseteq\mathbb{N}$ is recursive iff both $A$ and $A^c$ are r.e. I'm only beginning to learn some effective descriptive set theory, but I've heard that the analogy between Borel sets and recursive sets can be made precise in some way.

But recently I realized they are at least in one aspect the exact opposite. Analytic sets satisfy separation property (if $A,B$ are disjoint analytic sets, there exists Borel $C$ s.t. $A\subseteq C$ and $B\subseteq C^c$) but not reduction property (for $A,B$ analytic, it's not always possible to shrink them to disjoint $A^*,B^*$ that are still analytic and satisfy $A\cup B=A^*\cup B^*$). On the other hand, r.e. sets have reduction property but not separation property.

So is the analogy between these two notions superficial? Or is there a framework (effective DST?) in which they do become the same thing? Or are r.e. sets in fact more analogous to coanalytic sets? What about arithmetical hierarchy vs projective hierarchy?

Answer 1

Short version: see Chapter 3 of Sacks' book Higher recursion theory.

---

Longer version:

First of all, neither parallel is perfect. That said:

I would argue that one of the major realizations of generalized recursion theory is that "r.e. $\approx$ coanalytic" is usually more accurate than the (to me) more immediate comparison "$\Sigma^0_1\approx \Sigma^1_1$." To be (more) precise, there is a very tight analogy between "r.e. subset of $\omega$" and "lightface $\Pi^1_1$ subset of $\omega$," since the latter are in fact the "$\omega_1^{CK}$-r.e." sets of natural numbers; there is also a (somewhat separate) connection between $\Pi^1_1$ subsets of $\omega$ and coanalytic sets of reals.

One crucial point of confusion here is "where the existential quantifier goes" in the usual intuition for r.e.-ness. The snappy answer to this is the following (see the first part of Sacks' book Higher recursion theory):

$\Pi^1_1$ is the same as $\Sigma_1(\mathsf{HYP})$.

This can be made even nicer in terms of ordinals (cf. my reference to $\omega_1^{CK}$ earlier): we can think of a $\Pi^1_1$ set $A$ as being built in "layers" indexed by the computable ordinals $(A_\alpha)_{\alpha<\omega_1^{CK}}$, and so "$x\in A$" is the same as "for some $\alpha<\omega_1^{CK}$ we have $x\in A_\alpha$." In the right setting - namely $\omega_1^{CK}$-recursion theory (or its predecessor metarecursion theory) - this exactly parallels the idea of elements entering r.e. sets in stages indexed by $\omega$.

The connection with coanalytic sets of reals is a bit more subtle, but the same basic idea works. Sacks' book (linked above)has a fair amount of material on this topic; I also recommend reading the proof of Theorem 10 and its aftermath on page 19 in Sacks' paper Post's problem, admissible sets, and regularity, which illustrates quite nicely how coanalytic sets "behave like" r.e. sets at ordinals much bigger than $\omega_1^{CK}$ as well.