Weakly 1-generic sets

(3 ⇒ 2) Let $G \leq_T X$ be weakly 1-generic. For each $m$, the set of strings with a $1$ at some position at least $m$ is dense and computable, so $G$ is infinite. Let $h(n)$ be the number of zeros of $G$ that follow position $n - 1$ before the next $1$: the largest $k$ such that $(G \uh n)\, 0^k \prec G$. It is $G$-computable. Let $f$ be computable and $m \in \nat$. The set $\{ \sigma\, 0^{f(|\sigma|)}\, 1 : |\sigma| \geq m \}$ is dense and computable, so $G$ has a prefix $\sigma\, 0^{f(n)}\, 1$ with $n = |\sigma| \geq m$, and then $h(n) = f(n)$. So $h$ equals $f$ at infinitely many points.

(2 ⇒ 1) If $h$ equals every computable function infinitely often, then $h + 1$ exceeds every computable function at some point.

(1 ⇒ 3) Let $f \leq_T X$ be hyperimmune. We build $G$ with oracle $f$, one bit per stage: at stage $s$, the prefix $\sigma_s = G \uh s$ is known. Say that $e$ is met at stage $s$ if some prefix of $\sigma_s$ belongs to $W_e[f(t)]$ for some $t \leq s$; once met, $e$ stays met, since $\sigma_s \prec \sigma_{s+1}$. The construction may have a target: a pair $(\tau, e)$ with $\tau \succeq \sigma_s$ and $\tau \in W_e$.

Stage $s$. Look for the least $e \leq s$ such that $e$ is not met at stage $s$ and some $\tau \succeq \sigma_s$ belongs to $W_e[f(s)]$. If there is one, and there is no current target or the current target has an index larger than $e$, make $(\tau, e)$ the current target, for the first such $\tau$. Then let $G(s)$ be the bit of the current target at position $s$ if the target is longer than $s$, and $0$ otherwise. When the target is a prefix of $\sigma_{s+1}$, it is achieved, $e$ is met, and there is no current target.

The construction is computable in $f$, so $G \leq_T X$. We show that $G$ meets every dense c.e. set $W_e$.

Each index sets a target finitely often. An index $e$ sets a target only when it is not met; its target is then copied bit by bit, and is achieved unless it is replaced by a target of smaller index. By induction on $e$: if the indices smaller than $e$ set targets finitely often, then after they stop and their last targets are achieved or replaced, any target of $e$ is achieved, after which $e$ is met and never sets a target again.

Dense sets are met. Suppose $W_e$ is dense and $e$ is never met. Let $s_0 \geq e$ be a stage after which no index smaller than $e$ sets a target and none of their targets is current. If at some stage $s \geq s_0$ some $\tau \succeq \sigma_s$ belonged to $W_e[f(s)]$, then $e$ would be the least index with a candidate (a smaller index with a candidate would set a target at stage $s$, since no target of smaller index is current), $e$ would set a target unless its own target is current, and this target would be achieved, so $e$ would be met. Hence, for every $s \geq s_0$, no extension of $\sigma_s$ belongs to $W_e[f(s)]$. Now let $g(s)$ be the least $t$ such that every string of length $s$ has an extension in $W_e[t]$; $g$ is computable and total, since $W_e$ is dense and there are finitely many strings of length $s$. Since $\sigma_s$ has length $s$, the previous observation gives $f(s) < g(s)$ for all $s \geq s_0$, so a finite modification of $g$ dominates $f$, contradicting the hyperimmunity of $f$.

1. A non-computable $\Delta^0_2$ set has hyperimmune degree, as recalled above.
2. By the theorem, a set computing a weakly 1-generic set has hyperimmune degree.
3. If $X \leq_T \emptyset'$, the set $\{ \sigma : \sigma \not\prec X \}$ is dense and computable in $\emptyset'$, hence $\Sigma^0_2$; a weakly 2-generic set meets it, so it is not $X$.