My textbook Introduction to Set Theory 3rd by Hrbacek and Jech introduces $\mathcal B$, the set of all Borel sets, and then mentions that

enter image description here

I have tried, but only to successfully prove that there exists an ordinal $\delta$ such that ${\bf \Sigma}_\delta^0 = {\bf \Sigma}_{\delta+ 1}^0 = {\bf \Pi}_\delta^0 = {\bf \Pi}_{\delta+ 1}^0$.

Please help me prove

${\bf \Sigma}_\alpha^0 \cup {\bf \Pi}_\alpha^0 \subsetneq {\bf \Sigma}_{\alpha+1}^0$ and ${\bf \Sigma}_\alpha^0 \cup {\bf \Pi}_\alpha^0 \subsetneq {\bf \Pi}_{\alpha+1}^0$ for all ordinal $\alpha < \omega_1$.

I am aware of a proof given here, but it appeals to the notion of universal sets, which is too advanced for me.

Thank you for your help!


I don't know of any proof not involving universal sets - and they're an important concept, so it's worth devoting time to understanding them.

Here's a suggestion that might help with that. Let's look at $\bf\Sigma^0_1$ (= open) first. I think that this:

$(*)$ There is an open set $U\subseteq(\omega^\omega)^2$ such that for every open $V\subseteq\omega^\omega$ there is some $f\in\omega^\omega$ such that $V=\{g: \langle f,g\rangle\in U\}$.

is a lot more counterintuitive than this:

$(**)$ There is a natural way to code an open set by a real.

But $(**)$ is exactly the intuition behind $(*)$! Specifically, fix an enumeration $(B_i)_{i\in\omega}$ of the basic open sets in Baire space, and to a real $f\in\omega^\omega$ assign the open set $$[f]:=\{g: \exists i(g\in B_i\wedge f(i)\not=0)\}.$$ The idea is that we view $f$ as enumerating a bunch of basic open sets, and take the corresponding union: $[f]=\bigcup_{f(i)\not=0}B_i$.

Clearly $\{[f]: f\in\omega^\omega\}$ is precisely the set of open subsets of Baire space; I claim that moreover the set $$X:=\{\langle f,g\rangle: g\in[f]\}$$ is an open subset of $(\omega^\omega)^2$. This is our universal set for $\bf\Sigma^0_1$.

So why is $X$ open? Well, suppose $\langle f,g\rangle\in X$. Then there is some $n$ such that $(i)$ $f(n)\not=0$ and $(ii)$ $g\in B_n$. But "$g\in B_n$" is determined by some finite initial segment $\sigma$ of $g$, and so in fact we have that $\langle f',g'\rangle\in X$ whenever $f\upharpoonright n+1=f'\upharpoonright n+1$ and $\sigma\prec g'$; and this gives an open subset of $X$ containing $\langle f,g\rangle$.

More generally, you should think of a universal set for $\bf\Gamma$ as a set of the form "$\{\langle f,g\rangle$: $f$ is a code for a $\bf\Gamma$-set containing $g\}$." And the statement that there is a universal set amounts to saying "there is a good way to code sets in $\bf\Gamma$ by reals."

At this point it's a good exercise to try to whip up a universal set for a more complicated pointclass. $\bf\Sigma^0_2$ is a reasonable next step, but personally I think $\bf\Sigma^1_1$ is a better one to do first (although you should do both). I've rot13'd a hint:

Svk n jnl bs ercerfragvat gerrf ba anghenyf gvzrf anghenyf ol ernyf. Vaghvgviryl, jr jnag gb chg n erny t vagb gur frg "anzrq" ol s vs t vf va gur cebwrpgvba bs gur frg bs cnguf guebhtu gur gerr pbqrq ol s; qb lbh frr ubj gb fnl guvf va n Fvtzn11 jnl? (Guvax nobhg jvgarffrf ...)

After whipping up universal sets for $\bf\Sigma^1_1$ and $\bf\Sigma^0_2$ you should hopefully be optimistic about their existence for lots of pointclasses, and maybe go so far as to conjecture that they exist for all naturally-occurring (and non-self-dual) pointclasses. And now the proof you ask about in the OP here should be pretty accessible.

  • $\begingroup$ Thank you so much for your detailed answer! I will spend time reading it carefully. $\endgroup$ – LE Anh Dung Feb 24 '19 at 17:57
  • 1
    $\begingroup$ @LeAnhDung Thanks - I hope it helps! Let me know if you'd like to clarify something. (And you might want to un-accept until you're happy that I've actually addressed things satisfactorily.) $\endgroup$ – Noah Schweber Feb 24 '19 at 17:57
  • $\begingroup$ Your generosity deserves much more than one upvote and an acceptance from me :) but that's all i am allowed to do by MSE ^^ $\endgroup$ – LE Anh Dung Feb 24 '19 at 18:00

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.