Enumerating the reals using a definability hierarchy

84 Views Asked by At

(edit : for those perplexed with the meaning of "truth" in the following, let us say we believe in the consistency of ZFC, use the completeness theorem and reason in a fixed model $M$ of ZFC. The answer to the question may therefore depend on the choice of $M$).

Let $A_0$ denote the standard alphabet for expressing formulas in set theory, $A_0=\lbrace \in,\wedge,\vee,\Rightarrow,\neg,\forall,\exists\rbrace \cup V$ where $V$ is a countable stock of variables. The set $\Phi_0$ of all words over $A_0$ forming meaningful statements is obviously countable, so let $b_0: {\mathbb N} \to \Phi_0$ be a computable bijection. Define a new predicate $T_1(n)$ which says if statement $b_0(n)$ is true, and let $A_1=A_0\cup \lbrace T_1\rbrace$. The set $\Phi_1$ of all words over $A_1$ forming meaningful statements is obviously countable, so let $b_1: {\mathbb N} \to \Phi_1$ be a computable bijection. Define a new predicate $T_2(n)$ which says if statement $b_1(n)$ is true, and let $A_2=A_1\cup \lbrace T_2\rbrace$.

Using transfinite induction and the axiom of choice, one can iterate this construction and produce a sequence $(A_{\alpha})_{\alpha < \aleph_1}$ of countable alphabets such that $A_{\lambda}=\cup_{\alpha < \lambda} A_{\alpha}$ for limit $\lambda$ and $A_{\alpha+1}=A_{\alpha}\cup \lbrace T_{\alpha+1}\rbrace$ where $T_{\alpha+1}(n)$ says if statement $b_{\alpha}(n)$ is true, where $b_{\alpha}$ is a bijection ${\mathbb N} \to \Phi_{\alpha}$, and $\Phi_{\alpha}$ is the set of all words over $A_\alpha$ forming meaningful statements.

Say that a subset $x$ of $\omega$ is $\alpha$-definable if there is a one-variable formula $\phi$ over $A_{\alpha}$ such that $x=\lbrace y \in \omega \ | \ \phi(y) \rbrace$. Denote by $D_{\alpha}$ the set of all $\alpha$-definable subsets of $\omega$.

If ${\cal P}(\omega)=\bigcup_{\alpha < \aleph_1} D_{\alpha}$, then the Continuum Hypothesis holds. Is the converse true ?

Note that it is not clear if the $D_{\alpha}$ sets depends on the $b_{\alpha}$ bijections chosen (it is easy to see that for finite $\alpha$, $D_{\alpha}$ is independent of the choice made). So when I ask if the converse is true, I'm asking whether under CH we have ${\cal P}(\omega)=\bigcup_{\alpha < \aleph_1} D_{\alpha}$ for a suitable choice of the $b_{\alpha}$.