In my attempts to write a cleaner proof (compared to what I was taught) to the fact that for uncountable Polish spaces the Borel hierarchy does not stop until $\omega_1$ I am trying to prove the following specific case:

Suppose $X$ is a perfect Polish space, and $G_\alpha\subseteq\omega^\omega\times X$ is a universal set for $\Pi_\alpha^0(X)$ then we can find a set which is universal for $\Sigma_{\alpha+1}^0(X)$ in the product space.

I am aware that there are proofs in Moschovakis, Kechris and in my teacher's notes. All deal with the general cases and require a lot of notations which I think is unneeded for the case we base the set on the Baire space (since $\omega\times\omega^\omega\cong\omega^\omega$, so $\exists^\omega\Gamma$ universal sets based on Baire space, will be just $\Gamma$ universal sets based on Baire space).

I already know that if $G\subseteq\omega^\omega\times X$ is universal for $\Sigma_\alpha^0$ then $(\omega^\omega\times X)\setminus G$ is universal for $\Pi_\alpha^0$. So I am trying to prove either separately for successor and limit, or give a uniform proof.

Any help will be most welcomed.

  • 1
    $\begingroup$ I have found a nice reference for an even more particular case in Jech's Set Theory. I will probably sit on turning this proof into what I want tomorrow, and granted no one will post any solution - I will post my own. $\endgroup$ – Asaf Karagila Jul 5 '11 at 19:37
  • $\begingroup$ Slightly OT @Asaf: would you write the wiki for descriptive set theory? $\endgroup$ – Willie Wong Jul 6 '11 at 18:17
  • $\begingroup$ @Willie: OT is fun :-D, I will write it but not now, the course I took was not very good and mostly we spent time giving overly complicated proofs for the Borel hierarchy. I intend to study a bit on my own, after that I will surely write the wiki. $\endgroup$ – Asaf Karagila Jul 6 '11 at 18:23

So here is my solution to the problem (which is somewhat of a generalization of the proof in Jech's Set Theory, 3rd Millennium Edition I also unified the case of limit ordinal and successor ordinal).

I will be using three simple facts:

  1. If $X,Y$ are Polish and $X$ perfect then there is an open set in $X\times Y$ which is universal for open sets in $Y$;
  2. If $G_\alpha\subseteq X\times Y$ is universal for $\Sigma^0_\alpha(Y)$ then $(X\times Y)\setminus G_\alpha$ is universal for $\Pi^0_\alpha(Y)$ - and vice versa.
  3. If $X\subseteq Y$ then $\Sigma^0_\alpha(X)=\{A\cap X\mid A\in\Sigma^0_\alpha(Y)\}$, as well for $\Pi^0_\alpha(X)$.
  4. If $f\colon X\to Y$ is continuous and $A\in\Sigma^0_\alpha(Y)$ ($A\in\Pi^0_\alpha(Y)$) then $f^{-1}[A]\in\Sigma^0_\alpha(X)$ ($f^{-1}[A]\in\Pi^0_\alpha(X)$)

Theorem: Let $X,Y$ be Polish spaces, $X$ perfect, and $\alpha<\omega_1$. There exists $G_\alpha\subseteq X\times Y$ such that:

  • $G_\alpha\in\Sigma^0_\alpha(X\times Y)$,
  • $\Big\{\{y\in Y\mid\langle x,y\rangle\in G_\alpha\}\mid x\in X\Big\} = \Sigma^0_\alpha(Y)$ - that is every cut of $G_\alpha$ over $X$ is a $\Sigma^0_\alpha$ subset of $Y$, and every $\Sigma^0_\alpha$ subset of $Y$ is such cut.

Proof: It is enough to show there exists a universal set based on the Baire space. $X$ is perfect so Baire embeds into it as $\Pi^0_2$ (also known as $G_\delta$) - since it is a completely metrizable subset of a metric space.

Now if $\alpha>2$ then the universal set based on Baire embeds into the same level in the hierarchy of $X$ and so the universal set retains its level in the Borel hierarchy of $X$. For $\alpha=1$ we use Fact 1 for open, and its complement for closed sets (Fact 2) and we can generate universal sets based on $X$ in a straightforward manner. If $\alpha=2$ then we use Baire to generate $\Pi^0_2$-universal set in $X$, and Fact 2 to create a $\Sigma^0_2$-universal based on $X$. [Looking back, this proof can be modified so there is no need for the Baire space and the induction could work straightforward using only the fact that a countable product of Polish spaces is Polish.]

Now to prove the specific case that $X=\omega^\omega$.

Take $\langle\alpha_n\mid n<\omega\rangle$ a non-decreasing and cofinal sequence in $\alpha$ (if $\alpha=\beta+1$ take $\alpha_n=\beta$ for all $n$). By induction we have $G_{\alpha_n}\subseteq\omega^\omega\times Y$ which is $\Sigma^0_{\alpha_n}$-universal.

Take a homeomorphism of $\omega^\omega$ with $(\omega^\omega)^\omega$, and let $x_{(n)}$ be the $n$-th coordinate of the image of $x$ under the selected homeomorphism, note that the homeomorphism extends to a homeomorphism from $\omega^\omega\times Y$ to $(\omega^\omega)^\omega\times Y$.

Define $G_\alpha = \{\langle x,y\rangle\mid \exists n\in\omega(\langle x_{(n)},y\rangle\notin G_{\alpha_n})\}$. Equivalently, take $\widehat{G_{\alpha_n}}=(\omega^\omega\times Y)\setminus G_{\alpha_n}$, which is a $\Pi^0_{\alpha_n}$-universal set, and take $$G_\alpha = \{\langle x,y\rangle\mid\exists n\in\omega(\langle x_{(n)},y\rangle\in\widehat{G_{\alpha_n}})\}$$

It is clear that $G_\alpha$ is the union of the continuous preimage of $\widehat{G_{\alpha_n}}$. By Fact 4 this is a union of countably many $\Pi^0_\beta$ sets, for $\beta<\alpha$ and therefore a $\Sigma^0_\alpha$ set as needed.

Suppose $x\in\omega^\omega$, the set $A=\{y\in Y\mid \langle x,y\rangle\in G_\alpha\}$ is the union $\bigcup_n\{y\in Y\mid\langle x_{(n)},y\rangle\in G_{\alpha_n}\}$, and for every $n$ the set is $\Pi^0_{\alpha_n}$, so $A$ is $\Sigma^0_\alpha(Y)$ as needed.

On the other hand, $A\in\Sigma^0_\alpha(Y)$, then $A=\bigcup_n A_n$ for $A_n\in\bigcup_{\beta<\alpha}\Pi^0_\beta$. Since $\alpha_n$ is cofinal in $\alpha$, and $\Pi^0_\gamma(Y)\subseteq\Pi^0_\xi(Y)$ we can assume without the loss of generality that $A_n\in\Pi^0_{\alpha_n}$ (otherwise reorder $A_n$ and add the empty set where needed).

We have that for every $n$ there is $x_n\in\omega^\omega$ such that $A_n=\{y\in Y\mid\langle x_n,y\rangle\in G_{\alpha_n}\}$. Take $x$ such that $x_{(n)}=x_n$, and it is clear that $A=\{y\in Y\mid\langle x,y\rangle\in G_\alpha\}$.

Therefore $G_\alpha$ is as needed.

  • $\begingroup$ There were some minor mistakes in the proof, I finally got around to correct them. $\endgroup$ – Asaf Karagila Jul 17 '11 at 21:44

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.