betaFeedback

WorksMathematics

Some variants of function domination

Abstract

We investigate whether classical recursion-theoretic notions defined by function domination remain unchanged when success is required only on sets of prescribed asymptotic density. We establish robustness for many such notions and uncover unexpected connections between familiar degree properties by comparing upper and lower density. In contrast, pdomination, as defined by Chong, Hoi, Stephan and Turetsky, is not robust under density weakenings. We also answer a question of Kjos-Hanssen and Nies by characterizing superhighness as domination with a threshold boundedly limit recursive in the oracle. As an application, we introduce supermaximal sets, a strengthening of maximality whose degrees are exactly the superhigh r.e. degrees.

Introduction and preliminaries

Function domination is one of the principal ways in which growth rates encode the computational strength of a Turing degree. For total functions f,g:ω→ωf,g:\omega\to\omega, we say that ff dominates gg, and write g≪fg\ll f, if (∀∞n) g(n)≤f(n)(\forall^\infty n)\ g(n)\le f(n). A function is recursively dominated if some recursive function dominates it. Following Miller and Martin [16], a degree is hyperimmune-free if every function in it is recursively dominated, and it is hyperimmune otherwise. In the opposite direction, Martin’s domination theorem [15] identifies the high degrees:

A′≥T∅′′⟺(∃f≤TA)(∀g recursive) g≪f.A' \ge_T \emptyset'' \quad\Longleftrightarrow\quad(\exists f \le_T A)(\forall g\ \text{recursive})\ g\ll f.

These two classical notions already suggest that the placement of the quantifiers, rather than growth rate alone, carries the degree-theoretic content.

This paper asks how much of that content survives when eventual or everywhere success is weakened to success on a large set of inputs. The test is asymptotic density. For C⊆ωC\subseteq\omega and n>0n>0, let ρn(C)=∣C∩[0,n)∣n\rho_n(C)=\frac{|C\cap[0,n)|}{n}, and define its lower and upper asymptotic densities by ρ‾(C)=lim inf⁡n→∞ρn(C)\underline{\rho}(C)=\liminf_{n\to\infty}\rho_n(C) and ρ‾(C)=lim sup⁡n→∞ρn(C)\overline{\rho}(C)=\limsup_{n\to\infty}\rho_n(C). If these two quantities are equal, their common value is denoted by ρ(C)\rho(C).

Definition 1.1. Given functions f,g:ω→ωf,g:\omega\to\omega, we say that ff coarsely dominates gg, written g≪cfg\ll_c f, if ρ({m:f(m)≥g(m)})=1\rho(\{m:f(m)\ge g(m)\})=1. A function ff is coarsely recursively bounded if it is coarsely dominated by some recursive function.

Every recursively dominated function is coarsely recursively bounded, but the converse fails, which follows from a simple diagonal argument.

Our main concern is robustness. A definition based on domination, agreement, or tracing is robust under a density weakening when the weakened condition defines the same degree class. For many of the notions considered here, even positive lower density retains the content of eventual or everywhere success. In investigating this robustness, we also uncover some unexpected connections: replacing upper density by lower density in suitable formulations relates familiar notions whose usual definitions look quite different. § 2 begins by showing that coarse hyperimmunity is exactly ordinary hyperimmunity, and that highness is preserved when eventual domination is weakened to domination on a set of positive lower density. These results also place hyperimmunity and highness into a common scheme:

a is hyperimmune ⟺ (∃f≤Ta)(∀ recursive g) ρˉ({n:f(n)≥g(n)})>0,\text{a is hyperimmune}\ \Longleftrightarrow\ (\exists f \leq_T \text{a})(\forall\text{ recursive }g)\ \bar{\rho}(\{n:f(n)\geq g(n)\})>0,
a is high ⟺ (∃f≤Ta)(∀ recursive g) ρ({n:f(n)≥g(n)})>0.\text{a is high}\ \Longleftrightarrow\ (\exists f \leq_T \text{a})(\forall\text{ recursive }g)\ \rho(\{n:f(n)\geq g(n)\})>0.

In the upper-density characterization, positive upper density can be strengthened to upper density one. We also obtain an upper-density-one version of the infinitely-often-equal characterization of hyperimmunity (see Monin and Nies [18 Proposition II.17]).

Array recursiveness is also preserved when eventual domination is replaced by domination on a set of positive lower density. The corresponding upper-density condition instead characterizes ∅′≰TA\emptyset' \nleq_T A. For A≤T∅′A \leq_T \emptyset', lowness admits an analogous lower-density characterization using a single f≤T∅′f \leq_T \emptyset' to bound all partial AA-recursive functions, with undefined inputs counted as correct. Its upper-density version characterizes incompleteness.

Recursive semi-traceability is unchanged if agreement at infinitely many inputs is replaced by agreement on a set of upper density one. Positive upper density yields the same class; positive lower density instead forces AA to be recursive.

Strong jump traceability is likewise preserved when, for every recursive order bound and every partial AA-recursive function, an r.e. trace obeying the prescribed bound is required to be correct only on a set of positive lower density, again counting undefined inputs as correct. The upper-density analogue requires a different treatment of partiality: we spread each input over a long finite block to account for sparse domains, and count only genuine trace hits at defined inputs. Requiring that, for every order bound and every partial AA-recursive function ψ\psi with infinite domain, there be an r.e. trace obeying that bound whose genuine hits for ψ\psi have positive upper density characterizes the non-DNR degrees.

Almost-everywhere domination provides a measure-theoretic instance of robustness. Using its equivalence with uniformly almost-everywhere and positive-measure domination due to Kjos-Hanssen, Miller, and Solomon [14], we show that positive lower density suffices in both the uniform measure-one and the positive-measure formulations. The uniform formulation requires one f≤TAf \leq_T A to dominate every total g≤TXg \leq_T X on a set of positive lower density, for almost every X∈2ωX \in2^\omega. Replacing lower density by upper density here yields precisely the hyperimmune degrees.

§ 3 characterizes superhighness through domination with effective thresholds. As an application to r.e. degrees, we study an effective strengthening of maximality for r.e. sets. Mohrherr [17] defined a set AA to be superhigh when ∅′′≤ttA′\emptyset'' \leq_{tt} A'. Superhighness occurs naturally in work on almost-everywhere domination and algorithmic randomness [20, 10]. Kjos-Hanssen and Nies [10] asked for a domination characterization of superhighness.

Definition 1.2 (Cole and Simpson [3]). A total function h:ω→ωh:\omega\to\omega is boundedly limit recursive in AA if there are an AA-recursive function H(n,s)H(n,s) and a recursive function rr such that h(n)=lim⁡sH(n,s)h(n)=\lim_s H(n,s) and ∣{s:H(n,s)≠H(n,s+1)}∣<r(n)\lvert\{s:H(n,s)\ne H(n,s+1)\}\rvert<r(n)

for every nn. We write

BLR⁡(A)={h:h is boundedly limit recursive in A}.\operatorname{BLR}(A)=\{h:h\text{ is boundedly limit recursive in }A\}.

We answer their question in Theorem 3.1 (with Liang Yu): a set AA is superhigh if and only if there are f≤TAf \le_T A and h∈BLR⁡(A)h \in\operatorname{BLR}(A) such that, for the standard enumeration (Φe)e∈ω(\Phi_e)_{e\in\omega} of the partial recursive functions, whenever Φe\Phi_e is total, (∀n≥h(e)) Φe(n)≤f(n)(\forall n\ge h(e))\ \Phi_e(n)\le f(n). Thus superhighness is characterized by domination together with bounded-limit control of when domination begins.

An application is that the degrees containing supermaximal sets are exactly the superhigh r.e. degrees (Theorem 3.2). This gives an analogue of Martin’s characterization of the high r.e. degrees as those containing maximal sets [15]. Recall that an r.e. coinfinite set AA is maximal if its complement is cohesive: for each ee, all sufficiently large elements of A‾\overline{A} agree on membership in WeW_e. We call AA supermaximal if these homogeneity thresholds can be chosen as the values of a single function h∈BLR⁡(A)h \in\operatorname{BLR}(A). Since there are high r.e. degrees that are not superhigh [17], this defines a proper subclass of the maximal sets.

Proposition 3.3 returns to density robustness. Superhighness is also equivalent to the existence of f≤TAf \le_T A for which each total Φe\Phi_e is dominated on a set of density one, with convergence controlled by a two-variable function m∈BLR⁡(A)m \in\operatorname{BLR}(A): for every k≥1k\ge1 and N≥max⁡{1,m(e,k)}N\ge\max\{1,m(e,k)\}, ρN({n:Φe(n)≤f(n)})≥1−2−k\rho_N(\{n:\Phi_e(n)\le f(n)\})\ge1-2^{-k}. For any fixed rational 0<α<10<\alpha<1, it is already sufficient to require these proportions to be at least α\alpha beyond a threshold in BLR⁡(A)\operatorname{BLR}(A).

§ 4 gives a contrasting example using pdomination, introduced by Chong, Hoi, Stephan, and Turetsky [1]. We consider two weakenings: counting inputs outside the test domain as correct, and measuring successful domination relative to that domain. Both collapse to the class of all sets even at density one. A single partial recursive function witnesses both density-one conditions. These results show that density robustness cannot be taken for granted.

Preliminaries

We use standard notation from recursion theory and identify a Turing degree with any representative when no confusion can arise. For background, see Soare [21], Nies [19], and Downey and Hirschfeldt [5]. Unless explicitly declared partial, all functions have domain ω\omega. For sets AA and BB, the notations A≤ttBA\le_{tt}B and A≤wttBA\le_{wtt}B denote truth-table and weak truth-table reducibility, respectively.

We begin with a rapidly growing block system used in the density conversions in § 2. Its essential feature is that each block occupies an asymptotically full proportion of the initial segment ending at its right endpoint.

Definition 1.3. Let (qn)n∈ω(q_n)_{n\in\omega} and (Qn)n∈ω(Q_n)_{n\in\omega} be given by q0=2q_0=2, qn+1=qn2q_{n+1}=q_n^2, and

Qn=[qn,qn+1).(1)Q_n=[q_n,q_{n+1}). \tag*{(1)}

Lemma 1.4. For every C⊆ωC\subseteq\omega,

∣ρqn+1(C)−∣C∩Qn∣∣Qn∣∣≤1qn⟶0.\left|\rho_{q_{n+1}}(C)-\frac{|C\cap Q_n|}{|Q_n|}\right|\le\frac{1}{q_n}\longrightarrow0.

Consequently:

(i) If ρ(C)=δ>0\rho(C)=\delta>0 and 0≤η<δ0\le\eta<\delta, then ∣C∩Qn∣>η∣Qn∣|C\cap Q_n|>\eta|Q_n| for all sufficiently large nn.

(ii) If Qn⊆CQ_n\subseteq C for infinitely many nn, then ρ‾(C)=1\overline{\rho}(C)=1.

(iii) If C∩Qn=∅C\cap Q_n=\varnothing for infinitely many nn, then ρ‾(C)=0\underline{\rho}(C)=0.

Proof. Since [0,qn+1)=[0,qn)∪Qn[0,q_{n+1})=[0,q_n)\cup Q_n is a disjoint union,

∣ρqn+1(C)−∣C∩Qn∣∣Qn∣∣=qnqn+1∣ρqn(C)−∣C∩Qn∣∣Qn∣∣≤qnqn+1=1qn.\left|\rho_{q_{n+1}}(C)-\frac{|C\cap Q_n|}{|Q_n|}\right| =\frac{q_n}{q_{n+1}}\left|\rho_{q_n}(C)-\frac{|C\cap Q_n|}{|Q_n|}\right| \leq\frac{q_n}{q_{n+1}}=\frac{1}{q_n}.

The inequality holds because both proportions inside the absolute value belong to [0,1][0,1]. Since qn→∞q_n\to\infty, the three consequences follow by taking lower or upper limits. □\square

Definition 1.5. For any partial function ψ\psi, define its block spreading ψblk\psi^{\mathrm{blk}} by

ψblk(m)≃{ψ(0),m<q0,ψ(n),m∈Qn.\psi^{\mathrm{blk}}(m)\simeq \begin{cases} \psi(0), & m<q_0,\\ \psi(n), & m\in Q_n. \end{cases}

For total ψ\psi, block spreading preserves weak truth-table reducibility to a set AA. Applied to a positive, nondecreasing, unbounded recursive function, block spreading preserves these properties as well. Together with Lemma 1.4, it is the common mechanism behind the proofs in § 2.

We next fix the effective indexing used for superhighness. Let (Φe)e∈ω(\Phi_e)_{e\in\omega} be a standard enumeration of the partial recursive functions, and put Tot⁡={e:Φe is total}\operatorname{Tot}=\{e:\Phi_e\text{ is total}\}, INF⁡={e:We is infinite}\operatorname{INF}=\{e:W_e\text{ is infinite}\}. It is a standard fact that Tot⁡≡ttINF⁡≡tt∅′′\operatorname{Tot}\equiv_{\mathrm{tt}}\operatorname{INF}\equiv_{\mathrm{tt}}\emptyset''.

The following fact explains the connection between the class BLR⁡(A)\operatorname{BLR}(A) and truth-table reducibility to the jump and will be used throughout § 3.

Lemma 1.6 (Cole and Simpson [3]). For sets AA and BB, the following are equivalent.

(i) A≤ttB′A\leq_{\mathrm{tt}}B'.

(ii) A≤wttB′A\leq_{\mathrm{wtt}}B'.

(iii) The characteristic function of AA belongs to BLR⁡(B)\operatorname{BLR}(B).

Remark 1.7. Cole and Simpson [3] observed that A≤TBA\leq_T B implies BLR⁡(A)⊆BLR⁡(B)\operatorname{BLR}(A)\subseteq\operatorname{BLR}(B). In particular, A≡TBA\equiv_T B implies BLR⁡(A)=BLR⁡(B)\operatorname{BLR}(A)=\operatorname{BLR}(B).

The robust properties

Proposition 2.1. For every Turing degree a\mathbf{a}, the following are equivalent.

(i) a\mathbf{a} is hyperimmune.

(ii) a\mathbf{a} computes a function that is not coarsely recursively bounded.

(iii) There is a function h≤Tah\leq_T\mathbf{a} such that ρ‾({n:h(n)=g(n)})=1\overline{\rho}(\{n:h(n)=g(n)\})=1 for every recursive function gg.

Proof. (ii)⇒\Rightarrow(i). Every eventual recursive bound is also a coarse recursive bound.

(i)⇒\Rightarrow(iii). By the infinitely-often-equal characterization of hyperimmune degrees (see Monin and Nies [18]), there is a function f≤Taf\leq_T\mathbf{a} that agrees with every recursive function at infinitely many arguments. Fix an effective coding of finite sequences with recursive decoding, and use the blocks QkQ_k from (1). Set h(0)=h(1)=0h(0)=h(1)=0. If f(k)f(k) codes a sequence of length ∣Qk∣|Q_k|, use that sequence as the values of hh on QkQ_k, in increasing order of the inputs; otherwise, set hh equal to zero throughout QkQ_k. This defines a total function h≤Tfh\leq_T f.

Fix a recursive function gg. The function G(k)=code⁡(g(qk),…,g(qk+1−1))G(k)=\operatorname{code}(g(q_k),\ldots,g(q_{k+1}-1)) is recursive. By the choice of ff, f(k)=G(k)f(k)=G(k) for infinitely many kk. For every such kk, the functions hh and gg agree throughout QkQ_k. Hence Lemma 1.4(ii) gives ρ‾({n:h(n)=g(n)})=1\overline{\rho}(\{n:h(n)=g(n)\})=1.

(iii)⇒\Rightarrow(ii) is immediate. □\square

Reversing the direction of domination gives an exact density analogue of Martin’s characterization of the high degrees.

Proposition 2.2. For every Turing degree aa, the following are equivalent.

(i) aa is high.

(ii) There is a function f≤Taf \le_T a such that g≪cfg \ll_c f for every recursive function gg.

(iii) There is a function f≤Taf \le_T a such that ρ({n:f(n)≥g(n)})>0\rho(\{n : f(n) \ge g(n)\}) > 0 for every recursive function gg.

Proof. Martin’s domination theorem implies (i)⇒\Rightarrow(ii). The implication (ii)⇒\Rightarrow(iii) is immediate. It remains to prove (iii)⇒\Rightarrow(i). Let f≤Taf \le_T a witness (iii). Using the blocks QnQ_n from (1), define F(n)=max⁡{f(m):m∈Qn}F(n) = \max\{f(m) : m \in Q_n\}. Then F≤Tf≤TaF \le_T f \le_T a. Fix a recursive function gg. (iii) gives positive lower density to the set C={m:f(m)≥gblk⁡(m)}C = \{m : f(m) \ge g^{\operatorname{blk}(m)}\}. By Lemma 1.4(i) with η=0\eta= 0, we have C∩Qn≠∅C \cap Q_n \ne\varnothing for every sufficiently large nn. For each such nn, any m∈C∩Qnm \in C \cap Q_n satisfies F(n)≥f(m)≥gblk⁡(m)=g(n)F(n) \ge f(m) \ge g^{\operatorname{blk}(m)} = g(n). Thus FF dominates every recursive function, and hence aa is high. □

Following Downey, Jockusch and Stob [6], a set AA is array recursive if there is a single function g≤wtt∅′g \le_{wtt} \emptyset' that dominates every function f≤TAf \le_T A. The same construction, with the density step supplied by Lemma 1.4(i), shows that this notion is unchanged by passing to asymptotic density.

Proposition 2.3. Let A⊆ωA \subseteq\omega. The following are equivalent.

(i) AA is array recursive.

(ii) There is a function g≤wtt∅′g \le_{wtt} \emptyset' such that f≪cgf \ll_c g for every f≤TAf \le_T A.

(iii) There is a function g≤wtt∅′g \le_{wtt} \emptyset' such that ρ({n:g(n)≥f(n)})>0\rho(\{n : g(n) \ge f(n)\}) > 0 for every f≤TAf \le_T A.

Replacing lower by upper density in Proposition 2.3 yields a much larger class.

Proposition 2.4. Let A⊆ωA \subseteq\omega. The following are equivalent.

(i) ∅′̸≤TA\emptyset' \not\le_T A.

(ii) There is a function g≤wtt∅′g \le_{wtt} \emptyset' such that ρ‾({n:g(n)≥f(n)})=1\overline{\rho}(\{n : g(n) \ge f(n)\}) = 1 for every f≤TAf \le_T A.

(iii) There is a function g≤wtt∅′g \le_{wtt} \emptyset' such that ρ‾({n:g(n)≥f(n)})>0\overline{\rho}(\{n : g(n) \ge f(n)\}) > 0 for every f≤TAf \le_T A.

Proof. The implications (ii)⇒\Rightarrow(iii)⇒\Rightarrow(i) are immediate. It remains to prove (i)⇒\Rightarrow(ii). Let (Ks)s∈ω(K_s)_{s\in\omega} be the standard increasing recursive approximation to K=∅′K = \emptyset', and define m(n)=min⁡{s:Ks↾n=K↾n}m(n) = \min\{s : K_s \mathbin{\upharpoonright} n = K \mathbin{\upharpoonright} n\}. Then m≤wttKm \le_{wtt} K and no function u≤TAu \le_T A dominates mm since ∅′̸≤TA\emptyset' \not\le_T A. Put g=mblk⁡≤wtt∅′g = m^{\operatorname{blk}} \le_{wtt} \emptyset'. Fix f≤TAf \le_T A and define F(n)=max⁡{f(k):k∈Qn}F(n) = \max\{f(k) : k \in Q_n\}. Since F≤TAF \le_T A, it does not dominate mm. Hence there are infinitely many nn such that m(n)>F(n)m(n) > F(n). For each such nn, Qn⊆{k:g(k)≥f(k)}Q_n \subseteq\{k : g(k) \ge f(k)\}. Consequently, Lemma 1.4(ii) gives ρ‾({k:g(k)≥f(k)})=1\overline{\rho}(\{k : g(k) \ge f(k)\}) = 1, as required. □

The same lower-density mechanism also gives a partial-function form of lowness.

Proposition 2.5. Let A≤T∅′A \le_T \emptyset'. The following are equivalent.

(i) AA is low.

(ii) There is a function f≤T∅′f \le_T \emptyset' such that, for every partial AA-recursive function ψ\psi, (∀∞n)[ψ(n)↑ or ψ(n)<f(n)](\forall^\infty n)[\psi(n)\uparrow\ \text{or}\ \psi(n) < f(n)].

(iii) There is a function f≤T∅′f \leq_T \emptyset' such that, for every partial AA-recursive function ψ\psi, ρ({n:ψ(n)↑ or ψ(n)<f(n)})=1\rho(\{n : \psi(n)\mathord{\uparrow} \text{ or } \psi(n) < f(n)\}) = 1.

(iv) There is a function f≤T∅′f \leq_T \emptyset' such that, for every partial AA-recursive function ψ\psi, ρ({n:ψ(n)↑ or ψ(n)<f(n)})>0\rho(\{n : \psi(n)\mathord{\uparrow} \text{ or } \psi(n) < f(n)\}) > 0.

Proof. It is well-known that (i) and (ii) are equivalent, and (ii)⇒\Rightarrow(iii)⇒\Rightarrow(iv) is immediate. The implication (iv)⇒\Rightarrow(ii) follows by the same argument as (iii)⇒\Rightarrow(i) in Proposition 2.2, now applied to partial AA-recursive functions. □

Replacing lower density by upper density in the preceding proposition characterizes incompleteness. For a binary tree T⊆2<ωT \subseteq2^{<\omega}, closed under taking initial segments, its width is sup⁡n∣T∩2n∣\sup_n |T \cap2^n|; thus TT has bounded width if a single finite constant bounds the number of nodes on every level. We write [T][T] for the set of its infinite paths.

Lemma 2.6 (Kaufmann and Kummer [9]). Let A⊆ωA \subseteq\omega. If T⊆2<ωT \subseteq2^{<\omega} is an AA-r.e. binary tree of bounded width, then every X∈[T]X \in[T] is AA-recursive.

Theorem 2.7. Let A≤T∅′A \leq_T \emptyset'. The following are equivalent.

(i) A<T∅′A <_T \emptyset'.

(ii) There is a function f≤T∅′f \leq_T \emptyset' such that, for every partial function ψ\psi recursive in AA, ρ‾({n:ψ(n)↑ or ψ(n)<f(n)})=1\overline{\rho}(\{n : \psi(n)\mathord{\uparrow} \text{ or } \psi(n) < f(n)\}) = 1.

(iii) There is a function f≤T∅′f \leq_T \emptyset' such that, for every partial function ψ\psi recursive in AA, ρ‾({n:ψ(n)↑ or ψ(n)<f(n)})>0\overline{\rho}(\{n : \psi(n)\mathord{\uparrow} \text{ or } \psi(n) < f(n)\}) > 0.

Proof. The implications (ii)⇒\Rightarrow(iii)⇒\Rightarrow(i) are immediate. Conversely, suppose that A<T∅′A <_T \emptyset'. Let (Ks)s∈ω(K_s)_{s\in\omega} be the standard increasing recursive approximation to K=∅′K = \emptyset', and let m(n)=min⁡{s:Ks↾n=K↾n}m(n) = \min\{s : K_s \mathord{\upharpoonright} n = K \mathord{\upharpoonright} n\}. Put f=mblk≤wtt∅′f = m^{\mathrm{blk}} \leq_{\mathrm{wtt}} \emptyset'. Suppose, toward a contradiction, that some partial AA-recursive function ψ\psi has a failure set E={k:ψ(k)↓ and ψ(k)≥f(k)}E = \{k : \psi(k)\mathord{\downarrow} \text{ and } \psi(k) \geq f(k)\} of positive lower density δ=ρ‾(E)>0\delta= \underline{\rho}(E) > 0. By Lemma 1.4(i), for all sufficiently large nn, ∣E∩Qn∣>δ2∣Qn∣|E \cap Q_n| > \frac{\delta}{2}|Q_n|. Choose an integer rr so large that 1/r<δ/41/r < \delta/4, and put tn=⌈∣Qn∣r⌉t_n = \left\lceil\frac{|Q_n|}{r}\right\rceil. Since ∣Qn∣→∞|Q_n| \to\infty, tn<δ2∣Qn∣t_n < \frac{\delta}{2}|Q_n| for all sufficiently large nn.

For each nn, enumerate into Vn⊆2nV_n \subseteq2^n a string σ\sigma as soon as there are at least tnt_n distinct k∈Qnk \in Q_n such that ψ(k)↓\psi(k)\mathord{\downarrow} and Kψ(k)↾n=σK_{\psi(k)} \mathord{\upharpoonright} n = \sigma. The sequence (Vn)n∈ω(V_n)_{n\in\omega} is uniformly AA-r.e., and ∣Vn∣≤r|V_n| \leq r for every nn, since the sets of inputs counted for distinct strings are disjoint.

If k∈E∩Qnk \in E \cap Q_n, then ψ(k)≥f(k)=m(n)\psi(k) \geq f(k) = m(n), and therefore Kψ(k)↾n=K↾nK_{\psi(k)} \mathord{\upharpoonright} n = K \mathord{\upharpoonright} n. The preceding lower bound on ∣E∩Qn∣|E \cap Q_n| consequently implies K↾n∈VnK \mathord{\upharpoonright} n \in V_n for every sufficiently large nn. Replacing finitely many initial components by the corresponding singletons, we may assume that this holds for every nn.

Now form the AA-r.e. tree T={σ∈2<ω:(∀j≤∣σ∣) σ↾j∈Vj}T = \{\sigma\in2^{<\omega} : (\forall j \leq|\sigma|)\ \sigma\mathord{\upharpoonright} j \in V_j\}. The tree TT has width at most rr, and K∈[T]K \in[T]. By Lemma 2.6, K≤TAK \leq_T A, a contradiction. Hence (i)⇒\Rightarrow(ii).

We next consider agreement with recursive functions. A set AA is recursively semitraceable if, for every f≤TAf \leq_T A, there is a recursive function gg such that f(n)=g(n)f(n) = g(n) for infinitely many nn; see [13].

Proposition 2.8. Let A⊆ωA \subseteq\omega. The following are equivalent.

(i) AA is recursively semitraceable.

(ii) For every f≤TAf \leq_T A, there is a recursive function gg such that ρ({n:f(n)=g(n)})=1\rho(\{n : f(n) = g(n)\}) = 1. (iii) For every f≤TAf \leq_T A, there is a recursive function gg such that ρ({n:f(n)=g(n)})>0\rho(\{n : f(n) = g(n)\}) > 0.

Proof. It suffices to prove (i)⇒\Rightarrow(ii). Given f≤TAf \leq_T A, let F(n)F(n) code the finite sequence f↾qnf \upharpoonright q_n, where (qn)(q_n) is fixed in (1). By recursive semi-traceability, some recursive function F^\widehat{F} agrees with FF at infinitely many arguments. Define a recursive function gg as follows. If n≥1n \geq1 and m∈Qn−1m \in Q_{n-1}, decode F^(n)\widehat{F}(n); if it codes a sequence σ\sigma of length qnq_n, let g(m)=σ(m)g(m) = \sigma(m), and otherwise let g(m)=0g(m) = 0. Give gg arbitrary values below q0q_0. Whenever n≥1n \geq1 and F^(n)=F(n)\widehat{F}(n) = F(n), the functions ff and gg agree throughout Qn−1Q_{n-1}. Since this happens for infinitely many nn, Lemma 1.4(ii) shows that the agreement set has upper density one.

Replacing upper density by lower density forces recursiveness.

Proposition 2.9. A set A⊆ωA \subseteq\omega is recursive if and only if, for every f≤TAf \leq_T A, there is a recursive function gg such that ρ({n:f(n)=g(n)})>0\rho(\{n : f(n) = g(n)\}) > 0.

Proof. The forward implication is immediate. For the converse, suppose that AA satisfies the stated agreement condition. Fix a recursive coding σ↦⌜σ⌝\sigma\mapsto\ulcorner\sigma\urcorner of the finite binary strings by natural numbers. Let p(n)=⌜A↾n⌝p(n) = \ulcorner A \upharpoonright n \urcorner and put F=pblkF = p^{\mathrm{blk}}. By assumption, there is a recursive function gg such that, for C={m:F(m)=g(m)}C = \{m : F(m) = g(m)\}, we have δ:=ρ(C)>0\delta:= \rho(C) > 0. Choose an integer K≥1K \geq1 such that 1/K<δ1/K < \delta. By Lemma 1.4(i), for all sufficiently large nn, ∣C∩Qn∣>∣Qn∣K|C \cap Q_n| > \frac{|Q_n|}{K}. For each nn, let

Sn={σ∈2n:∣{m∈Qn:g(m)=⌜σ⌝}∣>∣Qn∣K}.S_n = \left\{\sigma\in2^n : \left|\{m \in Q_n : g(m) = \ulcorner\sigma\urcorner\}\right| > \frac{|Q_n|}{K}\right\}.

The sequence (Sn)n∈ω(S_n)_{n \in\omega} is uniformly recursive, and ∣Sn∣<K|S_n| < K for every nn, since the sets of positions counted for distinct strings are disjoint. Moreover, A↾n∈SnA \upharpoonright n \in S_n for all sufficiently large nn. Choose n0n_0 such that A↾n∈SnA \upharpoonright n \in S_n holds for every n≥n0n \geq n_0, and define a recursive binary tree

P={τ∈2<ω:(∀k)(n0≤k≤∣τ∣⇒τ↾k∈Sk)}.\mathcal{P} = \{\tau\in2^{<\omega} : (\forall k)(n_0 \leq k \leq|\tau| \Rightarrow\tau\upharpoonright k \in S_k)\}.

Then AA is an infinite path through P\mathcal{P}, while ∣P∩2n∣<K|\mathcal{P} \cap2^n| < K for every n≥n0n \geq n_0. Thus P\mathcal{P} has bounded width, so AA is recursive by Lemma 2.6.

We now turn to strong jump traceability. An r.e. trace is a uniformly r.e. sequence T=(Tn)n∈ω\mathcal{T} = (T_n)_{n \in\omega} of finite subsets of ω\omega. An order function is a positive, nondecreasing, unbounded recursive function. A trace is hh-bounded if ∣Tn∣≤h(n)|T_n| \leq h(n) for every nn, and it traces a partial function ψ\psi if ψ(n)∈Tn\psi(n) \in T_n whenever ψ(n)↓\psi(n)\downarrow. For such a function and trace, put

Hit⁡(ψ,T)={n∈dom⁡(ψ):ψ(n)∈Tn},\operatorname{Hit}(\psi,\mathcal{T}) = \{n \in\operatorname{dom}(\psi) : \psi(n) \in T_n\},
Corr⁡(ψ,T)={n:ψ(n)↑ or ψ(n)∈Tn}.\operatorname{Corr}(\psi,\mathcal{T}) = \{n : \psi(n)\uparrow\text{ or } \psi(n) \in T_n\}.

Thus T\mathcal{T} traces ψ\psi precisely when Corr⁡(ψ,T)=ω\operatorname{Corr}(\psi,\mathcal{T}) = \omega. Recall that AA is strongly jump traceable if for every order function hh, every partial AA-recursive function has an hh-bounded r.e. trace; see [7].

Theorem 2.10. A set AA is strongly jump traceable if and only if for every order function hh and every partial AA-recursive function ψ\psi, there is an hh-bounded r.e. trace T\mathcal{T} such that ρ(Corr⁡(ψ,T))>0\rho(\operatorname{Corr}(\psi,\mathcal{T})) > 0.

Proof. The forward implication is immediate. Conversely, fix an order function gg and a partial AA-recursive function ψ\psi. To respect the prescribed bound gg, we use a slower auxiliary order and retain only values that occur frequently within each block. Let b(n)=max⁡{1,⌊g(n)⌋}b(n)=\max\{1,\lfloor\sqrt{g(n)}\rfloor\}, and put a=bblka=b^{\mathrm{blk}}. Applying the assumed density condition to aa and ψblk\psi^{\mathrm{blk}}, there is an aa-bounded r.e. trace V=(Vm)m∈ω\mathcal{V}=(V_m)_{m\in\omega} such that C=Corr⁡(ψblk,V)C=\operatorname{Corr}(\psi^{\mathrm{blk}},\mathcal{V}) has positive lower density. Put δ=ρ(C)>0\delta=\rho(C)>0. By Lemma 1.4(i), for all sufficiently large nn, ∣C∩Qn∣>12∣Qn∣|C\cap Q_n|>\frac{1}{2}|Q_n|. If n∈dom⁡(ψ)n\in\operatorname{dom}(\psi), the members of C∩QnC\cap Q_n are precisely the m∈Qnm\in Q_n for which ψ(n)∈Vm\psi(n)\in V_m. Let kn=⌈∣Qn∣b(n)g(n)⌉k_n=\left\lceil\frac{|Q_n|b(n)}{g(n)}\right\rceil and enumerate into SnS_n each value yy that appears in at least knk_n distinct components VmV_m with m∈Qnm\in Q_n. The sequence (Sn)n∈ω(S_n)_{n\in\omega} is uniformly r.e., and

∣Sn∣kn≤∑m∈Qn∣Vm∣≤∣Qn∣b(n)≤g(n)kn.|S_n|k_n\leq\sum_{m\in Q_n}|V_m|\leq|Q_n|b(n)\leq g(n)k_n.

Consequently, ∣Sn∣≤g(n)|S_n|\leq g(n). Moreover, kn∣Qn∣≤b(n)g(n)+1∣Qn∣⟶0\frac{k_n}{|Q_n|}\leq\frac{b(n)}{g(n)}+\frac{1}{|Q_n|}\longrightarrow0. It follows from the preceding lower bound on ∣C∩Qn∣|C\cap Q_n| that ψ(n)∈Sn\psi(n)\in S_n for almost every n∈dom⁡(ψ)n\in\operatorname{dom}(\psi). After replacing finitely many components by singletons containing the corresponding convergent values, (Sn)n∈ω(S_n)_{n\in\omega} becomes a gg-bounded r.e. trace for ψ\psi. Since gg and ψ\psi were arbitrary, AA is strongly jump traceable. □\square

To formulate an upper-density analogue, we first need to account for the possible sparsity of the domain. Since Hit⁡(ψ,T)⊆dom⁡(ψ)\operatorname{Hit}(\psi,\mathcal{T})\subseteq\operatorname{dom}(\psi), an infinite domain of density zero prevents even a trace that captures every defined value from having positive upper density of hits. We therefore pass to ψblk\psi^{\mathrm{blk}}; its domain contains QnQ_n for every n∈dom⁡(ψ)n\in\operatorname{dom}(\psi), and hence has upper density one whenever dom⁡(ψ)\operatorname{dom}(\psi) is infinite, by Lemma 1.4(ii). We must also use Hit⁡\operatorname{Hit} rather than Corr⁡\operatorname{Corr}, so that undefined values do not count as successes. Recall that a total function dd is diagonally non-recursive, or DNRDNR, if d(e)≠Φe(e)d(e)\ne\Phi_e(e) whenever Φe(e)↓\Phi_e(e)\mathord{\downarrow}. A degree is non-DNR if it computes no DNRDNR function. We have the following characterization due to Kjos-Hanssen, Merkle, and Stephan [12] (see Hölzl and Merkle [8 Theorems 10 and 20]). A set AA computes no DNRDNR function if and only if there is an order function bb such that every total function f≤TAf\leq_T A has a bb-bounded r.e. trace (Vn)n∈ω(V_n)_{n\in\omega} with f(n)∈Vnf(n)\in V_n for infinitely many nn. Moreover, if AA computes no DNRDNR function, then for every order function bb and every partial AA-recursive function ψ\psi with infinite domain, there is a bb-bounded r.e. trace (Vn)n∈ω(V_n)_{n\in\omega} such that ψ(n)∈Vn\psi(n)\in V_n for infinitely many n∈dom⁡(ψ)n\in\operatorname{dom}(\psi).

The following proposition follows readily from these results by a block argument.

Proposition 2.11. Let A⊆ωA\subseteq\omega. The following are equivalent.

(i) AA computes no DNRDNR function.

(ii) For every order function hh and every partial AA-recursive function ψ\psi with infinite domain, there is an hh-bounded r.e. trace T\mathcal{T} such that ρ‾(Hit⁡(ψblk,T))=1\overline{\rho}(\operatorname{Hit}(\psi^{\mathrm{blk}},\mathcal{T}))=1.

(iii) For every order function hh and every partial AA-recursive function ψ\psi with infinite domain, there is an hh-bounded r.e. trace T\mathcal{T} such that ρ‾(Hit⁡(ψblk,T))>0\overline{\rho}(\operatorname{Hit}(\psi^{\mathrm{blk}},\mathcal{T}))>0.

Let μ\mu denote the usual product measure on 2ω2^\omega. Recall that a set AA is almost-everywhere dominating (a.e.d.) if, for μ\mu-almost every X∈2ωX\in2^\omega and every total function g≤TXg\leq_T X, there is a function f≤TAf\leq_T A which dominates gg. It is uniformly almost-everywhere dominating (u.a.e.d.) if one function f≤TAf\leq_T A works for almost every XX and all total g≤TXg \le_T X; see Dobrinen and Simpson [4]. For a Turing functional Φ\Phi, let Tot⁡(Φ)={X∈2ω:ΦX is total}\operatorname{Tot}(\Phi) = \{X \in2^\omega: \Phi^X \text{ is total}\}. If ff is total, define the domination set

DΦ,f(X)={n:ΦX(n)↓ and ΦX(n)≤f(n)}.D_{\Phi,f}(X) = \{n : \Phi^X(n)\downarrow\text{ and } \Phi^X(n) \le f(n)\}.

Definition 2.12 (Kjos-Hanssen [11]). A set AA is positive-measure dominating (p.m.d.) if, for every Φ\Phi with μ(Tot⁡(Φ))>0\mu(\operatorname{Tot}(\Phi)) > 0, there is an f≤TAf \le_T A such that μ({X∈Tot⁡(Φ):f dominates ΦX})>0\mu(\{X \in\operatorname{Tot}(\Phi) : f \text{ dominates } \Phi^X\}) > 0.

Theorem 2.13 (Kjos-Hanssen, Miller, and Solomon [14]). For every set AA, the following are equivalent.

(i) AA is u.a.e.d.

(ii) AA is a.e.d.

(iii) AA is p.m.d.

We now replace eventual domination in the positive-measure definition by a density condition.

Proposition 2.14. For every set AA, the following are equivalent.

(i) AA is a.e.d.

(ii) For every Turing functional Φ\Phi with μ(Tot⁡(Φ))>0\mu(\operatorname{Tot}(\Phi)) > 0, there is an f≤TAf \le_T A such that μ({X∈Tot⁡(Φ):ρ(DΦ,f(X))>0})>0\mu(\{X \in\operatorname{Tot}(\Phi) : \rho(D_{\Phi,f}(X)) > 0\}) > 0.

(iii) There is an f≤TAf \le_T A such that

μ({X:(∀g≤TX) ρ({n:g(n)≤f(n)})>0})=1.\mu(\{X : (\forall g \le_T X)\ \rho(\{n : g(n) \le f(n)\}) > 0\}) = 1.

Proof. (i)⇒\Rightarrow(iii). By Theorem 2.13, AA is u.a.e.d. and hence (iii) holds.

(iii)⇒\Rightarrow(ii) is immediate.

(ii)⇒\Rightarrow(i). Assume (ii) and fix Φ\Phi with μ(Tot⁡(Φ))>0\mu(\operatorname{Tot}(\Phi)) > 0. Let Φ^X(m)=max⁡i≤mΦX(i)\widehat{\Phi}^X(m) = \max_{i \le m} \Phi^X(i), with the value defined only when all computations on the right converge. Then Tot⁡(Φ^)=Tot⁡(Φ)\operatorname{Tot}(\widehat{\Phi}) = \operatorname{Tot}(\Phi). Applying the density condition to Φ^\widehat{\Phi}, choose f≤TAf \le_T A and a positive-measure set P⊆Tot⁡(Φ)P \subseteq\operatorname{Tot}(\Phi) such that CX={m:f(m)≥Φ^X(m)}C_X = \{m : f(m) \ge\widehat{\Phi}^X(m)\} has positive lower density for every X∈PX \in P. Define F≤TAF \le_T A by F(n)=max⁡{f(m):m∈Qn}F(n) = \max\{f(m) : m \in Q_n\}. By Lemma 1.4(i), for every X∈PX \in P, the set CXC_X meets QnQ_n for all sufficiently large nn. Choosing m∈CX∩Qnm \in C_X \cap Q_n and using m≥qn≥nm \ge q_n \ge n gives F(n)≥f(m)≥Φ^X(m)≥ΦX(n)F(n) \ge f(m) \ge\widehat{\Phi}^X(m) \ge\Phi^X(n). Hence FF witnesses p.m.d. for Φ\Phi. Since Φ\Phi was arbitrary, AA is p.m.d., therefore a.e.d. by Theorem 2.13. □

Replacing lower density by upper density in Proposition 2.14(iii) gives hyperimmunity.

Proposition 2.15. For every set AA, the following are equivalent.

(i) AA has hyperimmune degree.

(ii) There is an f≤TAf \le_T A such that

μ({X:(∀g≤TX) ρ‾({n:g(n)≤f(n)})=1})=1.\mu(\{X : (\forall g \le_T X)\ \overline{\rho}(\{n : g(n) \le f(n)\}) = 1\}) = 1.

(iii) There is an f≤TAf \le_T A such that

μ({X:(∀g≤TX) ρ‾({n:g(n)≤f(n)})>0})=1.\mu(\{X : (\forall g \le_T X)\ \overline{\rho}(\{n : g(n) \le f(n)\}) > 0\}) = 1.

Proof. Suppose first that AA has hyperimmune degree, and choose a hyperimmune function h≤TAh \le_T A. For almost every XX, the function hh remains XX-hyperimmune. Indeed, if for some functional Φ\Phi and some kk the class of XX satisfying ΦX(n)↓≥h(n)\Phi^X(n)\downarrow\ge h(n) for every n≥kn \ge k had positive measure, then, inside a cylinder on which this class has relative measure greater than 3/43/4, one could compute an eventual bound for hh, a contradiction. Taking the countable union over all functionals Φ\Phi and all kk proves the assertion. Put f=hblkf=h^{\mathrm{blk}}. For every such XX and every g≤TXg\leq_T X, h(n)>max⁡{g(m):m∈Qn}h(n)>\max\{g(m):m\in Q_n\} for infinitely many nn, and for each such nn the whole block QnQ_n is contained in {m:g(m)≤f(m)}\{m:g(m)\leq f(m)\}. By Lemma 1.4(ii), this set has upper density one. Thus (i) implies (ii), while (ii) implies (iii) and (iii) implies (i) trivially.

The methods used in this section apply more generally. Similar arguments yield density versions of other notions, including recursive traceability, r.e. traceability, and jump traceability. We omit the details.

Bounded-threshold domination and superhighness

We now answer the question of Kjos-Hanssen and Nies [10].

Theorem 3.1 (with Liang Yu). A set AA is superhigh if and only if there are functions h∈BLR⁡(A)h\in\operatorname{BLR}(A) and f≤TAf\leq_T A such that

(∀e∈Tot⁡)(∀n≥h(e)) Φe(n)≤f(n).(2)(\forall e\in\operatorname{Tot})(\forall n\geq h(e))\ \Phi_e(n)\leq f(n). \tag*{(2)}

Proof. Suppose first that h∈BLR⁡(A)h\in\operatorname{BLR}(A) and f≤TAf\leq_T A satisfy (2). Choose an AA-recursive approximation H(e,s)H(e,s) to h(e)h(e) and a recursive function gg such that ∣{s:H(e,s)≠H(e,s+1)}∣<g(e)|\{s:H(e,s)\ne H(e,s+1)\}|<g(e) for every ee. Replacing HH by H^(e,s)=max⁡t≤sH(e,t)\widehat{H}(e,s)=\max_{t\leq s}H(e,t), and hh by h^(e)=lim⁡sH^(e,s)\widehat{h}(e)=\lim_s\widehat{H}(e,s), we may assume without loss of generality that H(e,s)≤H(e,s+1)H(e,s)\leq H(e,s+1) for all e,se,s. Indeed, h^∈BLR⁡(A)\widehat{h}\in\operatorname{BLR}(A) and h^(e)≥h(e)\widehat{h}(e)\geq h(e), so (2) remains true.

Let θ\theta be a recursive function such that Φθ(e)(n)\Phi_{\theta(e)}(n) is the least stage tt, if it exists, for which Φe(m)[t]↓\Phi_e(m)[t]\mathord{\downarrow} for all m≤nm\leq n. Thus, if Φe\Phi_e is total, then Φθ(e)\Phi_{\theta(e)} is total, and Φe(m)[Φθ(e)(n)]↓\Phi_e(m)[\Phi_{\theta(e)}(n)]\mathord{\downarrow} for all m≤nm\leq n.

We define an AA-recursive binary approximation T(n,s)T(n,s) to Tot⁡\operatorname{Tot}. Put T(n,0)=0T(n,0)=0. For s>0s>0, let ks=H(θ(n),s)k_s=H(\theta(n),s). If either ks≥sk_s\geq s or ks>H(θ(n),s−1)k_s>H(\theta(n),s-1), put T(n,s)=0T(n,s)=0. Otherwise, put T(n,s)=1T(n,s)=1 exactly when

(∀m≤ks) Φn(m)[f(ks)]↓(\forall m\leq k_s)\ \Phi_n(m)[f(k_s)]\mathord{\downarrow}

and

(∀m)(ks<m≤s⇒Φn(m)[f(m)]↓);(\forall m)(k_s<m\leq s\Rightarrow\Phi_n(m)[f(m)]\mathord{\downarrow});

if either condition fails, put T(n,s)=0T(n,s)=0.

We first check that lim⁡sT(n,s)=Tot⁡(n)\lim_s T(n,s)=\operatorname{Tot}(n). If Φn\Phi_n is total, then Φθ(n)\Phi_{\theta(n)} is total. Let k=h(θ(n))k=h(\theta(n)). By (2) applied to θ(n)\theta(n), for every m≥km\geq k we have Φθ(n)(m)≤f(m)\Phi_{\theta(n)}(m)\leq f(m). Hence, for all sufficiently large ss, after H(θ(n),⋅)H(\theta(n),\mathord\cdot) has stabilized at kk, both displayed conditions hold, and therefore T(n,s)=1T(n,s)=1. If Φn\Phi_n is not total, then it is clear that for all sufficiently large stages ss, one of the two displayed conditions fails. And therefore T(n,s)=0T(n,s)=0.

Finally, TT has a recursive mind-change bound. If H(θ(n),⋅)H(\theta(n),\mathord\cdot) changes cc times, then c<g(θ(n))c<g(\theta(n)). On each interval on which H(θ(n),s)H(\theta(n),s) is constant, say with value kk, the sequence T(n,s)T(n,s) has the form $010*$: the reset rule and the condition k≥sk\geq s initially force the value 00, and thereafter the tests only acquire additional conjuncts as ss increases. Thus there are at most two changes within each of the $c+1 constant intervals, and at most one additional change at each of their cc boundaries. Consequently,

∣{s:T(n,s)≠T(n,s+1)}∣≤2(c+1)+c=3c+2<3g(θ(n))+3.\lvert\{s : T(n,s) \ne T(n,s+1)\}\rvert\le2(c+1)+c = 3c+2 < 3g(\theta(n))+3.

By Lemma 1.6, Tot⁡≤ttA′\operatorname{Tot} \le_{\mathrm{tt}} A' and AA is superhigh.

Conversely, suppose that AA is superhigh. Fix a functional Γ\Gamma and a recursive function λ\lambda such that, for every ee, Tot⁡(e)=ΓA′↾λ(e)(e)\operatorname{Tot}(e)=\Gamma^{A'\upharpoonright\lambda(e)}(e) and Γσ(e)∈{0,1}\Gamma^\sigma(e)\in\{0,1\} for every finite string σ\sigma of length λ(e)\lambda(e).

Let As′A'_s be the standard AA-recursive approximation to A′A'. We define H≤TAH\le_T A and f≤TAf\le_T A in stages. At stage 00, put H(i,0)=iH(i,0)=i for every ii.

At stage s>0s>0, first update HH. If there is no e<se<s such that As′↾λ(e)≠As−1′↾λ(e)A'_s\upharpoonright\lambda(e)\ne A'_{s-1}\upharpoonright\lambda(e), put H(i,s)=H(i,s−1)H(i,s)=H(i,s-1) for all ii. Otherwise, let ese_s be the least such ee, and define

H(i,s)={H(i,s−1),if i<es,max⁡{H(i,s−1),s+i},if i≥es.(3)H(i,s)= \begin{cases} H(i,s-1), & \text{if } i<e_s,\\ \max\{H(i,s-1),s+i\}, & \text{if } i\ge e_s. \end{cases} \tag*{(3)}

Thus H(i,⋅)H(i,\mathord{\cdot}) is nondecreasing for every ii.

We next define ff. At stage ss, let nn be the least number such that f(n)f(n) has not yet been defined. Let

En,s={e<s:H(e,s)≤n and ΓAs′↾λ(e)(e)=1}.E_{n,s}=\{e<s:H(e,s)\le n\text{ and }\Gamma^{A'_s\upharpoonright\lambda(e)}(e)=1\}.

If Φe(n)[s]↓\Phi_e(n)[s]\downarrow for every e∈En,se\in E_{n,s}, define

f(n)=max⁡({0}∪{Φe(n)[s]:e∈En,s}).f(n)=\max\bigl(\{0\}\cup\{\Phi_e(n)[s]:e\in E_{n,s}\}\bigr).

Otherwise define no new value of ff at stage ss.

We verify that the construction works. First, h(i)=lim⁡sH(i,s)h(i)=\lim_s H(i,s) exists for every ii. Indeed, H(i,⋅)H(i,\mathord{\cdot}) can change only at stages at which, for some e≤ie\le i, the finite string As′↾λ(e)A'_s\upharpoonright\lambda(e) changes. For each such ee, this finite string changes at most λ(e)\lambda(e) times. Thus

∣{s:H(i,s)≠H(i,s+1)}∣≤∑e≤iλ(e).\lvert\{s:H(i,s)\ne H(i,s+1)\}\rvert\le\sum_{e\le i}\lambda(e).

Since the construction of HH uses only the oracle AA, it follows that h∈BLR(A)h\in\mathrm{BLR}(A).

Next we show that ff is total. We argue by induction on nn. Assume that f↾nf\upharpoonright n has already been defined. Since H(i,0)=iH(i,0)=i and H(i,⋅)H(i,\mathord{\cdot}) is nondecreasing, if H(i,s)≤nH(i,s)\le n for some ss, then i≤ni\le n. Choose a stage s0>ns_0>n after which all strings As′↾λ(i)A'_s\upharpoonright\lambda(i) with i≤ni\le n and all values H(i,s)H(i,s) with i≤ni\le n have stabilized. Then, for all s≥s0s\ge s_0, the set En,sE_{n,s} is a fixed finite set consisting only of indices ee for which Tot⁡(e)=1\operatorname{Tot}(e)=1. Thus every Φe\Phi_e with e∈En,se\in E_{n,s} is total, and there is a later stage s1s_1 such that Φe(n)[s1]↓\Phi_e(n)[s_1]\downarrow for every ee in this finite set. If f(n)f(n) has not already been defined, the construction defines it at stage s1s_1. Therefore ff is total and f≤TAf\le_T A.

It remains to verify (2). Fix e∈Tot⁡e\in\operatorname{Tot} and n≥h(e)n\ge h(e). Let tt be the stage at which f(n)f(n) is defined. By construction, t>nt>n. Since H(e,⋅)H(e,\mathord{\cdot}) is nondecreasing and has limit h(e)h(e), H(e,t)≤h(e)≤nH(e,t)\le h(e)\le n. Also H(e,0)=eH(e,0)=e, so e≤h(e)≤n<te\le h(e)\le n<t.

We claim that At′↾λ(e)=A′↾λ(e)A'_t\upharpoonright\lambda(e)=A'\upharpoonright\lambda(e). Otherwise, this string would change at some later stage u>tu>t. At that stage the least changed index eue_u would be at most ee, and the update rule (3) would give H(e,u)≥u+e>nH(e,u)\ge u+e>n, contradicting the fact that the nondecreasing sequence H(e,⋅)H(e,\mathord{\cdot}) has final value at most nn.

Since Φe\Phi_e is total, e∈En,te\in E_{n,t}. When f(n)f(n) was defined at stage tt, the construction required Φe(n)[t]↓\Phi_e(n)[t]\downarrow for every e∈En,te\in E_{n,t} and Φe(n)≤f(n)\Phi_e(n)\le f(n). Since n≥h(e)n\ge h(e) was arbitrary, (2) holds. □\square

The bounded-threshold characterization also gives an effective strengthening of maximality. Martin [15] characterized the high r.e. degrees as exactly those containing maximal sets. An r.e. coinfinite set AA is maximal if its complement is cohesive: for every ee, either Aˉ∩We\bar{A} \cap W_e or Aˉ∖We\bar{A} \setminus W_e is finite. We obtain a stronger condition by requiring a bounded-limit threshold for this eventual homogeneity. Call an r.e. coinfinite set AA supermaximal if there is a function f∈BLR⁡(A)f \in\operatorname{BLR}(A) such that

(∀e)(∀n>m>f(e)) [n,m∉A⟹(n∈We⟺m∈We)].(4)(\forall e)(\forall n > m > f(e))\ [n,m \notin A \Longrightarrow(n \in W_e \Longleftrightarrow m \in W_e)]. \tag*{(4)}

Thus every supermaximal set is maximal.

Theorem 3.2. Every supermaximal set is superhigh, and every superhigh r.e. degree contains a supermaximal set.

Proof. First suppose that AA is supermaximal, witnessed by f∈BLR⁡(A)f \in\operatorname{BLR}(A). Choose a total AA-recursive approximation F(e,s)→f(e)F(e,s) \to f(e) whose number of changes is bounded by a recursive function r(e)r(e). Fix a recursive function θ\theta such that

Wθ(e)={[0,∣We∣),if We is finite,ω,if We is infinite.W_{\theta(e)} = \begin{cases} [0, |W_e|), & \text{if } W_e \text{ is finite},\\ \omega, & \text{if } W_e \text{ is infinite}. \end{cases}

Using AA, define x(e,s)=min⁡{x>F(θ(e),s):x∉A}x(e,s) = \min\{x > F(\theta(e),s) : x \notin A\}. Also define T(e,s)=1Wθ(e),s(x(e,s))T(e,s) = \mathbf{1}_{W_{\theta(e),s}}(x(e,s)). These functions are total because AA is coinfinite. On each interval on which F(θ(e),s)F(\theta(e),s) is constant, x(e,s)x(e,s) is constant and T(e,s)T(e,s) changes at most once. Counting changes between such intervals, T(e,s)T(e,s) changes at most 2r(θ(e))+12r(\theta(e)) + 1 times. Define xe=min⁡{x>f(θ(e)):x∉A}x_e = \min\{x > f(\theta(e)) : x \notin A\}. If WeW_e is infinite, then T(e,s)→1T(e,s) \to1. If WeW_e is finite, then xe∉Wθ(e)x_e \notin W_{\theta(e)}: otherwise (4) would put every element of Aˉ\bar{A} greater than xex_e into the finite set Wθ(e)W_{\theta(e)}. Thus T(e,s)→0T(e,s) \to0 in this case. Consequently, 1INF∈BLR⁡(A)\mathbf{1}_{\mathrm{INF}} \in\operatorname{BLR}(A). By Lemma 1.6, INF≤ttA′\mathrm{INF} \leq_{\mathrm{tt}} A', so AA is superhigh.

For the converse, let DD be an r.e. set of the prescribed superhigh degree. By Theorem 3.1, choose d≤TDd \leq_T D and h∈BLR⁡(D)h \in\operatorname{BLR}(D) such that

(∀j∈Tot⁡)(∀x≥h(j)) Φj(x)≤d(x).(5)(\forall j \in\operatorname{Tot})(\forall x \geq h(j))\ \Phi_j(x) \leq d(x). \tag*{(5)}

We also use BLR⁡(D)=BLR⁡(∅′)\operatorname{BLR}(D) = \operatorname{BLR}(\varnothing'): since D≤T∅′D \leq_T \varnothing' is superhigh, Cole and Simpson [3 Theorem 6.12], applied with X=∅′X = \varnothing' and Y=DY = D, give BLR⁡(∅′)⊆BLR⁡(D)\operatorname{BLR}(\varnothing') \subseteq\operatorname{BLR}(D). The reverse inclusion follows from D≤T∅′D \leq_T \varnothing'. Fix a recursive approximation ds(x)→d(x)d_s(x) \to d(x) with a DD-recursive convergence modulus, see [21].

We construct an r.e. set AA by defining an increasing sequence of finite sets (As)s∈ω(A_s)_{s \in\omega}, with A=⋃sAsA = \bigcup_s A_s. Our aim is to make all sufficiently large elements of Aˉ\bar{A} agree on membership in each WeW_e, with a threshold in BLR⁡(A)\operatorname{BLR}(A). To organize these requirements, define the ii-state of xx at stage ss by νi(x,s)=∑j≤i2i−j1Wj,s(x)\nu_i(x,s) = \sum_{j \leq i} 2^{i-j}\mathbf{1}_{W_{j,s}}(x). This is the binary code of the membership vector (1W0,s(x),…,1Wi,s(x))(\mathbf{1}_{W_{0,s}}(x), \ldots, \mathbf{1}_{W_{i,s}}(x)). Numerical comparison of states therefore orders these lexicographically, giving priority to the smaller indices. For each fixed ii and xx, the state is nondecreasing in ss and takes values in {0,…,2i+1−1}\{0,\ldots,2^{i+1}-1\}. Moreover, for e≤ie \leq i, νe(x,s)=⌊νi(x,s)2i−e⌋\nu_e(x,s) = \left\lfloor\frac{\nu_i(x,s)}{2^{i-e}} \right\rfloor. Thus replacing a marker by one with at least as large an ii-state does not decrease any of its ee-states for e≤ie \leq i. We use this ordering to select the markers that remain outside AA.

At any point in stage ss, the current markers are the numbers in [0,s][0,s] that have not yet been enumerated into AA. Write their increasing list as M={m0<⋯<mk−1}M = \{m_0 < \cdots< m_{k-1}\}; the rank of mim_i is its current index ii in this list. A tail action at rank i<ki<k is defined as follows. Let

ℓ=min⁡{j:i≤j<k and νi(mj,s)=max⁡i≤t<kνi(mt,s)}.\ell=\min\{j:i\leq j<k\text{ and }\nu_i(m_j,s)=\max_{i\leq t<k}\nu_i(m_t,s)\}.

Enumerate every element of {mi,…,mk−1}∖{mℓ}\{m_i,\ldots,m_{k-1}\}\setminus\{m_\ell\} into AA. After each action, ranks are reassigned according to the new increasing list; all subsequent actions use these updated ranks.

Put A−1=D−1=∅A_{-1}=D_{-1}=\varnothing and d−1(x)=0d_{-1}(x)=0 for every xx. At stage ss, start with the marker list M=[0,s]∖As−1M=[0,s]\setminus A_{s-1} and perform the following steps.

  1. Coding actions. Process the elements n∈Ds∖Ds−1n\in D_s\setminus D_{s-1} in increasing order. For each such nn, perform a tail action at rank nn if that rank is currently present; otherwise do nothing.

  1. Ordinary action. Using the current list m0<⋯<mk−1m_0<\cdots<m_{k-1} after all coding actions, declare rank i<ki<k eligible if there is a jj with i<j<ki<j<k such that νi(mj,s)>νi(mi,s)\nu_i(m_j,s)>\nu_i(m_i,s), and s≤ds(mi)∨ds(mi)≠ds−1(mi)s\leq d_s(m_i)\vee d_s(m_i)\ne d_{s-1}(m_i). If any rank is eligible, perform one tail action at the least eligible rank. Otherwise perform no ordinary action.

This completes stage ss.

Claim 1. There are only finitely many actions at each rank, and AA is coinfinite. The rank of any marker that survives an action cannot increase.

Proof of the claim. We argue inductively on ii. After the last action at a smaller rank and the last coding action at rank ii, every action at rank ii strictly increases the ii-state of its marker. Between actions, that state cannot decrease. Since it takes at most 2i+12^{i+1} possible values, there are only finitely many such actions. Once the smaller ranks have stabilized, new numbers ensure that rank ii is eventually present and stabilizes as well. Hence AA is coinfinite. Finally, an action only removes markers, so the rank of a surviving marker cannot increase. □

Write A‾={c0<c1<c2<⋯ }\overline{A}=\{c_0<c_1<c_2<\cdots\}.

Claim 2. A≡TDA\equiv_T D.

Proof of the claim. For A≤TDA\leq_T D, fix zz. An ordinary action that enumerates zz is triggered by a marker x≤zx\leq z. Using DD, find a stage beyond the convergence stages and final values of all ds(x)d_s(x) for x≤zx\leq z. Thereafter, none of these markers can satisfy the condition s≤ds(x)∨ds(x)≠ds−1(x)s\leq d_s(x)\vee d_s(x)\ne d_{s-1}(x) for an ordinary action. A coding action that affects zz must have rank at most zz, so DD also computes a stage beyond all such coding actions. Taking a stage beyond these bounds and zz decides whether z∈Az\in A. Conversely, if nn enters DD at stage ss, then after its coding action at most n+1n+1 current markers remain in [0,s][0,s]. The same bound holds if rank nn is absent. Subsequent actions cannot increase this number, so cn+1>sc_{n+1}>s. Thus D(n)=Dcn+1(n)D(n)=D_{c_{n+1}}(n), which proves D≤TAD\leq_T A.

We now find a threshold in BLR⁡(A)\operatorname{BLR}(A) above which all elements of A‾\overline{A} have the same ee-state. Fix ee and q<2e+1q<2^{e+1}. We record the numbers that appear as markers with ee-state at least qq. More precisely, at each stage ss, before any coding or ordinary action, the current markers are exactly [0,s]∖As−1[0,s]\setminus A_{s-1}. Enumerate each of these markers yy with νe(y,s)≥q\nu_e(y,s)\geq q into Re,qR_{e,q}. To use the domination property (5), we also need a recursive search for a stage at which a suitable marker is present. On input xx, let Φa(e,q)\Phi_{a(e,q)} simulate the construction until the first stage s≥xs \geq x at which the initial marker list [0,s]∖As−1[0,s] \setminus A_{s-1} contains a number y>xy > x with νe(y,s)≥q\nu_e(y,s) \geq q. The function outputs this stage ss; if no such stage exists, it is undefined. The following Claim 3 is immediate.

Claim 3. The sets Re,qR_{e,q} are uniformly r.e., and the indices a(e,q)a(e,q) can be chosen recursively. If Re,qR_{e,q} is infinite, then Φa(e,q)\Phi_{a(e,q)} is total.

Define νe(x)=lim⁡sνe(x,s)\nu_e(x) = \lim_s \nu_e(x,s).

Claim 4. For every ee and q<2e+1q < 2^{e+1}, if Re,qR_{e,q} is infinite, x∈A‾x \in\overline{A}, x>cex > c_e and x≥h(a(e,q))x \geq h(a(e,q)), then νe(x)≥q\nu_e(x) \geq q.

Proof of the claim. Suppose otherwise, and put s0=Φa(e,q)(x)s_0 = \Phi_{a(e,q)}(x). Then s0≤d(x)s_0 \leq d(x) by (5). At stage s0s_0 there is a marker y>xy > x of ee-state at least qq, whereas νe(x,s)<q\nu_e(x,s) < q at every stage. Since x>cex > c_e and its rank cannot increase, its current rank is greater than ee at every stage at which it is present.

As long as xx survives, a marker greater than xx of ee-state at least qq continues to exist. Indeed, a tail action beginning after xx either leaves such a witness untouched or replaces it by a marker whose ee-state is at least as large. An action beginning at or before xx cannot retain xx: if its rank is at least ee, maximality of the retained state rules this out; if its rank is less than ee, retaining xx would give it a rank less than ee, contrary to x>cex > c_e.

If ds0(x)≥s0d_{s_0}(x) \geq s_0, then xx satisfies the condition s≤ds(x)∨ds(x)≠ds−1(x)s \leq d_s(x) \lor d_s(x) \ne d_{s-1}(x) at stage s0s_0. Otherwise, ds0(x)<s0≤d(x)d_{s_0}(x) < s_0 \leq d(x), so ds(x)d_s(x) changes at a later stage, when the same condition is satisfied. At that stage, the persistent witness makes xx eligible for an ordinary action. The action at the least eligible rank therefore begins at or before xx and cannot retain it, a contradiction. This proves the claim. □\square

Claim 5. There is a function b∈BLR(D)b \in\mathrm{BLR}(D) such that, for every ee and q<2e+1q < 2^{e+1}, if Re,qR_{e,q} is finite, then Re,q⊆[0,b(e,q)]R_{e,q} \subseteq[0,b(e,q)].

Proof of the claim. For an approximation with at most one change, initially output 0 and use ∅\emptyset to search for a number bb satisfying Re,q⊆[0,b]R_{e,q} \subseteq[0,b]. On finding one, output it forever. If there is no such bound, the approximation stays at 0. This defines b∈BLR(∅)=BLR(D)b \in\mathrm{BLR}(\emptyset) = \mathrm{BLR}(D) with the required property. □\square

Claim 6. The function

f(e)=max⁡({ce}∪{h(a(e,q)),b(e,q):q<2e+1})f(e) = \max\left(\{c_e\} \cup\{h(a(e,q)), b(e,q) : q < 2^{e+1}\}\right)

belongs to BLR(A)\mathrm{BLR}(A) and witnesses that AA is supermaximal.

Proof of the claim. Since the function e↦cee \mapsto c_e is DD-recursive and the maximum has a recursively bounded number of terms, their bounded-change approximations give f∈BLR(D)=BLR(A)f \in\mathrm{BLR}(D) = \mathrm{BLR}(A). Fix ee, q<2e+1q < 2^{e+1}, and x∈A‾x \in\overline{A} with x>f(e)x > f(e). Suppose first that Re,qR_{e,q} is infinite. Since x>cex > c_e and x≥h(a(e,q))x \geq h(a(e,q)), Claim 4 gives νe(x)≥q\nu_e(x) \geq q. Now suppose that Re,qR_{e,q} is finite. If νe(x)≥q\nu_e(x) \geq q, then the permanent marker xx is eventually recorded in Re,qR_{e,q}. But Re,q⊆[0,b(e,q)]R_{e,q} \subseteq[0,b(e,q)] and x>b(e,q)x > b(e,q), a contradiction. Hence νe(x)<q\nu_e(x) < q in this case. Whether Re,qR_{e,q} is infinite is independent of xx, so all elements of A‾\overline{A} greater than f(e)f(e) have the same ee-state. In particular, they agree on membership in WeW_e. Thus AA is supermaximal. □\square

Claims 2 and 6 complete the proof. □\square

As a corollary, supermaximality is strictly stronger than maximality since there are high r.e. degrees that are not superhigh [17].

The density version of Martin’s theorem, Proposition 2.2, shows that coarse domination characterizes highness. The following proposition characterizes superhighness by requiring effective control of how quickly the density of successful domination approaches one, or of when it stays above any fixed positive density. For a total function ff and an index ee, put

Def={n:Φe(n)↓ and Φe(n)≤f(n)}.D_e^f = \{n : \Phi_e(n)\downarrow\text{ and } \Phi_e(n) \le f(n)\}.

Proposition 3.3. Fix a rational number α\alpha with 0<α<10 < \alpha< 1. For every set AA, the following are equivalent.

  1. AA is superhigh.

  2. There are a total function f≤TAf \le_T A and a function m:ω2→ωm:\omega^2 \to\omega with m∈BLR(A)m \in\mathrm{BLR}(A) such that, for every e∈Tote \in\mathrm{Tot}, every k≥1k \ge1, and every N≥max⁡{1,m(e,k)}N \ge\max\{1,m(e,k)\}, ρN(Def)≥1−2−k\rho_N(D_e^f) \ge1 - 2^{-k}.

  3. There are a total function f≤TAf \le_T A and a function h∈BLR(A)h \in\mathrm{BLR}(A) such that, for every e∈Tote \in\mathrm{Tot} and every N≥max⁡{1,h(e)}N \ge\max\{1,h(e)\}, ρN(Def)≥α\rho_N(D_e^f) \ge\alpha.

Proof. (i)⇒\Rightarrow(ii). By Theorem 3.1, there are f≤TAf \le_T A and h∈BLR(A)h \in\mathrm{BLR}(A) such that, for every e∈Tote \in\mathrm{Tot}, (∀n≥h(e)) Φe(n)≤f(n)(\forall n \ge h(e))\ \Phi_e(n) \le f(n). Define m(e,k)=2k(h(e)+1)m(e,k) = 2^k(h(e) + 1). Then m∈BLR(A)m \in\mathrm{BLR}(A). Fix e∈Tote \in\mathrm{Tot}, k≥1k \ge1, and N≥max⁡{1,m(e,k)}N \ge\max\{1,m(e,k)\}. Every member of [0,N)∖Def[0,N) \setminus D_e^f is less than h(e)h(e), so 1−ρN(Def)≤h(e)N≤h(e)2k(h(e)+1)<2−k1 - \rho_N(D_e^f) \le\frac{h(e)}{N} \le\frac{h(e)}{2^k(h(e)+1)} < 2^{-k}.

(ii)⇒\Rightarrow(iii) is immediate.

(iii)⇒\Rightarrow(i). Suppose that f≤TAf \le_T A and h∈BLR(A)h \in\mathrm{BLR}(A) satisfy (iii). Choose an integer L≥2L \ge2 with 1/L<α1/L < \alpha. Fix a recursive function θ\theta such that, whenever Φe\Phi_e is total, Φθ(e)(u)=max⁡i≤uΦe(i)\Phi_{\theta(e)}(u) = \max_{i \le u} \Phi_e(i) for every uu. Define

F(n)={max⁡{f(u):n≤u<Ln},if n≥1,f(0),if n=0,F(n) = \begin{cases} \max\{f(u) : n \le u < Ln\}, & \text{if } n \ge1,\\ f(0), & \text{if } n = 0, \end{cases}

and h0(e)=max⁡{1,⌈h(θ(e))L⌉}h_0(e) = \max\left\{1,\left\lceil\frac{h(\theta(e))}{L}\right\rceil\right\}. Then F≤TAF \le_T A and h0∈BLR(A)h_0 \in\mathrm{BLR}(A). If e∈Tote \in\mathrm{Tot} and n≥h0(e)n \ge h_0(e), then Ln≥h(θ(e))Ln \ge h(\theta(e)). The interval [n,Ln)[n,Ln) must meet Dθ(e)fD_{\theta(e)}^f, since otherwise ρLn(Dθ(e)f)≤1L<α\rho_{Ln}(D_{\theta(e)}^f) \le\frac{1}{L} < \alpha. For uu in this intersection,

F(n)≥f(u)≥Φθ(e)(u)=max⁡i≤uΦe(i)≥Φe(n).F(n) \ge f(u) \ge\Phi_{\theta(e)}(u) = \max_{i \le u}\Phi_e(i) \ge\Phi_e(n).

Thus FF and h0h_0 satisfy Theorem 3.1, and AA is superhigh. □\square

The non-robustness of pdomination under lower density

Pdomination was introduced by Chong, Hoi, Stephan, and Turetsky [1]. The notion was motivated by the bounded monotone enumeration principle BME in reverse mathematics; see [2].

Definition 4.1 ([1]). A set AA is pdominant if there is a partial AA-recursive function ψ\psi such that, for every partial recursive φ\varphi,

(∀∞x∈dom⁡(φ))(∃y≤x) [ψ(y)↓>φ(x)].(\forall^\infty x \in\operatorname{dom}(\varphi))(\exists y \le x)\ [\psi(y)\downarrow> \varphi(x)].

Chong, Hoi, Stephan, and Turetsky showed that pdomination is a nontrivial degree property. No weakly 2-generic set is pdominant, whereas there are pdominant 1-generic sets below the halting problem; the two halves of Chaitin’s Ω\Omega are pdominant, but no set which is low for Martin-Löf randomness is pdominant; there are a low r.e. pdominant set and a high r.e. set which is not pdominant.

We consider two density weakenings of pdomination, using correctness sets and density relative to the test domain, respectively. We show that both versions hold for every set, first at positive lower density and then at density one.

For partial functions ψ,φ\psi,\varphi, put

H(ψ,φ)={x∈dom⁡(φ):(∃y≤x) [ψ(y)↓>φ(x)]},H(\psi,\varphi)=\{x\in\operatorname{dom}(\varphi):(\exists y\leq x)\,[\psi(y)\mathord{\downarrow}>\varphi(x)]\},

and

C(ψ,φ)=(ω∖dom⁡(φ))∪H(ψ,φ).C(\psi,\varphi)=(\omega\setminus\operatorname{dom}(\varphi))\cup H(\psi,\varphi).

Definition 4.2. A set AA is lower-correctness-pdominant, abbreviated lcPD, if there is a partial AA-recursive function ψ\psi such that, for every partial recursive φ\varphi with infinite domain, ρ(C(ψ,φ))>0\rho(C(\psi,\varphi))>0. Replacing >0>0 by =1=1 gives correctness-pdominance, abbreviated cPD.

For an infinite set D⊆ωD\subseteq\omega and S⊆ωS\subseteq\omega, put ρD(S)=lim inf⁡N→∞∣S∩D∩[0,N)∣∣D∩[0,N)∣\rho_D(S)=\liminf_{N\to\infty}\frac{|S\cap D\cap[0,N)|}{|D\cap[0,N)|}. When the corresponding limit exists, we write

ρD(S)=lim⁡N→∞∣S∩D∩[0,N)∣∣D∩[0,N)∣.\rho_D(S)=\lim_{N\to\infty}\frac{|S\cap D\cap[0,N)|}{|D\cap[0,N)|}.

Definition 4.3. A set AA is lower-density-pdominant, abbreviated ldPD, if there is a partial AA-recursive function ψ\psi such that, for every partial recursive φ\varphi with infinite domain, ρdom⁡(φ)(H(ψ,φ))>0\rho_{\operatorname{dom}(\varphi)}(H(\psi,\varphi))>0. Replacing >0>0 by =1=1 gives density-pdominance, abbreviated dPD.

Every pdomination witness is a dPD witness. Every dPD witness is both an ldPD witness and a cPD witness, and every cPD witness is an lcPD witness.

We first give a single partial recursive witness for lcPD and ldPD.

Theorem 4.4. There is a single partial recursive function ψ\psi such that, for every e∈ωe\in\omega, ρ(C(ψ,Φe))≥12e+3>0\rho(C(\psi,\Phi_e))\geq\frac{1}{2^{e+3}}>0. Moreover, if D=dom⁡(Φe)D=\operatorname{dom}(\Phi_e) is infinite, then ρD(H(ψ,Φe))≥12e+3>0\rho_D(H(\psi,\Phi_e))\geq\frac{1}{2^{e+3}}>0. Thus every set is both lcPD and ldPD.

Proof. The idea is to partition the inputs for each test Φe\Phi_e into cells of a fixed length and to force one genuine hit whenever a cell contains a convergence. A dedicated marker is placed below every point of its cell; once the first convergence in that cell is seen, we define ψ\psi at the marker late enough to exceed the observed value of Φe\Phi_e. Disjoint marker columns allow this to be done for all ee simultaneously. Thus every nonempty cell contributes one hit but contains at most a fixed number of convergence points, which gives the required positive-density bound.

For the requirement indexed by ee, put L=Le=2e+3L=L_e=2^{e+3}, and divide a tail of ω\omega into cells Ie,j=[jL,(j+1)L)I_{e,j}=[jL,(j+1)L), j≥1j\geq1. Assign to the jjth cell the marker ae,j=2e+1(2j+1)−1a_{e,j}=2^{e+1}(2j+1)-1. The marker columns belonging to distinct ee are disjoint, since 2e+12^{e+1} is the exact power of 2 dividing ae,j+1a_{e,j}+1. Moreover, if x∈Ie,jx\in I_{e,j}, then ae,j<j2e+3=jL≤xa_{e,j}<j2^{e+3}=jL\leq x.

Construct an r.e. set WW as follows: for all e,je,j, when a convergence Φe(x)↓=t\Phi_e(x)\mathord{\downarrow}=t with x∈Ie,jx\in I_{e,j} is first found, wait until a construction stage s>ts>t and enumerate ae,ja_{e,j} into WW.

Each marker is enumerated at most once. Define ψ(a)=min⁡{s:a∈Ws}\psi(a)=\min\{s:a\in W_s\} when a∈Wa\in W, and leave ψ(a)\psi(a) undefined otherwise. This is a partial recursive function. Designate one convergence xe,jx_{e,j} witnessing the action of each cell. For every designated x=xe,jx=x_{e,j}, ae,j≤xa_{e,j}\leq x and ψ(ae,j)>Φe(x)\psi(a_{e,j})>\Phi_e(x), so x∈H(ψ,Φe)x\in H(\psi,\Phi_e). Then it is clear that ρC(ψ,Φe)≥ρD(ψ,Φe)≥12e+3\rho_C(\psi,\Phi_e) \ge\rho_D(\psi,\Phi_e) \ge\frac{1}{2^{e+3}} if DD is infinite. And if DD is finite, C(ψ,Φe)C(\psi,\Phi_e) is cofinite and has density 1. □

To obtain density one, we use several markers in each cell and repeat the construction at every prescribed accuracy. The following lemma supplies the thresholds for these markers.

Lemma 4.5. Given a rational number 0<ε<10 < \varepsilon< 1 and an integer M≥1M \ge1, one can effectively find a multiple LL of MM and a finite set T⊆{1,…,L}T \subseteq\{1,\ldots,L\} such that ∣T∣≤LM|T| \le\frac{L}{M} and, for every integer 1≤r≤L1 \le r \le L, there is some t∈Tt \in T satisfying (1−ε)r≤t≤r(1-\varepsilon)r \le t \le r.

Proof. For any L≥1L \ge1, define t0=1t_0=1, ti+1=⌈ti1−ε⌉t_{i+1}=\left\lceil\frac{t_i}{1-\varepsilon}\right\rceil, let mm be least such that tm>Lt_m>L, and put TL={t0,…,tm−1}T_L=\{t_0,\ldots,t_{m-1}\}. Given 1≤r≤L1 \le r \le L, choose the largest i<mi<m such that ti≤rt_i\le r. Then r<ti+1r<t_{i+1}, and, since rr is an integer, r≤ti+1−1<ti1−εr\le t_{i+1}-1<\frac{t_i}{1-\varepsilon}. Consequently (1−ε)r<ti≤r(1-\varepsilon)r<t_i\le r, so TLT_L has the required covering property.

Moreover, ti≥(1−ε)−it_i\ge(1-\varepsilon)^{-i} for every ii. Since tm−1≤Lt_{m-1}\le L,

∣TL∣=m≤1+log⁡L−log⁡(1−ε)≤1+ε−1log⁡L,|T_L|=m\le1+\frac{\log L}{-\log(1-\varepsilon)}\le1+\varepsilon^{-1}\log L,

where the last inequality follows from −log⁡(1−ε)≥ε-\log(1-\varepsilon)\ge\varepsilon. Hence, for all sufficiently large multiples LL of MM, ∣TL∣≤LM|T_L|\le\frac{L}{M}.

To find such an LL effectively, search through the positive multiples of MM, construct the corresponding finite set TLT_L, and stop when ∣TL∣≤L/M|T_L|\le L/M. The preceding estimate guarantees that this search terminates. Taking T=TLT=T_L completes the proof. □

Theorem 4.6. Every set is both cPD and dPD. Indeed, there is a partial recursive function ψ\psi such that, for every partial recursive function φ\varphi with infinite domain, putting D=dom⁡(φ)D=\operatorname{dom}(\varphi), ρC(ψ,φ)=1\rho_C(\psi,\varphi)=1 and ρD(ψ,φ)=1\rho_D(\psi,\varphi)=1.

Since the final number rr of convergence points in a cell is not known while the computation unfolds, at each prescribed accuracy εn\varepsilon_n we reserve several markers indexed by the thresholds from Lemma 4.5. When the ttth convergence appears, the corresponding marker makes the first tt convergence points into hits; once all convergences in the cell have appeared, some threshold tt lies between (1−εn)r(1-\varepsilon_n)r and rr. Hence all but an εn\varepsilon_n-fraction of the convergence points in each complete cell are hits, while disjoint reservoirs let all pairs (e,n)(e,n) act simultaneously.

Proof. Fix e,ne,n and put εn=2−n−1\varepsilon_n=2^{-n-1} and q=⟨e,n⟩q=\langle e,n\rangle. Use the disjoint recursive marker reservoir Rq={2q(2r+1)−1:r∈ω}R_q=\{2^{q}(2r+1)-1:r\in\omega\}. Apply Lemma 4.5 with ε=εn\varepsilon=\varepsilon_n and M=2q+1M=2^{q+1} to choose effectively a multiple L=Le,nL=L_{e,n} of 2q+12^{q+1} and a finite set T⊆{1,…,L}T\subseteq\{1,\ldots,L\} such that ∣T∣≤L/2q+1|T|\le L/2^{q+1} and, for every 1≤r≤L1\le r\le L, some t∈Tt\in T satisfies (1−εn)r≤t≤r(1-\varepsilon_n)r\le t\le r.

For j≥0j\ge0, let Iq,j=[(j+1)L,(j+2)L)I_{q,j}=[(j+1)L,(j+2)L). The preceding interval [jL,(j+1)L)[jL,(j+1)L) contains exactly L/2q+1L/2^{q+1} members of RqR_q, so assign distinct such markers aq,j,ta_{q,j,t} to the thresholds t∈Tt\in T. When tt distinct convergences of Φe\Phi_e in Iq,jI_{q,j} have been seen, define

ψ(aq,j,t)=1+max⁡{Φe(x):x is one of these t convergence points}.\psi(a_{q,j,t})=1+\max\{\Phi_e(x):x\text{ is one of these }t\text{ convergence points}\}.

Dovetailing over all e,n,j,te,n,j,t defines a partial recursive function, since the reservoirs RqR_q are pairwise disjoint. Moreover, aq,j,t<min⁡Iq,ja_{q,j,t}<\min I_{q,j}, so the first tt convergence points in the cell belong to H(ψ,Φe)H(\psi,\Phi_e).

Fix e,ne,n, put D=dom⁡(Φe)D=\operatorname{dom}(\Phi_e), and let E=D∖H(ψ,Φe)E=D\setminus H(\psi,\Phi_e). We first spell out the estimate on a complete cell. Put rj=∣D∩Iq,j∣r_j=|D\cap I_{q,j}|. If rj>0r_j>0, choose tj∈Tt_j\in T so that (1−εn)rj≤tj≤rj(1-\varepsilon_n)r_j \le t_j \le r_j. The inequality tj≤rjt_j \le r_j ensures that the construction eventually sees tjt_j distinct convergence points of Φe\Phi_e in Iq,jI_{q,j} and defines ψ(aq,j,tj)\psi(a_{q,j,t_j}). Each of these tjt_j points lies in H(ψ,Φe)H(\psi,\Phi_e). Thus ∣H(ψ,Φe)∩Iq,j∣≥tj|H(\psi,\Phi_e) \cap I_{q,j}| \ge t_j and consequently

∣E∩Iq,j∣=rj−∣H(ψ,Φe)∩Iq,j∣≤rj−tj≤εnrj.(6)|E \cap I_{q,j}| = r_j - |H(\psi,\Phi_e) \cap I_{q,j}| \le r_j - t_j \le\varepsilon_n r_j. \tag*{(6)}

When rj=0r_j=0, the same final estimate is immediate.

Now fix NN. The cells Iq,jI_{q,j} (j∈ωj \in\omega) are consecutive and cover [L,∞)[L,\infty). Hence [0,N)[0,N) consists of the initial piece [0,min⁡{L,N})[0,\min\{L,N\}), all the cells Iq,jI_{q,j} that are wholly contained in [0,N)[0,N), and possibly an initial segment of one further cell. The initial piece and the terminal incomplete cell each have length at most LL, so together they contain at most 2L2L points of EE. Applying (6) to every complete cell and summing gives

∣E∩[0,N)∣≤2L+∑Iq,j⊆[0,N)∣E∩Iq,j∣≤2L+εn∑Iq,j⊆[0,N)∣D∩Iq,j∣≤2L+εn∣D∩[0,N)∣.\begin{aligned} |E \cap[0,N)| &\le2L+\sum_{I_{q,j}\subseteq[0,N)} |E \cap I_{q,j}| \\ &\le2L+\varepsilon_n\sum_{I_{q,j}\subseteq[0,N)} |D \cap I_{q,j}| \\ &\le2L+\varepsilon_n|D \cap[0,N)|. \end{aligned}

If DD is infinite, then ∣D∩[0,N)∣→∞|D \cap[0,N)| \to\infty. Then lim sup⁡N→∞∣E∩[0,N)∣∣D∩[0,N)∣≤εn\limsup_{N\to\infty}\frac{|E\cap[0,N)|}{|D\cap[0,N)|} \le\varepsilon_n. Since this holds for every nn, the limsup is zero, and ρD(H(ψ,Φe))=1\rho_D(H(\psi,\Phi_e))=1. Finally, since ρ(C(ψ,Φe))≥ρD(H(ψ,Φe))\rho(C(\psi,\Phi_e)) \ge\rho_D(H(\psi,\Phi_e)), we have ρ(C(ψ,Φe))=1\rho(C(\psi,\Phi_e))=1 as well. □

acknowledgments

The author was supported by Focused Research Grants of Natural Science Foundation of Jiangsu Province No. BK20243060. The author thanks Professor Liang Yu for helpful discussions, and Theorem 3.1 was joint work with him. The assertion of Theorem 3.2 was posed as a question by the author in a student talk given at NUS when he was supported by the Institute for Mathematical Sciences to attend the 2026 logic summer school. The proof of this Theorem was later produced by ChatGPT 6. This proof has been verified by the author without the use of AI tools. The author takes full responsibility for the final content of the paper.

School of Mathematics, Nanjing University, Nanjing, Jiangsu 210093, People’s Republic of China

Email address: [email protected]

References

  1. [1]C. T. Chong, Gordon Hoi, Frank Stephan, and Daniel Turetsky, Partial functions and domination, Log. Methods Comput. Sci. 11 (2015), no. 3, Article 16, 16 pp.DOI
  2. [2]C. T. Chong, Theodore A. Slaman and Yue Yang. The metamathematics of stable Ramsey’s theorem for pairs, Journal of the American Mathematical Society, 27(3):863–892, 2014.DOI
  3. [3]Joshua A. Cole and Stephen G. Simpson, Mass problems and hyperarithmeticity, J. Math. Log. 7 (2007), no. 2, 125–143.DOI
  4. [4]Natasha L. Dobrinen and Stephen G. Simpson, Almost everywhere domination, J. Symbolic Logic 69 (2004), no. 3, 914–922.DOI
  5. [5]Rodney G. Downey and Denis R. Hirschfeldt, Algorithmic Randomness and Complexity, Theory and Applications of Computability, Springer, New York, 2010.DOI
  6. [6]R. G. Downey, C. G. Jockusch Jr. and M. Stob, Array non-recursive sets and multiple permitting arguments, in Recursion theory week (Oberwolfach, 1989), 141–173, Lecture Notes in Math., 1432, Springer, Berlin, 1990.
  7. [7]Santiago Figueira, André Nies, and Frank Stephan, Lowness properties and approximations of the jump, Ann. Pure Appl. Logic 152 (2008), no. 1–3, 51–66.
  8. [8]Rupert Hölzl and Wolfgang Merkle, Traceable sets, in: Theoretical Computer Science (TCS 2010), IFIP Adv. Inf. Commun. Technol., vol. 323, Springer, Berlin, 2010, pp. 301–315.
  9. [9]Susanne Kaufmann and Martin Kummer, On a quantitative notion of uniformity, Fund. Inform. 25 (1996), no. 1, 59–78.
  10. [10]Bjørn Kjos-Hanssen, André Nies, Superhighness, Notre Dame J. Formal Logic 50 (2009), no. 4, 445–452.
  11. [11]Bjørn Kjos-Hanssen, Low for random reals and positive-measure domination, Proc. Amer. Math. Soc. 135 (2007), no. 11, 3703–3709.
  12. [12]Bjørn Kjos-Hanssen, Wolfgang Merkle, and Frank Stephan, Kolmogorov complexity and the recursion theorem, Trans. Amer. Math. Soc. 363 (2011), no. 10, 5465–5480.
  13. [13]Bjørn Kjos-Hanssen, André Nies, Frank Stephan, and Liang Yu, Higher Kurtz randomness, Ann. Pure Appl. Logic 161 (2010), no. 10, 1280–1290.
  14. [14]Bjørn Kjos-Hanssen, Joseph S. Miller, and Reed Solomon, Lowness notions, measure and domination, J. Lond. Math. Soc. (2) 85 (2012), no. 3, 869–888.
  15. [15]Donald A. Martin, Classes of recursively enumerable sets and degrees of unsolvability, Z. Math. Logik Grundlagen Math. 12 (1966), 295–310.DOI
  16. [16]Webb Miller and D. A. Martin, The degrees of hyperimmune sets, Z. Math. Logik Grundlagen Math. 14 (1968), 159–166.DOI
  17. [17]Jeanleah Mohrherr, A refinement of low n and high n for the r.e. degrees, Z. Math. Logik Grundlagen Math. 32 (1986), no. 1, 5–12.DOI
  18. [18]Benoit Monin and André Nies, A unifying approach to the Gamma question, in: 2015 30th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS 2015), IEEE Computer Society, Los Alamitos, CA, 2015, pp. 585–596.
  19. [19]André Nies, Computability and Randomness, Oxford Logic Guides, vol. 51, Oxford University Press, Oxford, 2009.DOI
  20. [20]Stephen G. Simpson, Almost everywhere domination and superhighness, MLQ Math. Log. Q. 53 (2007), no. 4–5, 462–482.DOI
  21. [21]Robert I. Soare, Recursively Enumerable Sets and Degrees: A Study of Computable Functions and Computably Generated Sets, Perspectives in Mathematical Logic, Springer, Berlin, 1987.

Paper details

vlnc:W_w6shywme
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

ChatGPT 6

View statement
Looking for related papers…
Contents