# 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\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?

-
I somewhat tried to improve the readability by reducing line breaks, using \lim and markup touches (lists and such) –  Asaf Karagila Jan 11 '12 at 10:00
Alternative title for this question: 'How difficult can it be to tell in advance how often one needs to change ones mind?' –  Herman Jurjus Jan 11 '12 at 11:55

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$.

-
Yes, that seems to be it. Thanks! (I will chew on it for a day or so before accepting the answer; who knows there's a catch somewhere.) –  Herman Jurjus Jan 12 '12 at 11:42
The first part is ok. Simply put: the switch-points in $g_f$ form a well-founded tree, and this tree can be labelled with countable ordinals; so you can't possibly go beyond $\omega_1$. Your argument for the reverse, however, needs at least a little repair, I think. For example, if (x0,...xn) is mapped to 0, but (x0,...,xn,0) and (x0,...,xn,1) are both mapped to 1, then we have two 'switches', but, they're not needed. A simpler g could also compute f. In other words: the fact that g_f correctly 'computes' f doesn't prove that rank(f) = rank(g_f). Or am I overlooking something? –  Herman Jurjus Jan 12 '12 at 14:39
BTW, I do think that this is easily repairable. –  Herman Jurjus Jan 12 '12 at 14:41
@Herman: I don't think the reverse needs repair. I did not completely specify a way to do it, or any rk(f); I was just claiming that if you map the finite path tree into $2^{<\omega}$ (and I was not bothering to say how you do it, anything that works fine!) then you can see that this way gives you a method of building $g$'s corresponding to some $f$. Or, if you like, use an inductive argument on countable ordinals to build trees of switches within $2^{<\omega}$ corresponding to $g_f$'s of increasing countable ordinal rank. –  Philip Welch Jan 12 '12 at 15:09
But there exist f's of finite rank with infinitely complex g_f's. So at least the construction needs /somewhat/ more detail. You are right though: induction settles the matter. Therefore your answer is accepted. –  Herman Jurjus Jan 12 '12 at 15:24

(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 “ﬁnitary” inﬁnite 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$.

-
I'm confused by the "easy to see" statement at the start of the second paragraph. Suppose $f:2^\omega\to2$ sends the constant 0 function to 0 and everything else to 1. This is nice with $g_f$ sending any finite sequence of zeros to 0 and all other finite sequences to 1. Then if $s$ is a finite sequence of zeros, there is a proper extension with a different $g_f$-value (just append a 1 to $s$), so $s$ would be unsecured. Then all these finite sequences of 0's form an infinite path through $T_f$. What have I misunderstood here? –  Andreas Blass Jan 12 '12 at 1:15
Oh dear. The "easy to see" statement isn't actually true. I jumped to thinking that the nice functions lined up with the asymptotically stable functions, but asymptotically stable functions have an additional continuity property (in an A.S. function, the limit $f(x)$ is actually determined by an initial segment of $x$). –  Henry Towsner Jan 12 '12 at 3:28

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.

-