Turing reducibility in the fine hierarchy☆
Introduction
The study of various hierarchies of sets is central to mathematical logic. In computability theory, one investigates hierarchies of countable sets. This paper contributes to a general program in computability theory that seeks to understand various not necessarily algorithmic hierarchies using algorithmic tools such as Turing degrees. Recall that a Turing degree consists of oracles that are indistinguishable from the perspective of Turing computation.
It is quite remarkable that many natural hierarchies admit several equivalent definitions, one usually being syntactical, and the other topological or computability-theoretic (or both). There are many examples of this sort, including the classical hierarchies [9], [25], [18] as well as some very recently introduced ones [16], [17]. Perhaps, the most famous illustration of this phenomenon is provided by the well-known positive solution to Hilbert's Xth Problem [14]: the Diophantine sets are exactly the computably enumerable sets which form the first level of the arithmetical hierarchy. The second level of the hierarchy consists of first-order ∃∀-definable subsets of which are exactly the sets computably enumerable with the help of the Halting problem. The -sets are the complements of the -sets, and .
The Shoenfield Limit Lemma [26] says that a set is in exactly if it can be computably approximated with finitely many mind-changes; this effective approximability of -sets makes them relatively accessible for computability-theoretic investigations. In fact, the study of Turing degrees of -sets is one of the central topics of Turing computability theory [26]. The structure of -degrees turned out to be quite complex, with the theory of -degrees being its most developed and well-understood subtheory [26].
If we cannot fully grasp the structure of -degrees, it is natural to look at some finer intermediate complexity classes between the and the -degrees and try to extend the developed theory of -degrees to these intermediate classes. However, the arithmetical hierarchy is too crude to allow for such a subtle distinction, we need a more sensitive sub-hierarchy. One such finer hierarchy is the difference hierarchy, also known as the Ershov hierarchy [6], [7], [8]. The hierarchy looks at the Boolean combinations of computably enumerable (c.e. for short) sets and measures the complexity of the Boolean forms. The hierarchy has an equivalent “dynamic” definition which measures the number of mind-changes needed to compute a -set via the Shoenfield Limit Lemma. The c.e. sets form the first level of the Ershov hierarchy, while the differences of c.e. sets – also known as d-c.e. sets – form its second level . The hierarchy proceeds through all (notations for) computable ordinals to cover all -sets. There has been many deep results on the first few non-trivial levels of the hierarchy, especially the d-c.e. degrees, see the PhD thesis of Wu [29] and the more recent surveys by Arslanov and Kalimullin [1] and Lempp [11]. Less is known about the higher transfinite levels of the difference hierarchy, but there have been some recent impressive results on the closely related difference hierarchy introduced by Downey and Greenberg, see their book [17]. A survey on this hierarchy can be also found in [5].
Since the investigation of the difference hierarchy from the perspective of Turing degrees has been rather fruitful, one naturally seeks an extension – or at least an analogy – of such results beyond the degrees. Clearly, one naive possibility would be looking at relativised versions of the results on sets. However, lots of subtle information such as a dynamic approximation will be lost after a relativisation, thus such relativised results seem to be of little interest. We need a more sensitive hierarchy than the relativised Ershov hierarchy.
In [19], using some special jump operators Selivanov introduced a natural extension of the Ershov hierarchy to sets beyond , we omit the definition. The more intuitive description of the hierarchy can be found in [21], we outline the main idea. Consider the typed Boolean combinations over variables , where for each fixed k the variables range over -sets. Then for every typed Boolean term t, form the class Each such term has a natural notion of rank which is an ordinal below . We omit further formal details since they are irrelevant to our main result; see [22]. Similarly to the Ershov hierarchy, Selivanov defined classes for according to the rank of the typed term defining the class. He also proved that the definition is robust and the hierarchy is proper with respect to m-degrees.
As we have mentioned above, all natural and useful hierarchies tend to admit several equivalent definitions, and the Selivanov's fine hierarchy is not an exception. There are several equivalent ways to define the hierarchy, one of which, remarkably, uses a slight variation of the Wadge's operator bisep [25]; this gives a technical connection between the fine hierarchy in computability theory, the Wadge hierarchy [27] in descriptive set theory, and the Wagner hierarchy [28] in automata theory.
Selivanov called the new hierarchy the fine hierarchy. The hierarchy is “fine” in the sense that it is provably more sensitive than just the relativised Ershov hierarchy within , for any . The relativised version of the Ershov hierarchy at a level , , does not take into account the mind-changes at the lower levels, thus erasing much of the subtle complexity related to dynamic approximations. Recall that we were searching for a natural extension of the Ershov hierarchy beyond -sets. The fine hierarchy seems to be the most natural choice here.
Whenever we have a hierarchy of sets, the general expectation is that the more complex classes of the hierarchy should contain more powerful oracles, up to Turing equivalence. If this is indeed the case we say that the hierarchy is proper (i.e., does not collapse) with respect to Turing degrees. In the early 1970s, Cooper [4] constructed a d.c.e. set which is not Turing equivalent to any c.e. set. Cooper's result can be extended to all levels of the Ershov hierarchy [10], [20], illustrating that the Ershov hierarchy is proper from the perspective of Turing reducibility.
Which levels of the fine hierarchy are proper with respect to Turing degrees? One would hope for some inductive proof – e.g., by the complexity of the typed terms – that would extend the argument of Cooper [4] to all levels of the fine hierarchy, but this seems to be highly problematic. Somewhat unexpectedly, the situation with the fine hierarchy is more complicated than with the Ershov hierarchy. It seems that any construction of a set in not Turing equivalent to a set in any simpler class would necessarily require a guessing at the level of the highest type of the variable involved in the defining term. The dynamic feature which is so attractive about the fine hierarchy also makes the task quite complicated. The question of which levels of the hierarchy are proper with respect to Turing degrees remained unresolved, and essentially completely open, for a few decades. As we will see, the problem of properness of the fine hierarchy with respect to Turing degrees requires an essential use of advanced degree-theoretic techniques.
Only some partial progress has been done into this direction. For instance, it is known that all levels ( is a limit ordinal) are not proper and that level is proper [24], also each , , is proper [23]; see [25], [24] for further results. However, there are still many levels of the fine hierarchy for which the situation with the Turing degrees remained, and still remains, unknown. We note that the results listed above used constructions of complexity at most 0″. The class collapses with under Turing reducibility [24]. The first level at which a 0‴ guessing seems necessary is vs. , making the question of properness at this level of a special importance and also of some independent technical interest. We explain what these classes and are below.
The sets in the class have the same Turing degrees as the -sets [24]. Thus, we will not define the class; instead, we will be working with sets. The next simplest class that can potentially contain more oracles is . What are these sets? To enter a set from this class, each number goes through the following guessing procedure, in the spirit of mind-changes in the Ershov hierarchy. Initially, we wait for the guessing procedure to claim in a c.e. fashion; if this never happens then it is guaranteed that x is kept out of S forever. However, if the procedure eventually claims that it will be not necessarily be final. At a later stage, x can be extracted from S again, in a c.e. fashion, and if this ever happens it will be given a choice of two independent guessing procedures, and . More specifically, one of the two predicates will be tested on x, and x is truly in the set only if it passes the guessing that it chose. The choice is made by enumerating the witness, again in a c.e. way, to one of two special c.e. sets; and if x finds itself in the first c.e. set, then its final membership becomes a uniformly -question, and in the second set the actual membership will be a -question. The set A is in charge of the -guessing and B is in charge of the -guessing, so ; the formal definition will be given in Section 2, see also the diagram below. In some sense, the guessing on the membership for such sets is still at the level of only three quantifiers, but we get to dynamically choose between a - and a -guessing procedure. These sets are almost , there is only a subtle difference. As we noted above, all previous results on the fine hierarchy used arguments of complexity at most 0″. The reader will perhaps agree that, because of the dynamic nature of the above definition, the use of a 0‴-construction of some sort is likely necessary in any proof of our main result below.
Theorem There exist a set in the class which is not Turing equivalent to any set in .
The seemingly unavoidable complexity of guessing required to prove the theorem is very likely the main reason of why the problem has been open for so long. However, a very careful choice of the setup and a thoughtful use of self-referential predicates on the tree of strategies allowed us to significantly reduce the combinatorial complexity of the guessing. But it is still a 0‴ proof, with true -outcomes and non-standard priority order on the nodes of the tree.
We conjecture that our ideas can be pushed to cover all levels of the form . The hope is that we can potentially describe all proper levels of the fine hierarchy, but it will likely require a complicated iterated priority method, such as the ones introduced and developed by Lempp and Lerman [12], Ash [2], Marcone and Montalbán [13], and Montalbán [15]. We also hope that both the hierarchy and our methods might find interesting applications in degree theory and computable structure theory. For example, is there a natural syntactical description of the subsets of a computable structure that are relatively intrinsically , in the sense of [3]?
Section snippets
The main strategy
As we noted above the Turing degrees of and -sets coincide with the degrees of -sets. Before we proceed to the strategy we give the formal definition of -sets.
Definition A set S is if , where A is a -set, B is a -set, and there exist c.e. sets such that , , , , and .
The naive basic idea of the strategy is obvious, but its implementation will not be straightforward. We shall exploit the extra freedom that a -set has in the
Combining two strategies
Clearly, the main problem with two strategies, one working below the other, is that the weaker priority strategy will have to guess on the membership of the witness of the higher priority strategy.
Remark 3.1 Before we start, we note that the recursion theorem will be used throughout (and typically without explicit reference) to justify some of the uniform changes in the tree and in the strategies. However, the recursion theorem it is not really absolutely necessary for this proof. Although various
The tree of strategies
The tree of strategies will be the infinitely branching tree in which the strings are partially ordered lexicographically based on the order
The set of strings (nodes) of the tree clearly has a computable enumeration in which appears earlier than β. We fix any such enumeration of nodes. Let the index of a string α be the stage at which α appears in this enumeration. We say that α has a weaker priority
Verification
First, we will show that all the diagonalization requirements are met, and then we argue that the set S that we have constructed belongs to the desired class of the fine hierarchy. The set S will consist of all witnesses of strategies, including abandoned witnesses, which will be eventually declared to be in the set.
The true path is the left-most path visited infinitely often. Clearly, the top node is on the true path. We need to check that the true path is infinite. The below lemma is central
Declaration of Competing Interest
There is no competing interest.
References (29)
Fine hierarchies and m-reducibilities in theoretical computer science
Theor. Comput. Sci.
(2008)On ω-regular sets
Inf. Control
(1979)- et al.
A survey of results on the d-c.e. and n-c.e. degrees
Recursive labeling systems and stability of recursive structures in hyperarithmetical degrees
Trans. Am. Math. Soc.
(1986)- et al.
Computable Structures and the Hyperarithmetical Hierarchy
(2000) Degrees of unsolvability
(1971)- et al.
Hierarchies of sets and degrees below
A certain hierarchy of sets. I
Algebra Log.
(1968)A certain hierarchy of sets. II
Algebra Log.
(1968)A certain hierarchy of sets. III
Algebra Log.
(1970)
Invariant Descriptive Set Theory
Pseudojump operators. II. Transfinite iterations, hierarchies and minimal covers
J. Symb. Log.
A survey of results on the d.c.e. and n-c.e. degrees
Lobachevskii J. Math.
Iterated trees of strategies and priority arguments
Sacks Symposium (Cambridge, MA, 1993)
Arch. Math. Log.
Cited by (1)
Non-collapse of the effective Wadge hierarchy
2022, Computability
- ☆
The first author was partially supported by Marsden Fund (Royal Society of New Zealand). The research of the second author was funded by the subsidy allocated to Kazan Federal University for the state assignment in the sphere of scientific activities, project No. 1.13556.2019/13.1. The research of the third author was supported by the Russian Science Foundation, project No. 18-11-00028.