3
$\begingroup$

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

$\endgroup$
3
  • 2
    $\begingroup$ Actually "logician's reals" is just a fancy/borderline condescending name for the Baire space... $\endgroup$
    – Asaf Karagila
    Commented Jun 20, 2013 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$ Commented Jun 20, 2013 at 23:11
  • $\begingroup$ (Asaf's and my comments above are about a previous version of this question.) $\endgroup$ Commented Jun 21, 2013 at 0:26

1 Answer 1

6
$\begingroup$

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

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .