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 , we say that dominates , and write , if . 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:
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 and , let , and define its lower and upper asymptotic densities by and . If these two quantities are equal, their common value is denoted by .
Definition 1.1. Given functions , we say that coarsely dominates , written , if . A function 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:
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 . For , lowness admits an analogous lower-density characterization using a single to bound all partial -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 to be recursive.
Strong jump traceability is likewise preserved when, for every recursive order bound and every partial -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 -recursive function with infinite domain, there be an r.e. trace obeying that bound whose genuine hits for 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 to dominate every total on a set of positive lower density, for almost every . 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 to be superhigh when . 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 is boundedly limit recursive in if there are an -recursive function and a recursive function such that and
for every . We write
We answer their question in Theorem 3.1 (with Liang Yu): a set is superhigh if and only if there are and such that, for the standard enumeration of the partial recursive functions, whenever is total, . 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 is maximal if its complement is cohesive: for each , all sufficiently large elements of agree on membership in . We call supermaximal if these homogeneity thresholds can be chosen as the values of a single function . 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 for which each total is dominated on a set of density one, with convergence controlled by a two-variable function : for every and , . For any fixed rational , it is already sufficient to require these proportions to be at least beyond a threshold in .
§ 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 . For sets and , the notations and 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 and be given by , , and
Lemma 1.4. For every ,
Consequently:
(i) If and , then for all sufficiently large .
(ii) If for infinitely many , then .
(iii) If for infinitely many , then .
Proof. Since is a disjoint union,
The inequality holds because both proportions inside the absolute value belong to . Since , the three consequences follow by taking lower or upper limits.
Definition 1.5. For any partial function , define its block spreading by
For total , block spreading preserves weak truth-table reducibility to a set . 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 be a standard enumeration of the partial recursive functions, and put , . It is a standard fact that .
The following fact explains the connection between the class and truth-table reducibility to the jump and will be used throughout § 3.
Lemma 1.6 (Cole and Simpson [3]). For sets and , the following are equivalent.
(i) .
(ii) .
(iii) The characteristic function of belongs to .
Remark 1.7. Cole and Simpson [3] observed that implies . In particular, implies .
The robust properties
Proposition 2.1. For every Turing degree , the following are equivalent.
(i) is hyperimmune.
(ii) computes a function that is not coarsely recursively bounded.
(iii) There is a function such that for every recursive function .
Proof. (ii)(i). Every eventual recursive bound is also a coarse recursive bound.
(i)(iii). By the infinitely-often-equal characterization of hyperimmune degrees (see Monin and Nies [18]), there is a function that agrees with every recursive function at infinitely many arguments. Fix an effective coding of finite sequences with recursive decoding, and use the blocks from (1). Set . If codes a sequence of length , use that sequence as the values of on , in increasing order of the inputs; otherwise, set equal to zero throughout . This defines a total function .
Fix a recursive function . The function is recursive. By the choice of , for infinitely many . For every such , the functions and agree throughout . Hence Lemma 1.4(ii) gives .
(iii)(ii) is immediate.
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 , the following are equivalent.
(i) is high.
(ii) There is a function such that for every recursive function .
(iii) There is a function such that for every recursive function .
Proof. Martin’s domination theorem implies (i)(ii). The implication (ii)(iii) is immediate. It remains to prove (iii)(i). Let witness (iii). Using the blocks from (1), define . Then . Fix a recursive function . (iii) gives positive lower density to the set . By Lemma 1.4(i) with , we have for every sufficiently large . For each such , any satisfies . Thus dominates every recursive function, and hence is high. □
Following Downey, Jockusch and Stob [6], a set is array recursive if there is a single function that dominates every function . 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 . The following are equivalent.
(i) is array recursive.
(ii) There is a function such that for every .
(iii) There is a function such that for every .
Replacing lower by upper density in Proposition 2.3 yields a much larger class.
Proposition 2.4. Let . The following are equivalent.
(i) .
(ii) There is a function such that for every .
(iii) There is a function such that for every .
Proof. The implications (ii)(iii)(i) are immediate. It remains to prove (i)(ii). Let be the standard increasing recursive approximation to , and define . Then and no function dominates since . Put . Fix and define . Since , it does not dominate . Hence there are infinitely many such that . For each such , . Consequently, Lemma 1.4(ii) gives , as required. □
The same lower-density mechanism also gives a partial-function form of lowness.
Proposition 2.5. Let . The following are equivalent.
(i) is low.
(ii) There is a function such that, for every partial -recursive function , .
(iii) There is a function such that, for every partial -recursive function , .
(iv) There is a function such that, for every partial -recursive function , .
Proof. It is well-known that (i) and (ii) are equivalent, and (ii)(iii)(iv) is immediate. The implication (iv)(ii) follows by the same argument as (iii)(i) in Proposition 2.2, now applied to partial -recursive functions. □
Replacing lower density by upper density in the preceding proposition characterizes incompleteness. For a binary tree , closed under taking initial segments, its width is ; thus has bounded width if a single finite constant bounds the number of nodes on every level. We write for the set of its infinite paths.
Lemma 2.6 (Kaufmann and Kummer [9]). Let . If is an -r.e. binary tree of bounded width, then every is -recursive.
Theorem 2.7. Let . The following are equivalent.
(i) .
(ii) There is a function such that, for every partial function recursive in , .
(iii) There is a function such that, for every partial function recursive in , .
Proof. The implications (ii)(iii)(i) are immediate. Conversely, suppose that . Let be the standard increasing recursive approximation to , and let . Put . Suppose, toward a contradiction, that some partial -recursive function has a failure set of positive lower density . By Lemma 1.4(i), for all sufficiently large , . Choose an integer so large that , and put . Since , for all sufficiently large .
For each , enumerate into a string as soon as there are at least distinct such that and . The sequence is uniformly -r.e., and for every , since the sets of inputs counted for distinct strings are disjoint.
If , then , and therefore . The preceding lower bound on consequently implies for every sufficiently large . Replacing finitely many initial components by the corresponding singletons, we may assume that this holds for every .
Now form the -r.e. tree . The tree has width at most , and . By Lemma 2.6, , a contradiction. Hence (i)(ii).
We next consider agreement with recursive functions. A set is recursively semitraceable if, for every , there is a recursive function such that for infinitely many ; see [13].
Proposition 2.8. Let . The following are equivalent.
(i) is recursively semitraceable.
(ii) For every , there is a recursive function such that . (iii) For every , there is a recursive function such that .
Proof. It suffices to prove (i)(ii). Given , let code the finite sequence , where is fixed in (1). By recursive semi-traceability, some recursive function agrees with at infinitely many arguments. Define a recursive function as follows. If and , decode ; if it codes a sequence of length , let , and otherwise let . Give arbitrary values below . Whenever and , the functions and agree throughout . Since this happens for infinitely many , 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 is recursive if and only if, for every , there is a recursive function such that .
Proof. The forward implication is immediate. For the converse, suppose that satisfies the stated agreement condition. Fix a recursive coding of the finite binary strings by natural numbers. Let and put . By assumption, there is a recursive function such that, for , we have . Choose an integer such that . By Lemma 1.4(i), for all sufficiently large , . For each , let
The sequence is uniformly recursive, and for every , since the sets of positions counted for distinct strings are disjoint. Moreover, for all sufficiently large . Choose such that holds for every , and define a recursive binary tree
Then is an infinite path through , while for every . Thus has bounded width, so is recursive by Lemma 2.6.
We now turn to strong jump traceability. An r.e. trace is a uniformly r.e. sequence of finite subsets of . An order function is a positive, nondecreasing, unbounded recursive function. A trace is -bounded if for every , and it traces a partial function if whenever . For such a function and trace, put
Thus traces precisely when . Recall that is strongly jump traceable if for every order function , every partial -recursive function has an -bounded r.e. trace; see [7].
Theorem 2.10. A set is strongly jump traceable if and only if for every order function and every partial -recursive function , there is an -bounded r.e. trace such that .
Proof. The forward implication is immediate. Conversely, fix an order function and a partial -recursive function . To respect the prescribed bound , we use a slower auxiliary order and retain only values that occur frequently within each block. Let , and put . Applying the assumed density condition to and , there is an -bounded r.e. trace such that has positive lower density. Put . By Lemma 1.4(i), for all sufficiently large , . If , the members of are precisely the for which . Let and enumerate into each value that appears in at least distinct components with . The sequence is uniformly r.e., and
Consequently, . Moreover, . It follows from the preceding lower bound on that for almost every . After replacing finitely many components by singletons containing the corresponding convergent values, becomes a -bounded r.e. trace for . Since and were arbitrary, is strongly jump traceable.
To formulate an upper-density analogue, we first need to account for the possible sparsity of the domain. Since , 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 ; its domain contains for every , and hence has upper density one whenever is infinite, by Lemma 1.4(ii). We must also use rather than , so that undefined values do not count as successes. Recall that a total function is diagonally non-recursive, or , if whenever . A degree is non-DNR if it computes no 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 computes no function if and only if there is an order function such that every total function has a -bounded r.e. trace with for infinitely many . Moreover, if computes no function, then for every order function and every partial -recursive function with infinite domain, there is a -bounded r.e. trace such that for infinitely many .
The following proposition follows readily from these results by a block argument.
Proposition 2.11. Let . The following are equivalent.
(i) computes no function.
(ii) For every order function and every partial -recursive function with infinite domain, there is an -bounded r.e. trace such that .
(iii) For every order function and every partial -recursive function with infinite domain, there is an -bounded r.e. trace such that .
Let denote the usual product measure on . Recall that a set is almost-everywhere dominating (a.e.d.) if, for -almost every and every total function , there is a function which dominates . It is uniformly almost-everywhere dominating (u.a.e.d.) if one function works for almost every and all total ; see Dobrinen and Simpson [4]. For a Turing functional , let . If is total, define the domination set
Definition 2.12 (Kjos-Hanssen [11]). A set is positive-measure dominating (p.m.d.) if, for every with , there is an such that .
Theorem 2.13 (Kjos-Hanssen, Miller, and Solomon [14]). For every set , the following are equivalent.
(i) is u.a.e.d.
(ii) is a.e.d.
(iii) is p.m.d.
We now replace eventual domination in the positive-measure definition by a density condition.
Proposition 2.14. For every set , the following are equivalent.
(i) is a.e.d.
(ii) For every Turing functional with , there is an such that .
(iii) There is an such that
Proof. (i)(iii). By Theorem 2.13, is u.a.e.d. and hence (iii) holds.
(iii)(ii) is immediate.
(ii)(i). Assume (ii) and fix with . Let , with the value defined only when all computations on the right converge. Then . Applying the density condition to , choose and a positive-measure set such that has positive lower density for every . Define by . By Lemma 1.4(i), for every , the set meets for all sufficiently large . Choosing and using gives . Hence witnesses p.m.d. for . Since was arbitrary, 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 , the following are equivalent.
(i) has hyperimmune degree.
(ii) There is an such that
(iii) There is an such that
Proof. Suppose first that has hyperimmune degree, and choose a hyperimmune function . For almost every , the function remains -hyperimmune. Indeed, if for some functional and some the class of satisfying for every had positive measure, then, inside a cylinder on which this class has relative measure greater than , one could compute an eventual bound for , a contradiction. Taking the countable union over all functionals and all proves the assertion. Put . For every such and every , for infinitely many , and for each such the whole block is contained in . 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 is superhigh if and only if there are functions and such that
Proof. Suppose first that and satisfy (2). Choose an -recursive approximation to and a recursive function such that for every . Replacing by , and by , we may assume without loss of generality that for all . Indeed, and , so (2) remains true.
Let be a recursive function such that is the least stage , if it exists, for which for all . Thus, if is total, then is total, and for all .
We define an -recursive binary approximation to . Put . For , let . If either or , put . Otherwise, put exactly when
and
if either condition fails, put .
We first check that . If is total, then is total. Let . By (2) applied to , for every we have . Hence, for all sufficiently large , after has stabilized at , both displayed conditions hold, and therefore . If is not total, then it is clear that for all sufficiently large stages , one of the two displayed conditions fails. And therefore .
Finally, has a recursive mind-change bound. If changes times, then . On each interval on which is constant, say with value , the sequence has the form $010*$: the reset rule and the condition initially force the value , and thereafter the tests only acquire additional conjuncts as 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 boundaries. Consequently,
By Lemma 1.6, and is superhigh.
Conversely, suppose that is superhigh. Fix a functional and a recursive function such that, for every , and for every finite string of length .
Let be the standard -recursive approximation to . We define and in stages. At stage , put for every .
At stage , first update . If there is no such that , put for all . Otherwise, let be the least such , and define
Thus is nondecreasing for every .
We next define . At stage , let be the least number such that has not yet been defined. Let
If for every , define
Otherwise define no new value of at stage .
We verify that the construction works. First, exists for every . Indeed, can change only at stages at which, for some , the finite string changes. For each such , this finite string changes at most times. Thus
Since the construction of uses only the oracle , it follows that .
Next we show that is total. We argue by induction on . Assume that has already been defined. Since and is nondecreasing, if for some , then . Choose a stage after which all strings with and all values with have stabilized. Then, for all , the set is a fixed finite set consisting only of indices for which . Thus every with is total, and there is a later stage such that for every in this finite set. If has not already been defined, the construction defines it at stage . Therefore is total and .
It remains to verify (2). Fix and . Let be the stage at which is defined. By construction, . Since is nondecreasing and has limit , . Also , so .
We claim that . Otherwise, this string would change at some later stage . At that stage the least changed index would be at most , and the update rule (3) would give , contradicting the fact that the nondecreasing sequence has final value at most .
Since is total, . When was defined at stage , the construction required for every and . Since was arbitrary, (2) holds.
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 is maximal if its complement is cohesive: for every , either or is finite. We obtain a stronger condition by requiring a bounded-limit threshold for this eventual homogeneity. Call an r.e. coinfinite set supermaximal if there is a function such that
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 is supermaximal, witnessed by . Choose a total -recursive approximation whose number of changes is bounded by a recursive function . Fix a recursive function such that
Using , define . Also define . These functions are total because is coinfinite. On each interval on which is constant, is constant and changes at most once. Counting changes between such intervals, changes at most times. Define . If is infinite, then . If is finite, then : otherwise (4) would put every element of greater than into the finite set . Thus in this case. Consequently, . By Lemma 1.6, , so is superhigh.
For the converse, let be an r.e. set of the prescribed superhigh degree. By Theorem 3.1, choose and such that
We also use : since is superhigh, Cole and Simpson [3 Theorem 6.12], applied with and , give . The reverse inclusion follows from . Fix a recursive approximation with a -recursive convergence modulus, see [21].
We construct an r.e. set by defining an increasing sequence of finite sets , with . Our aim is to make all sufficiently large elements of agree on membership in each , with a threshold in . To organize these requirements, define the -state of at stage by . This is the binary code of the membership vector . Numerical comparison of states therefore orders these lexicographically, giving priority to the smaller indices. For each fixed and , the state is nondecreasing in and takes values in . Moreover, for , . Thus replacing a marker by one with at least as large an -state does not decrease any of its -states for . We use this ordering to select the markers that remain outside .
At any point in stage , the current markers are the numbers in that have not yet been enumerated into . Write their increasing list as ; the rank of is its current index in this list. A tail action at rank is defined as follows. Let
Enumerate every element of into . After each action, ranks are reassigned according to the new increasing list; all subsequent actions use these updated ranks.
Put and for every . At stage , start with the marker list and perform the following steps.
Coding actions. Process the elements in increasing order. For each such , perform a tail action at rank if that rank is currently present; otherwise do nothing.
Ordinary action. Using the current list after all coding actions, declare rank eligible if there is a with such that , and . If any rank is eligible, perform one tail action at the least eligible rank. Otherwise perform no ordinary action.
This completes stage .
Claim 1. There are only finitely many actions at each rank, and is coinfinite. The rank of any marker that survives an action cannot increase.
Proof of the claim. We argue inductively on . After the last action at a smaller rank and the last coding action at rank , every action at rank strictly increases the -state of its marker. Between actions, that state cannot decrease. Since it takes at most possible values, there are only finitely many such actions. Once the smaller ranks have stabilized, new numbers ensure that rank is eventually present and stabilizes as well. Hence is coinfinite. Finally, an action only removes markers, so the rank of a surviving marker cannot increase. □
Write .
Claim 2. .
Proof of the claim. For , fix . An ordinary action that enumerates is triggered by a marker . Using , find a stage beyond the convergence stages and final values of all for . Thereafter, none of these markers can satisfy the condition for an ordinary action. A coding action that affects must have rank at most , so also computes a stage beyond all such coding actions. Taking a stage beyond these bounds and decides whether . Conversely, if enters at stage , then after its coding action at most current markers remain in . The same bound holds if rank is absent. Subsequent actions cannot increase this number, so . Thus , which proves .
We now find a threshold in above which all elements of have the same -state. Fix and . We record the numbers that appear as markers with -state at least . More precisely, at each stage , before any coding or ordinary action, the current markers are exactly . Enumerate each of these markers with into . To use the domination property (5), we also need a recursive search for a stage at which a suitable marker is present. On input , let simulate the construction until the first stage at which the initial marker list contains a number with . The function outputs this stage ; if no such stage exists, it is undefined. The following Claim 3 is immediate.
Claim 3. The sets are uniformly r.e., and the indices can be chosen recursively. If is infinite, then is total.
Define .
Claim 4. For every and , if is infinite, , and , then .
Proof of the claim. Suppose otherwise, and put . Then by (5). At stage there is a marker of -state at least , whereas at every stage. Since and its rank cannot increase, its current rank is greater than at every stage at which it is present.
As long as survives, a marker greater than of -state at least continues to exist. Indeed, a tail action beginning after either leaves such a witness untouched or replaces it by a marker whose -state is at least as large. An action beginning at or before cannot retain : if its rank is at least , maximality of the retained state rules this out; if its rank is less than , retaining would give it a rank less than , contrary to .
If , then satisfies the condition at stage . Otherwise, , so changes at a later stage, when the same condition is satisfied. At that stage, the persistent witness makes eligible for an ordinary action. The action at the least eligible rank therefore begins at or before and cannot retain it, a contradiction. This proves the claim.
Claim 5. There is a function such that, for every and , if is finite, then .
Proof of the claim. For an approximation with at most one change, initially output 0 and use to search for a number satisfying . On finding one, output it forever. If there is no such bound, the approximation stays at 0. This defines with the required property.
Claim 6. The function
belongs to and witnesses that is supermaximal.
Proof of the claim. Since the function is -recursive and the maximum has a recursively bounded number of terms, their bounded-change approximations give . Fix , , and with . Suppose first that is infinite. Since and , Claim 4 gives . Now suppose that is finite. If , then the permanent marker is eventually recorded in . But and , a contradiction. Hence in this case. Whether is infinite is independent of , so all elements of greater than have the same -state. In particular, they agree on membership in . Thus is supermaximal.
Claims 2 and 6 complete the proof.
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 and an index , put
Proposition 3.3. Fix a rational number with . For every set , the following are equivalent.
is superhigh.
There are a total function and a function with such that, for every , every , and every , .
There are a total function and a function such that, for every and every , .
Proof. (i)(ii). By Theorem 3.1, there are and such that, for every , . Define . Then . Fix , , and . Every member of is less than , so .
(ii)(iii) is immediate.
(iii)(i). Suppose that and satisfy (iii). Choose an integer with . Fix a recursive function such that, whenever is total, for every . Define
and . Then and . If and , then . The interval must meet , since otherwise . For in this intersection,
Thus and satisfy Theorem 3.1, and is superhigh.
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 is pdominant if there is a partial -recursive function such that, for every partial recursive ,
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 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 , put
and
Definition 4.2. A set is lower-correctness-pdominant, abbreviated lcPD, if there is a partial -recursive function such that, for every partial recursive with infinite domain, . Replacing by gives correctness-pdominance, abbreviated cPD.
For an infinite set and , put . When the corresponding limit exists, we write
Definition 4.3. A set is lower-density-pdominant, abbreviated ldPD, if there is a partial -recursive function such that, for every partial recursive with infinite domain, . Replacing by 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 such that, for every , . Moreover, if is infinite, then . Thus every set is both lcPD and ldPD.
Proof. The idea is to partition the inputs for each test 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 at the marker late enough to exceed the observed value of . Disjoint marker columns allow this to be done for all 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 , put , and divide a tail of into cells , . Assign to the th cell the marker . The marker columns belonging to distinct are disjoint, since is the exact power of 2 dividing . Moreover, if , then .
Construct an r.e. set as follows: for all , when a convergence with is first found, wait until a construction stage and enumerate into .
Each marker is enumerated at most once. Define when , and leave undefined otherwise. This is a partial recursive function. Designate one convergence witnessing the action of each cell. For every designated , and , so . Then it is clear that if is infinite. And if is finite, 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 and an integer , one can effectively find a multiple of and a finite set such that and, for every integer , there is some satisfying .
Proof. For any , define , , let be least such that , and put . Given , choose the largest such that . Then , and, since is an integer, . Consequently , so has the required covering property.
Moreover, for every . Since ,
where the last inequality follows from . Hence, for all sufficiently large multiples of , .
To find such an effectively, search through the positive multiples of , construct the corresponding finite set , and stop when . The preceding estimate guarantees that this search terminates. Taking completes the proof. □
Theorem 4.6. Every set is both cPD and dPD. Indeed, there is a partial recursive function such that, for every partial recursive function with infinite domain, putting , and .
Since the final number of convergence points in a cell is not known while the computation unfolds, at each prescribed accuracy we reserve several markers indexed by the thresholds from Lemma 4.5. When the th convergence appears, the corresponding marker makes the first convergence points into hits; once all convergences in the cell have appeared, some threshold lies between and . Hence all but an -fraction of the convergence points in each complete cell are hits, while disjoint reservoirs let all pairs act simultaneously.
Proof. Fix and put and . Use the disjoint recursive marker reservoir . Apply Lemma 4.5 with and to choose effectively a multiple of and a finite set such that and, for every , some satisfies .
For , let . The preceding interval contains exactly members of , so assign distinct such markers to the thresholds . When distinct convergences of in have been seen, define
Dovetailing over all defines a partial recursive function, since the reservoirs are pairwise disjoint. Moreover, , so the first convergence points in the cell belong to .
Fix , put , and let . We first spell out the estimate on a complete cell. Put . If , choose so that . The inequality ensures that the construction eventually sees distinct convergence points of in and defines . Each of these points lies in . Thus and consequently
When , the same final estimate is immediate.
Now fix . The cells () are consecutive and cover . Hence consists of the initial piece , all the cells that are wholly contained in , and possibly an initial segment of one further cell. The initial piece and the terminal incomplete cell each have length at most , so together they contain at most points of . Applying (6) to every complete cell and summing gives
If is infinite, then . Then . Since this holds for every , the limsup is zero, and . Finally, since , we have 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]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]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]Joshua A. Cole and Stephen G. Simpson, Mass problems and hyperarithmeticity, J. Math. Log. 7 (2007), no. 2, 125–143.DOI
- [4]Natasha L. Dobrinen and Stephen G. Simpson, Almost everywhere domination, J. Symbolic Logic 69 (2004), no. 3, 914–922.DOI
- [5]Rodney G. Downey and Denis R. Hirschfeldt, Algorithmic Randomness and Complexity, Theory and Applications of Computability, Springer, New York, 2010.DOI
- [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]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]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]Susanne Kaufmann and Martin Kummer, On a quantitative notion of uniformity, Fund. Inform. 25 (1996), no. 1, 59–78.
- [10]Bjørn Kjos-Hanssen, André Nies, Superhighness, Notre Dame J. Formal Logic 50 (2009), no. 4, 445–452.
- [11]Bjørn Kjos-Hanssen, Low for random reals and positive-measure domination, Proc. Amer. Math. Soc. 135 (2007), no. 11, 3703–3709.
- [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]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]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]Donald A. Martin, Classes of recursively enumerable sets and degrees of unsolvability, Z. Math. Logik Grundlagen Math. 12 (1966), 295–310.DOI
- [16]Webb Miller and D. A. Martin, The degrees of hyperimmune sets, Z. Math. Logik Grundlagen Math. 14 (1968), 159–166.DOI
- [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]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]André Nies, Computability and Randomness, Oxford Logic Guides, vol. 51, Oxford University Press, Oxford, 2009.DOI
- [20]Stephen G. Simpson, Almost everywhere domination and superhighness, MLQ Math. Log. Q. 53 (2007), no. 4–5, 462–482.DOI
- [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.