2
$\begingroup$

Consider Cantor space $2^\omega$ with the standard topology generated by open sets $[\sigma] = \{ \sigma^\frown x: x \in 2^\omega \}$. If $A \subseteq 2^{<\omega}$ and $x \in 2^\omega$, we say $A$ is dense along $x$ if for every prefix $\sigma \prec x$, there is $\tau \succ \sigma$ such that all finite extensions of $\tau$ are in $A$.

An element $x \in 2^\omega$ is 1-generic if, for every $\Sigma^0_1$ (computably enumerable) set $A \subseteq 2^{<\omega}$ which is dense along $x$, we have $x \in [A]$ ($x$ is a path through $A$). I think this is the standard definition (from here).

Now, suppose $T \subseteq 2^{<\omega}$ is a tree. What conditions can we impose on $T$ that guarantee $[T]$ contains a 1-generic member? Effectively, I'm looking for some type of "generic basis theorem". In particular, if $T$ is infinite and $\Sigma^0_2$, can we guarantee it contains a 1-generic path?

$\endgroup$
3
$\begingroup$

What conditions can we impose on $T$ that guarantee $[T]$ contains a 1-generic member?

An element that is 1-generic relative to $T$ will not be on $[T]$ unless $[T]$ contains a whole clopen cone $[\sigma]$. Since "most" 1-generics are 1-generic relative to $T$, I suppose this means the condition to impose is basically that $[\sigma]\subseteq [T]$ for some $\sigma\in 2^{<\omega}$.

Effectively, I'm looking for some type of "generic basis theorem". In particular, if $T$ is infinite and $\Sigma^0_2$, can we guarantee it contains a 1-generic path?

No, if we let $T$ consist of all diagonally non-recursive $\{0,1\}$-valued functions then $T$ contains no 1-generic path. This is because one can show that no 1-generic computes a DNR function.

$\endgroup$
  • $\begingroup$ What do you mean by ' "most" 1-generics are 1-generic relative to $T$'? $\endgroup$ – Jordan Mitchell Barrett Jul 6 '20 at 6:48
  • 1
    $\begingroup$ The set of 1-generics relative to $T$ is comeager in the sense of Baire category. $\endgroup$ – Bjørn Kjos-Hanssen Jul 6 '20 at 6:53
  • $\begingroup$ Bjorn's answer is true even for weak-1-genericicty. More than that, if a recursive tree contains a non-recursive real which is recursive in a sufficiently generic real, then it has a recursive perfect subtree. $\endgroup$ – 喻 良 Dec 12 '20 at 3:34
1
$\begingroup$

I don't think you were asking for 1-genericity relative to $T$ but just plain old normal 1-genericity. I’m going to assume $T$ has no terminal nodes since if it doesn't things get more messy (though I did deal with that way back in my thesis).

The difficulty with any useful basis result here is that you lose if $T$ is too definable. Obviously if T contains a full cone $[\sigma]$ it contains a generic so let's suppose that $\sim T$ is dense (every string can be extended to meet it). But now if $T$ is $\Pi^0_1$ (and hence also if it is computable) it fails to have any generic paths since T complement itself is the witnessing $\Sigma^0_1$ set. But a really complex T need nor help either.

The best I think you can do for a general answer is the obvious thing you would start with: if $\sigma \in T$ and W is a $\Sigma^0_1$ set then you need an extension of $\sigma$ in $T$ that either meets With or strongly avoids that extension. But that's just another way of stating the genericity requirement. You can probably hide that a bit better but I don't think there are any useful basis type results here.

$\endgroup$

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.