Martin's domination theorem

($\Rightarrow$) Since $A$ is high, $\mathrm{Tot} \leq_T \emptyset'' \leq_T A'$. By the limit lemma relative to $A$ (Shoenfield's limit lemma), there is an $A$-computable function $a(e, s)$ with $\lim_s a(e, s) = \mathrm{Tot}(e)$ for every $e$. Define $g(x)$ as follows. For each $e \leq x$, search for the least $s \geq x$ such that $\Phi_e(x)[s]\converge$ or $a(e, s) = 0$. The search terminates: if $\Phi_e$ is total, $\Phi_e(x)$ converges at some stage; otherwise $a(e, s) = 0$ for all large $s$. Let $v_e = \Phi_e(x)$ if the search ended with $\Phi_e(x)[s]\converge$, and $v_e = 0$ otherwise. Let $g(x) = \sum_{e \leq x} v_e$. It is $A$-computable.

Let $\Phi_e$ be total. Let $s_0$ be such that $a(e, s) = 1$ for all $s \geq s_0$. For $x \geq \max(e, s_0)$, the search for $e$ starts at $s \geq x \geq s_0$, never meets $a(e, s) = 0$, and ends with the convergence of $\Phi_e(x)$; so $v_e = \Phi_e(x)$ and $g(x) \geq \Phi_e(x)$. Hence $g$ eventually dominates $\Phi_e$.

($\Leftarrow$) Let $g \leq_T A$ be dominant. If $\Phi_e$ is total, the function $t_e(x)$, the least $s$ with $\Phi_e(x)[s]\converge$, is computable, so $\forall^\infty x\ t_e(x) \leq g(x)$. Hence

If $e \in \mathrm{Tot}$, take $k$ such that $t_e(x) \leq g(x)$ for $x \geq k$. Conversely, the right-hand side states that $\Phi_e$ converges on every input. Inside the brackets, the first condition is $\Pi^0_1(A)$ and the second is $\Sigma^0_1$, so $\mathrm{Tot}$ is $\Sigma^0_2(A)$. It is also $\Pi^0_2$, hence $\Pi^0_2(A)$. So $\mathrm{Tot}$ is $\Delta^0_2(A)$, that is, computable in $A'$ by Post’s theorem relative to $A$ (Post). Hence $\emptyset'' \leq_T A'$.

Let $M$ be maximal, and let $f(n)$ be the least $m$ such that $\nat \setminus M$ has at least $2n$ elements below $m$; $f$ is $M$-computable, since the complement of $M$ is infinite. We show that $f$ is dominant, so that $M$ is high by Theorem 4.2.

Suppose not, and let $g$ be computable with $\exists^\infty n\ g(n) > f(n)$. Replacing $g$ by $n \mapsto n + \sum_{i \leq n} g(i)$, we may assume that $g$ is strictly increasing. Let $I_n = [g(n), g(n+1))$; these intervals partition $[g(0), \infty)$.

Infinitely many intervals contain two elements of $\nat \setminus M$. Otherwise, let $n_0$ be such that each $I_n$ with $n \geq n_0$ contains at most one element of $\nat \setminus M$, and let $c$ be the number of elements of $\nat \setminus M$ below $g(n_0)$. For $n \geq n_0$, $\nat \setminus M$ has at most $c + (n - n_0)$ elements below $g(n)$. If $g(n) > f(n)$, it has at least $2n$ elements below $g(n)$, so $2n \leq c + n - n_0$, which holds for finitely many $n$ only. This contradicts $\exists^\infty n\ g(n) > f(n)$.

A c.e. superset. Let $W$ be the c.e. set obtained by enumerating $M$ and, at each stage $s$ and for each $n \leq s$, the least element of $I_n$ not in $M_s$, if there is one. If $I_n \not\subseteq M$, the least element of $I_n \setminus M$ is eventually enumerated into $W$, and the elements of $I_n$ enumerated into $W$ are, apart from this one, elements of $M$: an element enumerated at stage $s$ as the least element of $I_n \setminus M_s$ that is not the least element of $I_n \setminus M$ is smaller than it, hence in $M$. So $W \setminus M$ contains exactly one element of each $I_n \not\subseteq M$, and $W \setminus M$ is infinite, since infinitely many intervals meet $\nat \setminus M$. For each of the infinitely many $n$ such that $I_n$ contains two elements of $\nat \setminus M$, the larger ones are not in $W$; so $W$ is coinfinite. This contradicts the maximality of $M$.

($\Leftarrow$) If $X$ is high, let $g \leq_T X$ be dominant; then $g + 1$ is almost everywhere different from every computable function. If $X$ computes a DNC function, let $h \leq_T X$ be as in Theorem 3.4 (2). Let $c(n)$ be an index, computable from $n$, of the c.e. set $\{ \Phi_e(n) : e \leq n,\ \Phi_e(n)\converge \}$, which has at most $n + 1$ elements. Let $k(n) = h(c(n), n + 1)$. Then $k(n) \neq \Phi_e(n)$ for every $e \leq n$ with $\Phi_e(n)\converge$. If $\Phi_e$ is total, $k(n) \neq \Phi_e(n)$ for every $n \geq e$.

($\Rightarrow$) Let $k \leq_T X$ be almost everywhere different from every computable function, and suppose that $X$ is not high. We first show that $\forall^\infty m\ k(m) \neq \Phi_m(m)$. Suppose instead that $k(m) = \Phi_m(m)$ for infinitely many $m$. Then the function $r(n)$, the least $t$ such that $k(m) = \Phi_m(m)[t]\converge$ for some $m$ with $n < m \leq t$, is total and $X$-computable. Since $X$ is not high, $r$ is not dominant (Theorem 4.2): there is a computable $b$ with $\exists^\infty n\ b(n) > r(n)$, and we may assume $b$ non-decreasing, replacing it by $n \mapsto \max_{i \leq n} b(i)$. Let $\psi(m) = \Phi_m(m)$ if $\Phi_m(m)[b(m)]\converge$, and $\psi(m) = 0$ otherwise; $\psi$ is computable. If $b(n) > r(n)$, there is $m$ with $n < m \leq r(n)$ and $\Phi_m(m)[r(n)]\converge = k(m)$; since $b(m) \geq b(n) > r(n)$, $\Phi_m(m)[b(m)]\converge$, so $\psi(m) = k(m)$. This happens for infinitely many $n$, with $m > n$, so $\psi(m) = k(m)$ for infinitely many $m$, a contradiction.

So there is $m_0$ with $k(m) \neq \Phi_m(m)$ for all $m \geq m_0$. Let $k'(m) = k(m)$ for $m \geq m_0$, and for $m < m_0$, let $k'(m) = \Phi_m(m) + 1$ if $\Phi_m(m)\converge$, and $k'(m) = 0$ otherwise. This modification involves finitely many values, so $k' \leq_T X$, and $k'$ is DNC.