Any two uncountable Borel subsets of $[0,1]$ Borel isomorphic

Question 1: Why are any two uncountable Borel subsets of $[0,1]$ Borel isomorphic?

Recall that $f\colon X \to Y$ is a Borel isomorphism if $A$ being Borel in $X$ is equivalent to $f(A)$ being Borel in $Y$.

In Kechris' Classical Descriptive Set Theory, Theorem 17.41, where he's proving the Isomorphism Theorem for Measures, he states that because a certain two sets (called $P\cup M$ and $Q\cup N$) are uncountable Borel sets, there is a Borel isomorphism between them.

I know that by Theorem 15.6, the (Borel) isomorphism theorem, any two standard Borel spaces are isomorphic, but I don't see why an uncountable Borel set is standard (i.e. Polish).

Question 2: Suppose $A$ and $B$ are uncountable $\mathbf{\Sigma^{0}_{n}}$ subsets of $[0,1]$. Can the lowest complexity of a Borel isomorphism between $A$ and $B$ be determined from $A$ and $B$?

I'm not sure if Question 2 even makes sense. I think I'm assuming that if a function from $A$ to $B$ is Borel (i.e. the preimage of every Borel set is Borel) then that function is Borel as a subset of $A\times B$. If this is false, please let me know.

• I don't understand the question. How do Borel subsets can be isomorphic? Nov 8, 2013 at 14:08
• I know we can find a bijection between the two sets, but I don't see why it and it's inverse can be Borel. Nov 8, 2013 at 14:12
• Perhaps the following theorem can help: if $(X,T)$ is a Polish space and $U$ is a Borel set, then there is a topology $T'\supseteq T$ which is also Polish and $U\in T'$? Nov 8, 2013 at 14:14
• @AsafKaragila Doesn't that contradict Theorem 3.11: "A subspace of a Polish space is Polish iff it is a $G_\delta$"? Nov 8, 2013 at 14:34
• No, because we don't consider the subspace topology. We extend the original topology instead. Nov 8, 2013 at 14:35

The usual proof of the Bernstein-Schroeder theorem is fairly explicit, it gives you a construction where you are taking countable unions of small sets. (See "Another proof" on the link above, if you are not familiar with the argument).

It is easy to see from that proof that when you start with Borel injections and Borel sets, all the relevant sets you need end up being Borel as well, and so is the resulting map. (You can also see a write up by Rao here.)

This is a very general phenomenon, that you have a "Bernstein-Schroeder theorem" in many categories. See here for some examples and exceptions. John Goodrick, who is answering the question there, studied this generality in his thesis, in the context of model theory.

For question $2$, there is no bound on the complexity, in general. Greg Hjorth used to comment on this, since in the descriptive set theoretic study of classification problems, we do not take into account the complexity of the relevant Borel maps, and he suggested this may be a mistake, as the Borel functions involved in some arguments may end up being of much higher complexity than the Borel sets they are applied to.

That said, if we bound the complexities of the two sets involved, we can say something. The bijection we obtain from the Bernstein-Schroeder argument is fairly close to the complexities of the injections and the sets involved.

The way we measure complexity here is using the Baire hierarchy of functions. A Baire class 0 function is a continuous function, so preimages of open sets are continuous. A Baire class 1 function has preimages of open sets being $F_\sigma$. Etc. (We can define Baire functions independently of the Borel hierarchy, as the functions obtained by closing the continuous functions under pointwise limits. We then have Baire class 1 functions being pointwise images of continuous functions, Baire class 2 functions being pointwise images of Baire class 1 functions, etc.)

The point is that if you know the Borel complexity of $f^{-1}(O)$ whenever $O$ is open, you can bound the Borel complexity of $f^{-1}(B)$ for arbitrary Borel sets $B$ as well: If preimages of open sets are $\mathbf{\Sigma}^0_\alpha$, then $f^{-1}(B)$ is $\mathbf{\Sigma}^0_{\alpha+\beta}$ if $B$ is $\mathbf{\Sigma}^0_\beta$.

Running the construction as in the Wikipedia page, if $A,B$ are $\mathbf{\Sigma}^0_\alpha$ sets and $f:A\to B$ and $g:B\to A$ are Borel injections whose preimages send open sets to $\mathbf{\Sigma}^0_\beta$ sets then the Borel bijection we obtain between $A$ and $B$ is such that preimages of open sets are at most $\mathbf{\Sigma}^0_{\beta+\alpha+\omega}$. I do not know of a reference off hand verifying whether this is optimal, and it may very well be we can do somewhat better.

Perhaps part of the question is how we know that if $A$ and $B$ are uncountable and Borel, there are Borel injections from $A$ to $B$ and from $B$ to $A$ to begin with. There are several ways of seeing this. One is to prove the result first when one of $A,B$ is the Cantor set. This is classical, or see Rao's note linked to above. A more modern argument goes by showing that given any Borel subset $A$ of a polish space $P$, we can change the topology of $P$ to make $A$ open while preserving the Borel structure of $P$. This is discussed in the book by Becker and Kechris, among other places. The result then follows easily as it is easy to find Borel injections between uncountable open sets.