Timeline for Hard-to-"realize" instances of downward density
Current License: CC BY-SA 4.0
9 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 30, 2022 at 1:38 | comment | added | Noah Schweber | Ah yes, that seems right, I was overcomplicating things in my head. | |
| May 30, 2022 at 1:30 | comment | added | Patrick Lutz | The proof in my answer implies that for $X$ and $Y$ c.e. in $A$, "$X$ is $A$-efficiently not above $Y$" is equivalent to "$Y \nleq_T X$ and $X' \leq_T A$." So I think everything should work the same if you work over $X$ and ask the same question as before using $X'$ instead of $0'$. | |
| May 30, 2022 at 1:26 | comment | added | Noah Schweber | Yes (I corrected "efficiently" to "$X'$-efficiently" after the initial posting!). | |
| May 30, 2022 at 1:24 | comment | added | Patrick Lutz | @NoahSchweber In the definition of "efficiently between $X$ and $Y$" do you only require the maps $F$ and $G$ to be $X'$ computable? | |
| May 30, 2022 at 1:23 | comment | added | Noah Schweber | Possibly silly question: does "low over" work analogously to give an affirmative answer to the question, "For all c.e. $X<_TY$ there is a c.e. $Z$ such that $Z$ is $X'$-efficiently strictly between $X$ and $Y$" (apologies for brevity, hopefully it's clear what I mean there)? | |
| May 30, 2022 at 0:59 | comment | added | Patrick Lutz | @NoahSchweber No, I thought about it a little but only enough to convince myself there is not a super straightforward answer. | |
| May 30, 2022 at 0:55 | vote | accept | Noah Schweber | ||
| May 30, 2022 at 0:55 | comment | added | Noah Schweber | Ah, nice! I feel a bit embarrassed in retrospect. Incidentally, do you have any ideas for my previous question about downward-density? | |
| May 30, 2022 at 0:53 | history | answered | Patrick Lutz | CC BY-SA 4.0 |