MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

2 Improved formatting, and stuff.

Let $S^\omega$ denote either $\omega^\omega$ or $2^\omega$.

Let's call a function $f: S^\omega \rightarrow$ {0,1} 'nice' if there exists a function $g_f: S^{\lt \omega} \rightarrow 2$ such that for every $x \in S^\omega$: $lim_{k \lim_{k \rightarrow \infty} g_f( (x_0,...,x_k) ) = f(x)$.

(One could think of this as a calculation of $f(x)$ that 'changes its mind' at most finitely often.)

(Note that this does /not/ not imply that $f$ is continuous. Rather, the nice functions correspond to $\Delta_2^0$ sets.)

If $\alpha$ is an ordinal, we call $f$ '$\alpha$-nice' if there exists a function $h_f: S^{\lt \omega} \rightarrow \alpha \times$ {0,1} times\lbrace 0,1\rbrace$such that, using the notation$(\alpha(k), n(k)) = h_f( (x_0,..., x_k) )$, we have: 1) 1.$lim_{k \lim_{k \rightarrow \infty} n(k) = f(x)$for all$x \in S^\omega$2) 2.$\alpha(k+1) \leq \alpha(k)$for all$k \in \omega$3) 3. whenever$n(k+1) \neq n(k)$, we have$\alpha(k+1) \lt \alpha(k)$We'll say that$f$'has rank'$\alpha$if$\alpha$is the minimal ordinal such that$f$is$\alpha$-nice (if there exists any such$\alpha$). Questions: 1) 1. Is every nice function an$\alpha$-nice function for some$\alpha$? 2) 2. Assuming ZFC but not CH, what is the maximum (or l.u.b.) rank that a nice function can have? 1 # Question of combinatorics in the lower part of the Borel hierarchy. Let$S^\omega$denote either$\omega^\omega$or$2^\omega$. Let's call a function$f: S^\omega \rightarrow${0,1} 'nice' if there exists a function$g_f: S^{\lt \omega} \rightarrow 2$such that for every$x \in S^\omega$:$lim_{k \rightarrow \infty} g_f( (x_0,...,x_k) ) = f(x)$. (One could think of this as a calculation of$f(x)$that 'changes its mind' at most finitely often.) (Note that this does /not/ imply that$f$is continuous. Rather, the nice functions correspond to$\Delta_2^0$sets.) If$\alpha$is an ordinal, we call$f$'$\alpha$-nice' if there exists a function$h_f: S^{\lt \omega} \rightarrow \alpha \times${0,1} such that, using the notation$(\alpha(k), n(k)) = h_f( (x_0,..., x_k) )$, we have: 1)$lim_{k \rightarrow \infty} n(k) = f(x)$for all$x \in S^\omega$2)$\alpha(k+1) \leq \alpha(k)$for all$k \in \omega$3) whenever$n(k+1) \neq n(k)$, we have$\alpha(k+1) \lt \alpha(k)$We'll say that$f$'has rank'$\alpha$if$\alpha$is the minimal ordinal such that$f$is$\alpha$-nice (if there exists any such$\alpha$). Questions: 1) Is every nice function an$\alpha$-nice function for some$\alpha\$?

2) Assuming ZFC but not CH, what is the maximum (or l.u.b.) rank that a nice function can have?