key: cord-0046146-z3r757u0
authors: Miller, Russell
title: Non-coding Enumeration Operators
date: 2020-06-24
journal: Beyond the Horizon of Computability
DOI: 10.1007/978-3-030-51466-2_10
sha: 66f1a67bfab3ed0d19fde469f5c75f0f8b1f0f13
doc_id: 46146
cord_uid: z3r757u0

An enumeration operator maps each set A of natural numbers to a set [Formula: see text], in such a way that E(A) can be enumerated uniformly from every enumeration of A. The maximum possible Turing degree of E(A) is therefore the degree of the jump [Formula: see text]. It is impossible to have [Formula: see text] for all A, but possible to achieve this for all A outside a meager set of Lebesgue measure 0. We consider the properties of two specific enumeration operators: the HTP operator, mapping a set W of prime numbers to the set of polynomials realizing Hilbert’s Tenth Problem in the ring [Formula: see text]; and the root operator, mapping the atomic diagram of an algebraic field F of characteristic 0 to the set of polynomials in [Formula: see text] with roots in F. These lead to new open questions about enumeration operators in general.

Consider enumeration operators. These are functions E mapping Cantor space 2 ω into itself, in an effective way defined by a computably enumerable set E of axioms of the form (D i , j), all with i, j ∈ ω. The intended meaning of such an axiom is that, if A ∈ 2 ω is the input to E and the finite set D i is a subset of A, then j must lie in E(A). (Here D i is defined to be the unique finite subset of ω with i = n∈Di 2 n , as in [ There is a natural analogy to Turing operators T , which allow one to decide membership of numbers in T (A) when given a decision procedure (effective or not) for A. Enumeration operators use only positive information about A, and produce only positive information about E(A); whereas Turing operators use and produce both positive and negative information. Turing operators have been the focus of more intense study by computability theorists, but enumeration operators need make no apology for their presence. Indeed, the fundamental

The author was partially supported by Grant #581896 from the Simons Foundation and by the City University of New York PSC-CUNY Research Award Program. operator used by Kurt Gödel for his Incompleteness Theorems is an enumeration operator: the deducibility operator D, which (using a fixed Gödel coding of firstorder formulas in a fixed signature) lists the elements of the set D(A) of code numbers of those formulas provable from the formulas with code numbers in A. Thus A is viewed as an axiom set, and D(A) is the set of consequences of A.

Here we focus not on D, but rather on two other enumeration operators. In Sect. 2, we will examine the Hilbert's-Tenth-Problem operator HTP, as defined in [3] and [11] . The results there will continue a program connecting the properties of Hilbert's Tenth Problem for the field Q itself with the corresponding properties for subrings of Q. Then, in Sect. 3, we will consider the root operator for algebraic fields, finding it to have some very pleasing properties, but also noting that it is not a true enumeration operator, according to the definition above. Our final section raises and describes the open question of whether an enumeration operator, strictly as defined above, can realize the properties that make the root operator distinctive. We view this question as being of sufficient interest that posing it, rather than proving the results in Sects. 2 and 3, may be the most consequential act of this article.

A set B is e-reducible to A if B = E(A) for some enumeration operator E. Therefore it is largely trivial to compare A and E(A), or their jumps, under ereducibility; the more interesting comparisons involve Turing reducibility. Much of this article concerns the property of essential lowness, which we now define.

Likewise E is essentially low for Baire category if this same set {A ⊆ ω : (E(A)) ≤ T A } is comeager, in the sense of Baire.

Thus essential lowness says that, for almost all inputs A, the output E(A) is low relative to A. It is important to specify the context of "almost all," as an operator can be essentially low for Baire category without being so for Lebesgue measure, or vice versa. This definition can apply equally well to Turing operators. We use standard notation from [13] . For an introduction to computable fields, [5] and [7] are both helpful.

For a subset W of the set P of all prime numbers, we set R W = Z[W −1 ] to be the subring of the rational numbers Q generated by the reciprocals of the primes in W . The map W → R W is a bijection from the power set of P onto the space of all subrings of Q. Moreover, if subrings of Q are considered in a signature with +, ·, and a predicate I for invertibility (with I(x) defined by ∃y(x·y = 1)), and 2 P has the usual Cantor topology, then this bijection is a computable homeomorphism of topological spaces, in the sense of [10] . Fix a computable list g 0 , g 1 , . . . of the polynomials in Z[ X] = Z[X 1 , X 2 , . . .] and define the enumeration operator HTP as follows. (We usually write HTP(R W ) instead of HTP(W ).)

We recall the definition of the boundary set of subrings of Q. For any single polynomial f ∈ Z[ X], the boundary set is

This says that, although f = 0 has no solution in R W , there is no finitary reason for it to lack a solution: no finite set S 0 of primes omitted from W has the property that every solution requires the inversion of some prime from S 0 . Examples and explanation appear in [3, 8] .

Topologically B(f ) is the boundary of the (open) set A(f ) of subrings in which f = 0 has a solution. More generally, the boundary set of subrings of Q is the union of these:

In Baire category, it is known that B is meager, i.e., small in the sense given by Baire; see [8] . In Lebesgue measure, on the other hand, it remains open whether this same class B is small, i.e. of measure 0, or not. This distinction leads us to state Theorems 1 and 2 separately, for these two notions of smallness, as it is essential for the boundary set to be small. Theorem 1 arises very naturally as a kind of extension of [8, Corollary 1] , which stated that an arbitrary set C satisfies C ≤ T HTP(R W ) for a non-meager class of sets W if and only if C ≤ T HTP(Q). Here lowness (relative to W ) replaces the property of computing C. If HTP is not essentially low, then by this theorem HTP(Q) must be undecidable. Essential lowness of HTP would not yield any consequences about the decidability of HTP(Q) (as the degree 0 of the computable sets is considered to be low, along with every other degree d satisfying d = 0 ), but it would imply a different important result: the existential undefinability of Z within the field Q.

Proof. One direction is readily seen. Essential lowness of HTP means that all W in a co-meager subclass of 2 P satisfy (HTP(R W )) ≤ T W . The intersection of this subclass with the co-meager class {W : W ≤ T ∅ ⊕ W } is also co-meager. By [1, Cor. 5.2] , all W have HTP(Q) ≤ T HTP(R W ), so these comeager-many W all also satisfy

But this implies (HTP(Q)) ≤ T ∅ , by a standard result (see [8, Lemma 2] .)

For the forwards direction, recall that HTP(R W ) ≤ T (W ⊕ HTP(Q)) uniformly for all HTP-generic W . The procedure is as follows. For each f , HTPgenericity means, by definition, that W ∈ A(f ) ∪ C(f ), where

So, to decide whether f ∈ HTP(R W ), we simply search for either a solution to f = 0 in R W (using the W -oracle to enumerate R W ), or a finite subset S 0 ⊆ (P−W ) such that f / ∈ HTP(R P−S0 ). (The latter is decidable from HTP(Q), uniformly in S 0 ; see [1, Prop. 5.4] or [8, Prop. 1] .) Therefore, for HTP-generic sets W , we have (HTP(R W )) ≤ T (W ⊕ HTP(Q)) (indeed via a 1-reduction, by the Jump Theorem [13, III.2.3] ). But with HTP(Q) assumed low, the class of W for which

is comeager, as is the class of HTP-generic sets W , so we have shown that {W : (HTP(R W )) ≤ T W } is comeager.

If the operator HTP is essentially low in the sense of Lebesgue measure, then the set HTP(Q) has low Turing degree. As a partial converse, If HTP(Q) has low Turing degree and the set B of all boundary rings has Lebesgue measure 0, then HTP is essentially low for Lebesgue measure.

Proof. The forward direction has much the same proof as in Theorem 1: measure-1-many sets W satisfy

Consequently (HTP(Q)) ≤ T ∅ ; see Lemmas 2.1 and 2.3 of [9] for details.

The reverse direction requires more care. Notice that with an HTP(Q)-oracle, we can enumerate the finite binary strings σ such that a given f does not lie in HTP(R (P−σ −1 (0)) ). (Again this follows from [1, Prop. 5.4] or [8, Prop. 1] .) This in turn allows us to approximate, from below, the measure of the set C(f ). On the other hand, with no oracle at all, we can approximate from below the measure of the set A(f ). By assumption μ(A(f )) + μ(C(f )) = 1, since the rings lying in neither A(f ) nor C(f ) are by definition boundary rings of f . Therefore, we can approximate μ(A(f )) = 1 − μ(C(f )) from above as well, using the HTP(Q)oracle.

Given any ε > 0, and any f i in an enumeration f 0 , f 1 , . . . of Z[ X], the HTP(Q)-oracle now allows us to approximate the measure μ(A(f i )) to arbitrary precision. Suppose this approximation places μ(

. We then enumerate solutions to f i = 0 in Q until we have found finitely many solutions such that the total measure of the set of subrings containing any of those solutions is > a i . Among the subrings R that do not contain any of those finitely many solutions, the set of those that do contain some solution to f i = 0 has measure < ε 2 i+1 . Therefore, for any n and any η ∈ 2 n , we can produce a finite set S η,ε of binary strings σ such that, among subsets W ⊆ P, the equivalence

Our other hypothesis, for the reverse direction, is that HTP(Q) is low, meaning that (HTP(Q)) ≤ T ∅ . It follows that

Using this, we can now give a procedure that (uniformly in the given ε), computes (HTP(R W )) from W correctly on a set of measure ≥ 1 − ε. Given a number e, we wish to determine whether e ∈ HTP(R W ), which is to say, whether Φ HTP(RW ) e (e) halts. The oracle (W ⊕ HTP(Q)) will decide whether

since the quantifier-free subformula is decidable from (W ⊕ HTP(Q)), as seen above. Thus, outside a set of measure < ε 2 e+2 , the (W ⊕ HTP(Q)) -oracle has decided correctly whether

which is to say, whether Φ HTP(RW ) e (e) halts. Outside a set of measure < e ε 2 e+2 = ε 2 , this computation will be correct for every e, and since the computation of (W ⊕ HTP(Q)) from W was also correct outside a set of measure < ε 2 , we have proven the theorem.

Let Δ(F ) be the atomic diagram -viewed as a subset of ω, using Gödel coding -of a field F of characteristic 0, in the pure language of rings. Given Δ(F ), the root operator Θ enumerates the subset W F ⊆ ω called the index of F :

. (Here all polynomials have just one variable X, as opposed to Sect. 2.) It is clear that W F can be enumerated uniformly this way if one has an oracle for the atomic diagram, but of course we mean Θ to be given only an (arbitrary) enumeration of that atomic diagram. Fortunately, these are equivalent. To decide whether a + b = c in the field F , just enumerate Δ(F ) until a formula of the form a + b = d (for some d) appears, and check whether this d is the element c or not; similarly for multiplication. So, given any enumeration of the atomic diagram Δ(F ) of any presentation of a field F of characteristic 0, Θ will indeed enumerate W F . Our specific interest is in algebraic fields, i.e., algebraic extensions of Q.

Algebraic fields of characteristic 0 may be viewed in much the same context as subrings of Q. In both cases, the collection of all isomorphism types belonging to the class forms a topological space computably homeomorphic to Cantor space. Also, in both cases, one natural definable predicate must be adjoined to the signature in order for the homeomorphism to exist. In both cases, the original signature is that of rings, with addition and multiplication symbols. For subrings of Q, in the preceding section, we required an invertibility predicate I in the signature, defined by I(x) ⇐⇒ (∃y) x · y = 1: with this predicate it becomes possible to compute the index W = {p ∈ P : 1 p ∈ R} of an arbitrary subring R of Q uniformly from the atomic diagram of each presentation of R.

For our algebraic fields -which, since we restrict to characteristic 0, may be viewed as precisely the class of all subfields of the algebraic closure Qwe likewise require some additional information to compute the index of an arbitrary member of the class. The usual strategy is to adjoin root predicates: either a single finitary predicate R, or else a d-ary predicate R d for each d > 1. These are defined by

(If a single R is used, it is simply the union of all these R d .) Given the atomic diagram of a subfield F of Q, in the signature with these predicates, one can readily compute the index W F of F as defined above. Clearly W F = W E whenever E ∼ = F , and the converse also holds (cf. [12, Cor. 3.9] , with Q as the ground field). That is, the subfields of Q may be classified up to isomorphism by their indices. On the other hand, it should be noted that not every subset of ω is the index of an algebraic field under this definition: if (X 4 − 2) has a root in F , for example, then (X 2 − 2) cannot fail to have one. Nevertheless, the indices used here do yield a computable homeomorphism from the space of all subfields of Q onto Cantor space. It is decidable uniformly for each σ ∈ 2 <ω whether there exists an algebraic field F for which σ is an initial segment of W F , and the collection of σ for which such a field does exist is thus a computable subtree T of 2 ω , with no terminal nodes and no isolated paths. The desired homeomorphism then maps the class of isomorphism types of algebraic fields bijectively onto the space of all paths through T , which in turn is computably homeomorphic to 2 ω .

One should note that this homeomorphism is not canonical: it depends heavily on the choice of the computable enumeration of Z[X] used to define the indices W F . Using Lebesgue measure on this space is possible but not recommended: different enumerations of Z[X] will give distinct measures on the space of (isomorphism types of) subfields of Q. A better option is to use the Haar-compatible measure μ defined in [10] , which has the property that, for every normal field extension K ⊇ Q with finite vector-space dimension [K : Q], However, the isomorphism types F of fields such that all presentations of F compute W F are rare: they form a meager set of Haar-compatible measure 0 within the class of all subfields of Q. To see this, notice first that the ability to enumerate W F is equivalent to the ability to compute (or enumerate) a presentation of the field F : whenever a polynomial in Z[X] is found to have a root in F , we first check whether we have already put such a root into our presentation, then consider the possible ways that such a root (if not already present) could sit over the finitely-generated subfield we have built so far, and enumerate W F further until the minimal polynomial of a primitive generator of one of these possibilities appears in W F , at which point it is safe to extend our field to be isomorphic to that possibility. All of this is effective, by Kronecker's Theorem (see [6, Thm. 2.2]), allowing us to state our next theorem.

Then L has measure 1 as a subset of 2 ω , under the Haar-compatible measure, and is also co-meager in 2 ω . (By analogy to Definition 1, we say that Θ is essentially noncomputable.)

Proof. By results of Jockusch [2] and Kurtz [4] , there is a co-meager, measure-1 class of sets W ∈ 2 ω each having the property that there exists some V ∈ 2 ω for which W is V -computably enumerable but not V -computable. Whenever W has this property, we can find a presentation of the field F with W = W F that is computable from such a set V . For this presentation, Δ(F ) fails to compute W F = Θ Δ(F ) , although it can enumerate it.

We note that, for each index W in the measure-1 co-meager set described by the theorem, the presentations F that do have W F ≤ T Δ(F ) are (of course) those in the upper cone above W ; whereas every set that computes V can compute a presentation of this field. Thus the presentations of F that succeed in computing W F may be viewed as a small subset of the set of all presentations of F , as every upper cone that is a proper subset of another upper cone has measure 0 within the larger upper cone. Hence Theorem 3 may be viewed as saying that for almost all isomorphism types of algebraic fields, almost all presentations of that field fail to compute the index of the isomorphism type.

Nevertheless, the indices are almost never too far away from the presentation. Of course, since Δ(F ) can enumerate W F , it is immediate that we always have W F ≤ T (Δ(F )) . In certain cases the two are Turing-equivalent -e.g., when F is a computable presentation of the field Q[ √ p n : n ∈ ∅ ], whose W F has degree 0 . However, our next two theorems say that in almost all cases, this fails, and indeed W F is almost always low relative to Δ(F ) -by which we mean that their jumps satisfy (W F ) ≤ T (Δ(F )) . (From here on we will mostly write F and F when we actually mean Δ(F ) and (Δ(F )) .) Proof. We describe the uniform procedure. Let F be a field with W F = W . Our procedure is given an F -oracle, from which it can compute both W and ∅ , uniformly. To decide whether e ∈ W , it begins running Φ W e (e), and if this computation ever halts, then it outputs 1, knowing this to be correct. Simultaneously, it tests each initial segment σ ⊆ W , using ∅ to decide whether ∀τ ⊇ σ∀t Φ τ e,t (e) ↑ . If the procedure ever finds a σ ⊆ W for which this holds, then it outputs 0, since no extension of this σ (including W itself) can ever cause Φ e to halt on input e. Now if W is 1-generic, then for every e there must exist some finite initial segment σ ⊆ W for which either Φ σ e (e) ↓ or else no τ ⊇ σ ever gives convergence. The procedure eventually discovers such a σ and outputs the correct answer about whether e ∈ W . (It is clear that it nevers gives an answer except when it has found such a σ.) Thus W ≤ T F , uniformly in F , for all 1-generic W . The theorem now follows from the co-meagerness of the 1-generic sets in 2 ω .

The situation for Lebesgue measure is similar but not quite as nice. It remains true that W is almost always low relative to all presentations of the field with index W : in particular, this holds outside a set of measure 0. However, no single uniform procedure can establish this for all W outside a set of measure 0. Instead, we must argue up to sets of arbitrarily small measure. (Notice that in Baire category, there is no natural analogue of "up to arbitrarily small measure": the only divisions are meager-or-not and comeager-or-not. It is fortunate that we had a uniform procedure there!) Theorem 5. For each ε > 0, there is a uniform procedure that, for all W in a set of Haar-compatible measure > 1 − ε, computes W from F for all fields F with W F = W . Hence, for all W outside a set of measure 0, every presentation F of that field satisfies W ≤ T F .

We fix a rational ε > 0 and give a uniform procedure that computes W from F on a set of measure > 1 − ε. For each W in this set, each presentation F of the field with index W , and each e, the procedure will determine whether Φ W e (e) halts. The procedure goes through each pair r, n with r ∈ [0, 1] rational and with n ∈ ω in turn, asking its F oracle whether both of the following hold:

(∃k, s) ∃τ 0 , . . . , τ k ∈ 2 n of total measure > r − ε 2 e+1 (∀i ≤ k) Φ τi e,s (e) ↓ ¬(∃k, s)(∃τ 0 , . . . , τ k ∈ 2 n of total measure > r)(∀i ≤ k)Φ τi e,s (e) ↓

Here "total measure" means the Haar-compatible measure of the set {A ∈ 2 ω : (∃i ≤ k)τ i ⊆ A}, which is readily computed (making sure to avoid doublecounting overlaps!). The first sentence is considered to hold vacuously if r < ε 2 e+1 . Also, with τ i ∈ 2 n , we interpret "convergence" of Φ τi⊕F e,s (e) to mean that the procedure halts without ever asking whether any number ≥ n lies in τ i . These sentences are existential, hence decidable from the F -oracle.

Eventually our procedure must find a pair r, n for which both answers from F are positive. It then stops asking such questions, and searches until it finds the promised τ 0 , . . . , τ k ∈ 2 n of total measure > r − ε 2 e+1 for which all Φ τi e,s (e) ↓. As soon as it has found such strings, it checks whether any of the (finitely many) τ i it has found is an initial segment of W . (Here is where the full F -oracle is needed: it can compute W . For the first step, a ∅ -oracle would have sufficed.) If so, then it outputs that Φ W e (e) ↓, knowing this answer to be correct. If not, then it outputs that Φ W e (e) ↑. The latter answer is not guaranteed to be correct, of course, but it can fail only for those W within a set of measure < ε 2 e+1 , and so the set of W for which our procedure fails to compute W correctly has measure ≤ e ε 2 e+1 = ε, as required.

A careful reading of Sect. 3 will reveal that we avoided ever actually calling the root operator Θ an enumeration operator. Indeed, it was intended specifically to operate on (enumerations of) atomic diagrams of algebraic fields, rather than on (enumerations of) arbitrary subsets of ω. One could run it with an enumeration of an arbitrary A ⊆ ω, but with high probability the result would be that every f ∈ Z[X] would be deemed to have a root, as the configuration describing this would appear sooner or later. Even worse, the output would not be independent of the enumeration of A, since for most A the ternary relations + and · described by A would not be functions: a+b would be deemed to equal the first c for which the code number of the statement "a + b = c" appeared in A. So this Θ does not satisfy the definition given in Sect. 1: it functions as such an operator only on a specific domain within 2 ω , and that domain is meager with measure 0.

The basic question, therefore, asks whether the pleasing results about Θ can hold of a true enumeration operator. When E satisfies the full definition, can E be essentially low and essentially noncomputable, as Θ was on its domain? The answer to this first question is immediate and positive. To find an essentially noncomputable enumeration operator, one need look no further than the map A → (A ⊕ ∅ ), whose output is Turing-equivalent to A for a comeager measure-1 collection of sets A. To add essential lowness for Lebesgue measure, we adjust the operator to map A to (A ⊕ L), where L is a fixed c.e. set of low (nonzero) Turing degree. It is known that, for such an L,

and since L ≡ T ∅ , this implies that (A ⊕ L) is low relative to A for almost all sets A. Moreover, every A that is 1-generic relative to L lies in this set, so the set is comeager. On the other hand, A computes (A ⊕ L) only if A ≥ T L, and since L is noncomputable, the upper cone of sets ≥ T L has measure 0 and is meager. (All measure-theoretic results used here were proven by Stillwell in [14] .)

In brief, one can accomplish the same goals achieved by Θ, simply by coding an appropriate c.e. set into the output of the enumeration operator. However, Θ accomplished the goal by different means: it produced an output Θ Δ(F ) > T Δ(F ) (in almost all cases) simply because the problem of determining existence of roots of polynomials in a field seems to be inherently noncomputable. The following lemma makes this more specific. Lemma 1. Fix a noncomputable subset C ⊆ ω, and let L be the set of indices W such that, for every F with W F = W , C ≤ T Θ Δ(F ) . Then L is comeager of measure 1.

Proof. Θ Δ(F ) is just W F itself, and since C is noncomputable, only a comeager measure-0 collection of sets W satisfy C ≤ T W .

The simplicity of the proof exposes the overstatement of this lemma, which really just says that upper cones above noncomputable sets are meager of measure 0, as has been long known. Part of the difficulty of working with Θ is that, since its domain is only a small subset of 2 ω , we used different means to measure what it did. In particular, for a subset S of the domain, we measured the image of S under the operator, rather than measuring S itself. Since the image of Θ (on its intended domain: atomic diagrams of algebraic fields) is all of 2 ω , this was reasonable, but it makes Lemma 1 trivial.

Nevertheless, Lemma 1 was stated this way for a reason: it introduces the notion of a non-coding operator.

An enumeration operator E is non-coding for Lebesgue measure if, for every noncomputable C ⊆ ω,

Likewise, E is non-coding for Baire category if this set is meager whenever

Thus this is the same idea we noted above for Θ, but now defined using measure and category on the domain 2 ω of E, rather than on the image of a specific smaller domain.

All operators of the form A → A ⊕ C (with C noncomputable) clearly fail this definition. Indeed, any enumeration operator E for which A ≤ T E(A) holds on a set of positive measure must fail the definition, as ∅ ≤ T A always holds. So a noncoding operator must avoid producing the jump of its input, at least in almost all cases. This brings us to our main open questions, which can be seen as a sort of uniform version of Post's Problem for enumeration operators. Indeed, does there exist such an operator for which this set has measure < 1? Likewise, can this set be meager? Or at least, can it fail to be co-meager?

We point out the following operator. Let R, S be two noncomputable c.e. sets that form a minimal pair (as in [13, §IX.1] , e.g.), and define the enumeration operator E by the union of the following c.e. sets of enumeration axioms:

Therefore, in almost all cases we have E(A) ≤ T A. However, if C ≤ T E(A) on a co-meager or measure-1 collection of sets A, then C must be computable, as it would be computed by both R and S. So it is readily possible to answer Question 1 if one relaxes the definition of non-coding enumeration operators to require only that {A ⊆ ω : C ≤ T E(A)} have measure < 1, or that it not be co-meager. In fact, Definition 2 requires that these sets be small (as opposed to "not-large").

A significant part of the difficulty in answering Question 1 is that enumeration operators E must enumerate the same set E(A) for all enumerations of the set A. This precludes the use of many of the techniques employed in studying the theory of the c.e. degrees, such as the Friedberg-Muchnik method, or the strategy for the Sacks Density Theorem. The latter, for example, starts with two c.e. sets C < T D, and immediately fixes computable enumerations of each. Its strategy succeeds in enumerating a set strictly between C and D, but if different computable enumerations were used, it would generally enumerate a different set in that interval. Therefore that method would require significant refinement -a kind of uniformization -to succeed in answering Question 1.

Our last proposition illustrates the importance of Question 1.

Suppose that the answer to the strong form of Question 1 is negative for Baire category. (That is, assume that for all non-coding enumeration operators E, {A ⊆ ω : E(A) ≤ T A} is not meager.) Then the existence of a comeager collection of subsets W ⊆ P satisfying HTP(R W ) ≤ T W is equivalent to the undecidability of HTP(Q). Likewise, if the answer to the weak form of Question 1 for Baire category is negative, then the existence of a non-meager collection of subsets W satisfying HTP(R W ) ≤ T W , is equivalent to the undecidability of HTP(Q).

Proof. First of all, every W ⊆ P satisfies HTP(Q) ≤ T HTP(R W ). Therefore, every W outside the upper cone above HTP(Q) satisfies HTP(R W ) ≤ W . If HTP(Q) were undecidable, then the upper cone above it would be meager, so the backwards direction in each paragraph of the proposition holds even without knowing any answers to Question 1.

The forwards direction is where Question 1 comes into play. In each paragraph, the hypotheses imply that the HTP-operator cannot be non-coding for Baire category. Therefore there is some non-meager subset S ⊆ 2 P on which it codes some noncomputable information: some C > T ∅ satisfies (∀W ∈ S) C ≤ T HTP(R W ).

But then it follows from Corollary 1 in [8] that C ≤ T HTP(Q).

A negative answer to one of the two alternative forms of Question 1 essentially says that if HTP(R W ) ≤ T W holds for a non-meager (alternatively, co-meager) class of sets W , then there must be some specific non-computable information that HTP is coding into those sets. The result [8, Corollary 1] then shows that this specific information can be derived from just HTP(Q). Similar statements would hold for Lebesgue measure if the boundary set B defined earlier has measure 0, but this remains an open question.

As easy as Q: Hilbert's Tenth Problem for subrings of the rationals

Degrees of generic sets. Recursion theory: its generalisation and applications

The Hilbert's-Tenth-Problem operator

Randomness and genericity in the degrees of unsolvability

Computable fields and Galois theory

Q-computable categoricity for algebraic fields

An introduction to computable model theory on groups and fields

Baire category theory and Hilbert's Tenth Problem inside Q

Measure theory and Hilbert's Tenth Problem inside Q

Isomorphism and classification for countable structures

HTP-complete rings of rational numbers

Computable categoricity for algebraic fields with splitting algorithms

Recursively Enumerable Sets and Degrees

Decidability of the "almost all" theory of degrees