My question is about a fairly artificial preorder on functions from $\omega$ to $\omega$, which for simplicity I'll call "reals."


For $r, s\in {}^\omega\omega$, write $r\le\_E^\*s$ if for each real $f$ computable from $r$, there is some real $g$ computable from $s$ such that $g$ escapes $f$: $$ \forall n\exists m>n (f(m) < g(m)).$$ Let $\le\_E$ be the transitive closure of $\le\_E^\*$, and call a set of the form $$\lbrace f: f\le\_E g\wedge g\le\_E f\rbrace $$ an *escape degree*. Let $\mathcal{E}$ denote the partial order of escape degrees under $\le\_E$.


Now, this is - so far as I know - not a particularly deep notion, and it just arose as a byproduct of playing around with other things. My interest in $\mathcal{E}$ comes from the following few observations:


(1) $\mathcal{E}$ is a linear order. This is because if $r\not\le\_E s$, we must have some $g\le\_T r$ such that $g$ is not escaped by any real computable from $s$. But this means that $g+1$ dominates all $r$-computable reals, and in particular escapes them all - so $s\le\_E^\* r$ and in turn $s\le\_E r$.


(This is the real reason I am interested in $\mathcal{E}$. A more natural ordering to consider might be that gotten by replacing "escapes" with "dominates," throughout, but that degree structure won't be linearly ordered, and linear orders intrigue me.)


(2) $\mathcal{E}$ is uncountable. [EDIT: As Bjorn's answer shows, this is completely false.] Let $X$ be any countable set of reals; then we can find some real $g$ which dominates all reals computable from finitely many reals in $X$. It is easy to check that $g$ is of a different escape degree than any element of $X$.


(3) Individual escape degrees are uncountable. In particular, the escape degree containing the computable reals also contains all all reals which do not compute a function escaping every recursive real - the so-called *hyperimmune-free* or *computably bounded* degrees - and there are uncountably many of these (am I right about this? my memory is somewhat fuzzy on this point.).


(4) I can't seem to answer such basic questions as: "What is the cardinality of $\mathcal{E}$?" (That probably depends on a cardinal characteristic of the continuum.) "Does $\mathcal{E}$ have the countable predecessor property?" "Is $\mathcal{E}$ well-founded?" (I'm almost certain the answer to both of those questions is "no," but I can't prove it.)


My question, then, is this: What can we say about $\mathcal{E}$? In particular, is the order type of $\mathcal{E}$ determined by $ZFC$?


Also, is there any reason we should care about $\mathcal{E}$? I care about it because it seems weird in a way I approve of, but that's not exactly what I'd call a "reason."




---


(Note: because of the apparent connection to cardinal characteristics of the continuum, I've included the "set-theory" tag; feel free to delete if that seems inappropriate.)



A computability-theoretic preorder on reals
This order has only one element.


Indeed, let $h$ be any function. Let $G$ be Cohen generic relative to $h$ (something like 3-generic relative to $h$ will do). Then 


$$
h \le^\*\_E G \le^\*\_E 0
$$


