Borel rank of the set of transitive well–founded relations

66 Views Asked by At

Could you help me with the following question?

Let TW denote the set of all transitive well-founded binary relations $R$ on the set of natural numbers. As any binary relation $R$ on natural numbers could be seen as a point of $\{0,1\}^{\mathbb{N}\times\mathbb{N}}$, we could think of TW as a subset of $\{0,1\}^{\mathbb{N}\times\mathbb{N}}$, endowed with its usual topology. For a countable ordinal $\alpha$ let TW$(\alpha)$ denote the set all those relations $R$ in TW that have a rank smaller than $\alpha$.

Is it true that TW$(\alpha)$ has Borel rank of at most $\alpha$?

Jech: Set theory, Lemma 25.10, says that the set of well-founded binary relations WF$(\alpha)$ with rank of at most $\alpha$ is a Borel set, but it is silent about its Borel rank.

Thanks a lot for your help!

1

There are 1 best solutions below

0
On

This is a partial answer.

Consider $\mathrm{WO}(\alpha)$, the set of wellorderings of rank less than $\alpha$. It is clearly the intersection of $\mathrm{TW}(\alpha)$ with a closed set. Now, by Kechris (p.189, where he quotes Stern), $\mathrm{WO}(\omega^\alpha)$ is $\boldsymbol\Sigma^0_{2\cdot\alpha}$-complete, and each $\mathrm{WO}(\omega^\beta)$ for $\omega^\alpha<\beta<\omega^{\alpha+1}$ is not $\boldsymbol\Sigma^0_{2\cdot\alpha+1}$.

Thus, if $\alpha = \omega^\alpha$, then $\mathrm{TW}(\alpha)$ must be at least $\boldsymbol\Sigma^0_{\alpha}$, and we have a lower bound for such $\alpha$s.

I believe that the lower bound you are looking for can be obtained by reduction to $\mathrm{WF}(\alpha)$, but I have to double check this.