Uncountable closed set of reals biject with reals without replacement or choice

I recently gave a proof of this theorem:

Every uncountable closed set of reals is in bijection with the reals.

My proof used the axiom of countable choice. Asaf Karagila stated in a comment that Arnie Miller showed in "A Dedekind Finite Borel Set" (Arch. Math. Logic 50, No. 1-2, 1-17 (2011); or on arXiv), that we do not need choice to get perfect subsets of uncountable Borel sets, provided that they can be written as a countable union of $G_δ$ sets, and so the theorem can be proven without choice. But it appears that this proof requires the use of the replacement schema.

So my question is:

Is there a proof of that theorem in Z, namely without replacement or choice? (Z does not have the foundation axiom either, but that seems irrelevant to this theorem.)

If the answer is yes, of course the proof would be interesting.

If the answer is no, it would be equally interesting, as an example of a theorem that can be proven in Z+CC or Z+R despite CC and R both being independent of each other over Z, and apparently unrelated. Also, if the answer is no, I have a follow up question:

Is there a proof of that theorem in Z plus replacement on $ω$? (Namely that the image of any definable function on $ω$ is a set.)

Solution 1:

The claim is provable in $Z_2$ (second-order arithmetic) in the sense of definable bijections (and then in $Z_3$ we easily get the theorem verbatim). This requires only minor modification of the standard ZF proof, which only involves objects codable by reals, particularly low complexity sets of reals and countable ordinals.

We first note that $ATR_0$ is well-known to be equivalent to every uncountable closed subset of a Polish space having a perfect subset. Let $X$ be the uncountable closed set and $P$ a perfect subset (Borel coded by reals $r_X$ and $r_P$). The standard construction of a continuous injection $f$ from Cantor space into $P$ (coded by a function on finite binary sequences) goes through easily. Compose that with any explicit injection from $\mathbb{R}$ into Cantor space.

Finally to get a bijection from $X$ to $\mathbb{R},$ carry out the Schroder-Bernstein construction. In the terminology of the Wikipedia article (https://en.wikipedia.org/wiki/Schr%C3%B6der%E2%80%93Bernstein_theorem), $X$-stoppers, $\mathbb{R}$-stoppers, and doubly infinite sequences are all functions from a set of integers to $\mathbb{R},$ and are thus codable by reals. The verifications are routine.

Solution 2:

Here is a partial answer. It cannot be proved by $KP$.

Let $M=L_{\omega_1^{CK}}$, where $\omega_1^{CK}$ is the least nonrecursive ordinal. Fix a recursive binary tree $T$ so that

(1) For any $\alpha<\omega_1^{CK}$, $0^{(\omega\cdot \alpha)}$, the $\omega\cdot\alpha$-th $\Sigma_1$-master code, belongs to $[T]$; and

(2) $[T]\cap M$ only contains those $\omega\cdot \alpha$-master codes; and

(3) $[T]$ is uncountable.

$T$ can be obtained by an effective transfinite recursion through a nonstandard ordinal.

Then in $M$, $T$ is uncountable due to (1).

Now suppose there is a bijection $f:[T]\to 2^{\omega}$ in $M$. Assume that $f\in L_{\alpha}$ for some $\alpha<\omega_1^{CK}$. Let $x\equiv_T 0^{(\beta+1)}$ for some $\beta>\alpha$ in $M$ which is not in $f(L_{\alpha}\cap [T])$ (such $x$ exists due to the admissibility of $M$). Then $f^{-1}(x)\in L_{\beta+1}$. Moreover, by the assumption, $f^{-1}(x)$ is the $\gamma$-th master code for some $\gamma>\alpha$ not greater than $\beta+1$. So $x$ must belong to $L_{\gamma}$ and so $\beta+1\leq \gamma$. In other words, $\gamma=\beta+1$, a contradiction to (2).