4
$\begingroup$

I'm probably just missing something obvious but suppose that $T \subset 2^{< \omega}$ is a perfect tree with no terminal nodes (what about just $[T]$ non-empty?). If $Y \leq_{T} X$ for all $X \in [T], X \leq_T T$ must we have $Y \leq_T Z$ for all $Z \in [T]$? In other words, is the lower bound of the $T$ computable paths equal to the lower bound of all paths?

More generally, does the following hold for all $T, n, Y$? $$ \forall X\left[X \in [T] \land X \leq_T T \implies Y \leq_T X^{(n)} \right] \implies \forall Z\left[Z \in [T] \implies Y \leq_T Z^{(n)} \right] $$

I suspect the answer is yes but, if not, would it hold if we assume that $Z$ must be generic relative to $T$ (that was what initially motivated the question and then I realized I didn't know the answer more generally)?

Edit: by generic relative to T I meant being generic in the local forcing on T (perhaps relative to the degree of T).

$\endgroup$
1
  • 2
    $\begingroup$ (Looks like the last sentence of the first paragraph is unfinished.) $\endgroup$ Commented Oct 1 at 23:58

2 Answers 2

5
$\begingroup$

No. Start with $Q$ a $\emptyset'$-computable tree such that the paths are all $2$-random. Make $T$ from $Q$ as follows: wherever $Q$ has a leaf, extend a single path which is a copy of $\emptyset'$.

All the $2$-randoms form a minimal pair with $\emptyset'$, so the $X \in [T]$ which are $T$-computable are the new paths; thus their lower bound is $\emptyset'$. On the other hand, as mentioned, all the paths of $Q$ form minimal pairs with $\emptyset'$, so the lower bound of all paths is $\emptyset$.

For your follow-up question, assuming by generic you mean 1-generic relative to $T$, the answer is yes for somewhat vacuous reasons. If $[T]$ does not contain a neighborhood, then there are no paths through $T$ which are 1-generic relative to $T$, so it holds vacuously. If $[T]$ does contain a neighborhood, then it has computable elements, so both lower bounds are just $\emptyset$.

$\endgroup$
4
  • $\begingroup$ Excellent, but by generic relative to T I meant generic under T local forcing. I probably should have said n-T-generic. $\endgroup$ Commented Oct 4 at 0:45
  • $\begingroup$ Wait, I'm confused. The tree T you built doesn't seem to be perfect since the leaf nodes get extended with a single path. $\endgroup$ Commented Oct 4 at 0:58
  • $\begingroup$ But I guess you can save the argument but instead extending them with a perfect tree whose even levels branch and odd levels encode 0'. $\endgroup$ Commented Oct 4 at 2:14
  • $\begingroup$ I missed the perfect condition, but that fixes it. $\endgroup$ Commented Oct 5 at 5:08
1
$\begingroup$

Dan's idea above is good but he made a tiny mistake that left $T$ non-perfect so I figured I'd fix that and at the same time give a solution that doesn't use machinery from randomness.

Build r.e sets A, B, D all non-computable such that $A \oplus B$ doesn't compute $D$ and A, B are disjoint and can't be separated by any D computable set (victories against a possible D computable seperation get to freeze D with appropriate priority).

Define Leaf to be the set of $\sigma$ such no initial segment of $\sigma$ is in Leaf and if $|\sigma|=s$ then for some $x < s$ either $\sigma(x)=1$ and $A_s(x) = 1$ or $\sigma(x)=0$ and $B_s(x) = 1$. Leaf is clearly a computable set. Define $T$ to be the set of $\sigma$ such that either no initial segment of $\sigma$ is in Leaf or $\sigma$ extends some length $l$ string in Leaf and for all $x$ if $2x \geq l$ then $\sigma(2x) = D(x)$.

This means every $T$ computable path computes $D$ but the path given by the characteristics function of $A$ doesn't compute $D$.

$\endgroup$

You must log in to answer this question.

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