Recursive sets vs constructible sets in ${\cal P}(\omega)$ Let $D$ be the set of all recursive (aka decidable) sets of
integers, and $C$ be the set of all constructible sets of integers
, i.e. $C=L\cap {\cal P}(\omega)$ where $L$ is Godel's constructible
universe. What inclusions hold or do not hold between $C$ and $D$ ?
My thoughts : $D$ is countable since there are only countably many
programs/algorithms to decide the sets. On the other hand, $C$ is uncountable inside $L$ because $L$ is a model of $ZFC$, and my guess is that $C$ should stay
uncountable inside $V$, so the inclusion $C \subseteq D$ should be false.
 A: You are right. $L$ contains all Turing machines of $V$ (since Turing machines are/can be coded as elements of $V_{\omega} = V_{\omega}^{L}$) and it evaluates Turing machines correctly. So $D = D^L$, where $D^L$ is the set of all subset of $\omega$ that are decidable from the point of view of $L$. On the other hand 
$$
C = \mathcal P(\omega) \cap L = \mathcal P(\omega)^L,
$$
i.e. $C$ is the powerset of $\omega$ as constructed in $L$. Since $\operatorname{ZFC}$ proves that there are non-recursive subsets of $\omega$, we have that 
$$
L \models D^L \subsetneq \mathcal P(\omega),
$$
i.e. $D = D^L \subsetneq C$.
We can be much more precise than that: Let 
$$
E = \{ I \in \omega \mid I = \langle M \rangle \text{ for some Turing machine } M \text{ that holds on empty input} \},
$$
where $\langle . \rangle$ is some primitive recursive coding. Then $E = E^L \in C$ and $E \not \in D$ (this is the halting problem). So $E$ is a canonical witness for $D \neq C$.
A: Just an extra comment. Given that recursive sets can equivalently be described as $\Delta^0_1$-formulas, all these sets lie in $L_{\omega+2}$ (since $\omega\in L_{\omega+1}$). Given that $\mathcal P(\omega)^L$ is cofinal in $L_{\omega_1^L}$, there are many non-recursive subsets.
