As far as I understand, it is consistent with ZF that every set of real numbers is a Borel set. Furthermore, I know that relatively weak forms of the axiom of choice suffice to prove that $|\mathcal B| = \mathfrak c$. The standard proof that constructs the Borel hierarchy requires the regularty of $\omega_1$ (so, for example, countable choice) to show that the hierarchy collapses at $\omega_1$, and then requires -- as far as I can tell -- something like the well-orderability of $\mathbb R$ to show that $\aleph_1 \times \mathfrak c = \mathfrak c$.

Can we relax this last 'requirement'? In particular, can we show that there are continuum-many Borel sets using only countable choice?


Yes. Because countable choice is enough to prove that every Borel set has a code, and there are only continuum many codes.

To see that this is the case, first notice—as you did—that countable choice is enough to ensure that the Borel hierarchy is of height $\omega_1$. Next, by induction we can prove every $\bf\Sigma^0_\alpha$ set has a code, simply by concatenating codes for sets from previous levels in the appropriate ways. Choice is needed for choosing these codes, but since we only need to choose from countably many candidates, countable choice is enough.

  • $\begingroup$ To be clear that I understand: a code is a description given by a countable sequence of reals, e.g. by coding an interval $(a, b)$ as $(1, a, b, 0, 0, \ldots)$, coding the complement of a set with code $(a_0, a_1, 0, 0, \ldots)$ as $(0, a_0, a_1, \ldots)$ and coding a union of $(a_i^j)_{i, j \in \omega \times \omega}$ as $(2, a_0^0, a_0^1, a_1^0, a_0^2, a_1^1, a_2^0, \ldots)$? $\endgroup$ – Mees de Vries Jul 10 '18 at 10:51
  • $\begingroup$ Yeah, for example. $\endgroup$ – Asaf Karagila Jul 10 '18 at 10:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.