Every subset of $\mathbb N \times \mathbb N$ can be viewed as a relation on $\mathbb N$. The set $\mathcal P(\mathbb N \times \mathbb N)$ of all relations on $\mathbb N$ has a natural topology with which it is homeomorphic to the Cantor space. A pretty well-known fact from descriptive set theory is:

The subset $\mathsf{WO}$ of well orderings of $\mathbb N$ is a coanalytic subset of $\mathcal P(\mathbb N \times \mathbb N)$.

This is one of the most natural examples out there of a subset of a Polish space that is coanalytic but not Borel. This coanalytic set stratifies nicely into an increasing union of $\omega_1$ Borel sets:

For each $\alpha < \omega_1$, the set $\mathsf{WO}_{\alpha}$ of all well orderings of $\mathbb N$ with order type $\alpha$ is Borel.

Question: Given $\alpha < \omega_1$, is there a $G_\delta$ set $A \subseteq \mathcal P(\mathbb N \times \mathbb N)$ such that $\mathsf{WO}_{\alpha} \subseteq A \subseteq \mathsf{WO}$?

Motivation: If the answer is positive, then we would be able to write this coanalytic set as a union $\bigcup_{\alpha < \omega_1} A_\alpha$ of $G_\delta$ sets, which would imply that there is a partition $\{ A_\alpha \setminus \bigcup_{\xi < \alpha} A_\xi :\, \alpha < \omega_1 \}$ of $\mathsf{WO}$ into $F_{\sigma \delta}$ sets. Because $\mathsf{WO}$ is an example of a complete coanalytic set, this would then imply that every coanalytic set can be partitioned into $\aleph_1$ $F_{\sigma \delta}$ sets, answering another recent question of mine.

  • 1
    $\begingroup$ By Hurewicz Theorem, the hyperpsace $K_{<\omega_1}(2^\omega)$ of countable closed susbets of the Cantor set $2^\omega$ is $\Pi^1_1$-complete. This hyperspace is the union $\bigcup_{\alpha\in\omega_1}K_\alpha(2^\omega)$, where each $K_\alpha(2^\omega)$ is the hyperspace of all subsets of $2^\omega$ that are homeomorphic to the ordinal $\alpha+1$ with the order topology. What is the Borel complexity of the hyperspaces $K_\alpha(2^\omega)$? $\endgroup$ Apr 21 at 21:41

2 Answers 2


No, not for $\alpha\geq\omega$. For let $A$ be $G_\delta$ and suppose that WO$_\alpha\subseteq G_\delta$. Let's show that $A\not\subseteq$ WO. Fix a sequence $\left<A_n\right>_{n<\omega}$ of open sets such that $A=\bigcap_{n<\omega}A_n$. Instead of directly discussing elements of $\mathcal{P}(\mathbb{N}\times\mathbb{N})$, I will discuss functions $x:\mathbb{N}\times\mathbb{N}\to 2$, and functions $\sigma:n\times n\to 2$ for $n<\omega$ as their finite approximations. Say that such a $\sigma$ is \emph{good} if it is (the characteristic function of) a linear order on $n$ (where $\mathrm{dom}(\sigma)=n\times n$). Note that since $\alpha\geq\omega$, every good $\sigma$ extends to some $x\in\mathrm{WO}_\alpha$. We can assume that for each $n$ we can fix a set $B_n$ of good tuples such that $A_n$ is just the set of all $x$ which extend some $\sigma\in B_n$, and $B_n$ is closed under extension, i.e. if $\sigma\in B_n$ and $\sigma'$ extends $\sigma$ and is also good, then $\sigma'\in B_n$.

Now we will construct a sequence $\left<\sigma_n,k_n\right>_{n<\omega}$ consisting of good $\sigma_n\in B_n$ with $\sigma_n\subsetneq\sigma_{n+1}$, and integers $k_n$, as follows. (Letting $x=\bigcup_{n<\omega}\sigma_n$, we will then have $x\in A$. But the plan is to arrange that $x(k_{n+1},k_n)=1$ for all $n$, so $x\notin\mathrm{WO}$.)

So, fix some $\sigma_0\in A_0$ with domain $m\times m$ for some $m>0$, and let $k_0=0$. Given $\sigma_n\in A_n$, and given $k_0<\ldots<k_n$ with $\mathrm{dom}(\sigma_n)=m'\times m'$ for some $m'>k_n$, let $k_{n+1}=m'$, and let $\sigma'_n$ be good and with domain $(m'+1)\times(m'+1)$ and with ``bottom'' element $m'$, i.e. $\sigma'_n(m',i)=1$ for all $i<m'$. Now since $\sigma'_n$ is good, we can find $y\in\mathrm{WO}_\alpha$ such that $\sigma'_n\subseteq y$, and therefore $y\in A_{n+1}$. So let $\sigma_{n+1}\in B_{n+1}$ with $\sigma'_n\subseteq\sigma_{n+1}$. This completes the construction.

Letting $x=\bigcup_{n<\omega}\sigma_n$, note that $x\in A$, but $x(k_{n+1},k_n)=1$ for all $n$, so $x\notin\mathrm{WO}$.


A negative answer follows from $(*)$ Proposition 8.2 of Jacques Stern's paper “Effective partitions of the real line into Borel sets of bounded rank”. Link to paper:


Assume $\alpha<\omega_1$ is a countable ordinal, $(\omega+\omega)\cdot\alpha<\beta<\omega_1$ is an arbitrary countable ordinal sufficiently large, and $A\subseteq\textrm{WO}$ is a $\mathbf{\Sigma}^0_\alpha$ Borel set. We'll show that $\textrm{WO}_{\omega^\beta}\not\subseteq A$.

Assume towards a contradiction that $\textrm{WO}_{\omega^\beta}\subseteq A$. Recall that $S_\infty$ is the Polish group of all permutations on $\omega$, and it admits a logic action on $\mathscr{P}(\omega\times\omega)$ in which each $\textrm{WO}_\gamma$ is an $S_\infty$-orbit. Then the Vaught transform $A^\Delta=A^{\Delta S_\infty}$ of $A$ is still a $\mathbf{\Sigma}^0_\alpha$ Borel set such that $\textrm{WO}_{\omega^\beta}\subseteq A^\Delta$, since $\textrm{WO}_{\omega^\beta}$ is $S_\infty$-invariant. By the cited proposition $(*)$, if $(\omega+\omega)\cdot \alpha<\zeta<\omega_1$ is arbitrary then we also have $\textrm{WO}_{\omega^\zeta}\subseteq A^\Delta$. In particular, there is an unbounded set of $\omega^\zeta=\gamma<\omega_1$ for which $\textrm{WO}_\gamma\subseteq A^\Delta$. On the other hand since $\textrm{WO}$ is $S_\infty$-invariant, $A^\Delta\subseteq\textrm{WO}$ is a Borel subset, and the boundedness theorem for analytic subsets of $\textrm{WO}$ implies $\{\gamma:\textrm{WO}_\gamma\textrm{ intersects }A^\Delta\}$ is bounded below $\omega_1$. This is a contradiction.

Letting $\alpha=3$ gives for any $A\subseteq\textrm{WO}$ a $\mathbf{\Pi}^0_2$ set, $\textrm{WO}_{\omega^{\omega\cdot 7}}\not\subseteq A$ which is weaker than Farmer S's answer.

  • 1
    $\begingroup$ Thanks very much for sharing this. I wasn't aware of this paper before. The remarks following Problem II in the introduction of Stern's paper, together with Theorem 4, seem to come very close to answering the other question I posted (the one linked to in this question) in the negative. If I'm reading things right, they say that a positive solution cannot come from an $\omega_1$-norm on a coanalytic set. Theorem 4 rules out a too-nice-looking solution to the problem in any form. Thanks again, and welcome to MathOverflow! $\endgroup$
    – Will Brian
    Apr 24 at 12:00
  • $\begingroup$ Thanks for the kind comment and very glad to be of help! I wasn't familiar with this paper as well, but I was lead to it after a quick search through the literature for any result that bounded the Scott complexities of countable ordinals from below. Stern's next paper “Evaluation du rang de Borel de certains ensembles” seemed to contain more results of the similar kind, but unfortunately I couldn't find any available copy of it. $\endgroup$
    – Edward H
    Apr 24 at 15:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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