Unary Borel functions and second-order arithmetic (Q795831)

In the paper statements of descriptive set theory are considered which are provable in third order arithmetic and are not provable in second order arithmetic \(Z_ 2\). These are mainly the following statements: Proposition A. There is a Borel function from \(2^{\omega}\) to \(2^{\omega}\) such that for all shift invariant Borel functions \(G:2^{\omega}\to 2^{\omega}\) (i.e. satisfying \(G(sx)=G(x)\) for all x where \(s(x)(n)=x(n+1))\) we have \(F(x)=G(x)\) somewhere. Proposition E. There is a Borel function \(F:S\to S\) (where S is the group of addition modulo 1 at \(<0,1))\) such that for all Borel functions \(G:S\to S,\) if for all integers \(r>0\), \(G(rx)=G(x)\), then \(G(x)=F(x)\) somewhere. Thus the statements in question are a kind of Borel diagonalization theorems for functions defined on the Cantor space \(2^{\omega}\) or on the circle group. Proposition A is proved in third order arithmetic using a forcing argument. Proposition E is reduced to Proposition A. To prove that A and E are not provable in \(Z_ 2\), it is shown that both A and E imply the existence of an \(\omega\)-model of \(Z_ 2\). In fact they are equivalent (in third order arithmetic) to ''for every countable subset \(A\subseteq {\mathcal L}_{\omega_ 1,\omega}\) there is an \(\omega\)-model of second order comprehension for formulas (with parameters) in A''. The proof of the last theorem is again a diagonalization argument based on the fact that the ''shift'' of x has the same Turing degree as x.