Given the hierarchy of Borel sets, how to prove that ${\bf \Sigma}_\alpha^0 \subsetneq {\bf \Sigma}_{\alpha+1}^0$ for all ordinal $\alpha<\omega_1$

Question

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

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!

Answer 1

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.