Arithmetic genericity

If $W$ is a dense $\Sigma^0_n$ set of strings, no string avoids $W$, so $W^\perp = \emptyset$, and an $n$-generic set meets $W \cup W^\perp = W$.

Let $G$ be weakly $(n+1)$-generic and $W$ a $\Sigma^0_n$ set of strings. The set $W^\perp = \{ \sigma : \forall \tau \succeq \sigma\ \tau \notin W \}$ is $\Pi^0_n$. So $W \cup W^\perp$ is the union of a $\Sigma^0_n$ and a $\Pi^0_n$ set, hence $\Delta^0_{n+1}$, in particular $\Sigma^0_{n+1}$. It is dense. So $G$ meets it.

For each $e$, let $W_e = \{ \sigma : \Phi^{\sigma \oplus A}_e(e)\converge \}$, where the computation with oracle $\sigma \oplus A$ only queries the $G$-side below $|\sigma|$. The sets $W_e$ are $A$-c.e., uniformly in $e$. Since $G$ is 1-generic relative to $A$, it has a prefix in $W_e$ or a prefix avoiding $W_e$. Both questions are decided by $A'$, uniformly in $e$ and in the prefix: "$\sigma \in W_e$" is $\Sigma^0_1(A)$, and ”$\sigma$ avoids $W_e$” is $\Pi^0_1(A)$. With oracle $G \oplus A'$, search through the prefixes $G \uh k$ for one that is in $W_e$ or avoids $W_e$; the search terminates. In the first case $\Phi^{G \oplus A}_e(e)$ converges; in the second case, it diverges, since a convergent computation would have its $G$-use below some $k' \geq |G \uh k|$, and $G \uh k'$ would be an extension of $G \uh k$ in $W_e$.

By induction on $k$. For $k = 0$ there is nothing to prove. Let $k < n$ and suppose $G^{(k)} \equiv_T G \oplus \emptyset^{(k)}$. The jump is invariant under Turing equivalence, so $G^{(k+1)} \equiv_T (G \oplus \emptyset^{(k)})'$. Since $k \leq n - 1$, $G$ is 1-generic relative to $\emptyset^{(k)}$: indeed it is 1-generic relative to $\emptyset^{(n-1)}$, and every $\emptyset^{(k)}$-c.e. set is $\emptyset^{(n-1)}$-c.e. By Lemma 5.2 with $A = \emptyset^{(k)}$, $(G \oplus \emptyset^{(k)})' \leq_T G \oplus \emptyset^{(k+1)}$. Conversely, $G \leq_T (G \oplus \emptyset^{(k)})'$ and $\emptyset^{(k+1)} \leq_T (G \oplus \emptyset^{(k)})'$, since the jump of a set computes the jump of every set below it. Hence $G^{(k+1)} \equiv_T G \oplus \emptyset^{(k+1)}$.

Let $e$ be such that $P(X) \iff \Phi^{X^{(n-1)}}_e(0)\converge$ for every $X$. The reduction $X^{(n-1)} \leq_T X \oplus \emptyset^{(n-1)}$ of Theorem 5.3, for $(n-1)$-generic sets $X$, is given by a procedure that does not depend on $X$: the proof of Lemma 5.2 describes it uniformly, and the induction composes these procedures. So there is an index $d$ such that $P(X) \iff \Phi^{X \oplus \emptyset^{(n-1)}}_d(0)\converge$ for every $(n-1)$-generic set $X$. For $n = 1$ we take $d = e$, and the equivalence holds for every set.

Let $W = \{ \tau : \Phi^{\tau \oplus \emptyset^{(n-1)}}_d(0)\converge \}$, a $\Sigma^0_n$ set of strings. Since $G$ is $n$-generic, it has a prefix $\sigma \in W$ or a prefix $\sigma$ avoiding $W$. In the first case, every set $X \succ \sigma$ satisfies $\Phi^{X \oplus \emptyset^{(n-1)}}_d(0)\converge$, so every $(n-1)$-generic $X \succ \sigma$ satisfies $P$. In the second case, no $X \succ \sigma$ satisfies $\Phi^{X \oplus \emptyset^{(n-1)}}_d(0)\converge$, since a convergent computation would place a prefix of $X$ extending $\sigma$ in $W$; so no $(n-1)$-generic $X \succ \sigma$ satisfies $P$. Since $G$ is itself $(n-1)$-generic and extends $\sigma$, $P(G)$ holds exactly in the first case.

Let $(W_e)$ be an enumeration of the $\Sigma^0_n$ sets of strings, uniform in the sense that $\{ (e, \tau) : \tau \in W_e \}$ is $\Sigma^0_n$; for instance $W_e$ is the $e$-th set of strings c.e. relative to $\emptyset^{(n-1)}$. Build $\sigma_0 = \varepsilon \preceq \sigma_1 \preceq \cdots$ with oracle $\emptyset^{(n)}$. At step $e$, ask whether $\sigma_e$ has an extension in $W_e$; this is a $\Sigma^0_n$ question, answered by $\emptyset^{(n)}$. If yes, search for such an extension $\tau$, using $\emptyset^{(n)}$ to decide membership in $W_e$, and let $\sigma_{e+1} = \tau\, 0$ for the first one found. If no, $\sigma_e$ avoids $W_e$, and $\sigma_{e+1} = \sigma_e\, 0$. The lengths increase strictly, so the limit $G$ is a set; it meets or avoids every $W_e$, so it is $n$-generic, and $G \leq_T \emptyset^{(n)}$. By Theorem 5.3, $G^{(n)} \equiv_T G \oplus \emptyset^{(n)} \equiv_T \emptyset^{(n)}$.