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

  • 2
    $\begingroup$ Actually "logician's reals" is just a fancy/borderline condescending name for the Baire space... $\endgroup$
    – Asaf Karagila
    Jun 20 '13 at 22:40
  • $\begingroup$ No condescension was meant; I was just saying that to head off any confusion about why I refer to "reals" throughout. Should I get rid of it? $\endgroup$ Jun 20 '13 at 23:11
  • $\begingroup$ (Asaf's and my comments above are about a previous version of this question.) $\endgroup$ Jun 21 '13 at 0:26

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

  • $\begingroup$ Ouch, that really should have occurred to me. Thanks! $\endgroup$ Jun 21 '13 at 0:23
  • 4
    $\begingroup$ I have a 30 page unpublished manuscript about this kind of thing. :) $\endgroup$ Jun 21 '13 at 0:42
  • 2
    $\begingroup$ $\le^*_E $ might be interesting when restricting to a subset, maybe the minimal Turing degrees. $\endgroup$ Jun 21 '13 at 2:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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