Question

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\lbrace 0,1\rbrace$ 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?

Answer 1

If the switch tree of $g_f$ is finite (i.e. not just well founded, but having only finitely many nodes), then no matter how large the number of nodes, the rank of $f$ will still be no more than 2. (Because an alternative $g'_f$ could give an irrelevant default value 'at first', and 'wait' until all the switchpoints are passed; it can then give its definitive answer as its second value.)

In my opinion, to complete the proof, you need at least something like the following:

Given any countable ordinal $\alpha$, make a countable well-founded tree T having $\alpha$ as its rank, and with the following additional property: for every node $n$, and any child $c$ of that node: (countably) infinitely many copies of the subtree rooted by $c$ occur under $n$.

Next, make an embedding of T into the tree $2^{\lt \omega}$ such that, whenever a non-leaf node of T is associated with sequence $s$, then the children of the node are associated with the sequences $s + [0]$, $s + [1,0]$, $s + [1,1,0]$, etc., where '$+$' denotes concatenation of finite sequences.

(That this can be done can be proved with an non-constructive 'reverse-induction' proof: if there existed a tree for which such an embedding doesn't exist, then there would be a subtree for which such an embedding doesn't exist, this subtree having itself also such a subtree, etc. But since T is well-founded, we can't have an infinite decreasing chain of subtrees. Contradiction.)

Now with /this/ embedding, make $g_f$ such that the switch points are precisely the image points of the embedding, and define $f$ accordingly.

Claim: /then/ $f$ has rank $\alpha$.

A sloppy argument for the latter: Any alternative $g'_f$ which correctly computes $f$ must, at some 'moment' in the sequence $s + [1,1,1,...]$ adopt the correct $f$ value for that infinite sequence; after which 'we still have any subtree of T available', so to speak. I.e. for every such $g'_f$, we can make a sequence that 'forces' $g'_f$ to actually make a change of mind corresponding to the node in T mapped to $s$, and after that point we can still proceed with any child-subtree that we wish.

I'm open for suggestions on how to express all of this more formally.

Answer 2

Consider the case $2^\omega$ (the case of Baire space I believe is only notationally more complicated.) Let $(s_i : i<\omega)$ recursively enumerate $2^{<\omega}$ with $s_0=\varnothing$ and $s_i \subset s_j $ $\rightarrow$ $i < j$

Let $l_i=length(s_i)$. Given a nice function $f$ as witnessed by $g_f$ call $s_i$ a "switch" if $g_f(s_i\upharpoonright l_i - 1) \neq g_f(s_i)$. For switches $s_i,s_j, j\neq i$ only define $s_i \prec s_j$ if $s_i \supset s_j$. By the properties of $f,g_f$, $\prec$ has no infinite descending paths, hence it is a finite path tree $T_{g_f}$, with a rank function $rk_T$ say. Let $r(g_f)$ be the rank of this tree. Then $r(g_f) < \omega_1^{g_f}$ where the latter ordinal is the least not recursive in (the real code of) $g_f$.

Consequently we can now define an $h$ function of the desired kind into $r(g_f)+1 \times 2$ as long as

$h(s) \geq sup [ rk_T(s_i) : s \subset s_i ] +1$ for any $s\in 2^{<\omega}$.

This shows any nice function is an $\alpha$-nice function for some $h$, and thus answers 1.

Conversely given any finite path tree one can embed it into $2^{<\omega}$ in an order preserving way, via $G$ say, and define a function $f,g_f$ using the range of $G$ as "switches". As any countable ordinal is realised as the rank of such a finite path tree we see that the l.u.b for Q2 is $\omega_1$.

Answer 3

(As Andreas has pointed out, this answer is not correct---it concerns a slightly different class of functions.)

The answer to your first question is yes. For any nice function $f$, consider the tree $T_f$ of finite sequences $(x_0,\ldots,x_k)$ such that there is some proper extension $(x_0,\ldots,x_k,\ldots,x_{k+r})$ with $$g_f((x_0,\ldots,x_k))\neq g_f((x_0,\ldots,x_k,\ldots,x_{k+r})).$$ (In other contexts, this is called the "tree of unsecured sequences".)

Then it is easy to see that $f$ being nice implies that this tree is well-founded. The function $h_f$ can be defined, with ordinal $ht(T_f)$, by setting the ordinal value $\alpha((x_0,\ldots,x_k))$ to be the height of $(x_0,\ldots,x_k)$ in $T_f$ if this sequence is unsecured, and $0$ if the sequence is secured.

In the $2^\omega$ case, this means the supremum of ranks of nice functions is $\omega$: by Konig's lemma, a well-founded binary tree is finite.

In the $\omega^\omega$ case, I believe the supremum of ranks should be $\omega_1$ (in plain ZFC), though the proof doesn't appear to be entirely obvious. (One could to take a tree of sequences of height $\alpha$, which induces a function $h_f$, and then take the corresponding $f$, but some additional work is needed to ensure that there is no other representation of $f$ giving it a lower rank.)

Functions like your $g_f$, but with range $\omega$ instead of ${0,1}$, have been called "asymptotically stable". I believe this terminology was introduced by Tao in a blog post; Kohlenbach and Gaspar have a paper ("On Tao’s “finitary” infinite pigeonhole principle") discussing an application, and I have a paper with Beiglbock ("Transfinite Approximation of Hindman's Theorem") which deals with the tree $T_f$.