# 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$

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$$.

$${\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.

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.

• Thank you so much for your detailed answer! I will spend time reading it carefully. – LE Anh Dung Feb 24 '19 at 17:57
• @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.) – Noah Schweber Feb 24 '19 at 17:57
• Your generosity deserves much more than one upvote and an acceptance from me :) but that's all i am allowed to do by MSE ^^ – LE Anh Dung Feb 24 '19 at 18:00