# Finding 1-generic paths through a tree $T \subseteq 2^{<\omega}$

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?

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.

• What do you mean by ' "most" 1-generics are 1-generic relative to $T$'? – Jordan Mitchell Barrett Jul 6 '20 at 6:48
• The set of 1-generics relative to $T$ is comeager in the sense of Baire category. – Bjørn Kjos-Hanssen Jul 6 '20 at 6:53
• 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. – 喻 良 Dec 12 '20 at 3:34

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.