Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
    
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
add comment

3 Answers 3

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

share|improve this answer
    
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
show 1 more comment

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

share|improve this answer
    
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
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.