On the main scientific achievements of Victor Selivanov

1. Numbering theory

Computable numberings and degrees of unsolvability 1

In addition, Selivanov proved several facts on degrees of unsolvability. He classified the possible versions of t t -reducibilities [S-9] (a result that was independently obtained by Bulitko [10]). Moreover, he completely described the relationship between the Ershov hierarchy and the high-low hierarchy of Turing degrees [S-16,S-19,S-27]. This was independently discovered by Jockusch and Shore [21].

Additional information on this section may be found in [34].

Precomplete and complete numberings . Selivanov defined and investigated several generalizations of the so called m-jump operator [S-13]. It turned out that these generalized operators are closely related to the theory of complete numberings developed by Mal’tsev and Ershov [13,27]. He also developed a relativized version of the theory of precomplete and complete numberings which led to priority-free proofs of several known results about the structure of t t -type degrees and about m-degrees of index sets in such structures [S-18,S-21,S-28,S-32]. Furthermore, Selivanov extended the famous Arslanov’s completeness criterion to the case of an arbitrary precomplete numbering [S-18]. See the survey [S-82] for a detailed discussion of the results on precomplete numberings. This line of research was recently continued by Arslanov, Barendregt, Faizrakhmanov, Terwijn, and other authors [4,6,15].

Among other applications of numberings, one should also mention that Selivanov provided a complete discussion on proving analogs of the famous Rice–Shapiro theorem for the levels of the arithmetical hierarchy, as well as for some of its refinements [S-11,S-13]. The study of extensions of Rice–Shapiro theorem has been actively developed by Korovina and Kudinov [25], among others.

Positively numbered structures . In the beginning of the 1990s, Selivanov obtained general results on positively numbered Boolean algebras, part of them jointly with Odintsov [S-23,S-26]. Recently, these results have found interesting applications in the investigations of effective presentations for Stone spaces (in the works of Hoyrup, Kihara, Selivanov [S-c42] and Bazhenov, Harrison-Trainor, Melnikov, Ng [8]).

The main results of [S-23,S-26] are the following: the class of positively numbered Boolean algebras has a good computable numbering (an analog of the numbering of the computably enumerable sets), and that there is a unique (up to effective isomorphism) universal positive Boolean algebra (an analog of the creative set). Selivanov also characterized many natural and important index sets of positive Boolean algebras. Later some of these results were extended by him to a very general context of recursively axiomatizable quasivarieties [S-32,S-38]. This research has found different applications, e.g., in the classification of many natural index sets in the lattice of computably enumerable sets, in the semilattice of computably enumerable m-degrees, and in the Lindenbaum algebra of propositions [S-23,S-24,S-26,S-31,S-32,S-38]. In recent years, the theory of positive algebraic structures has been actively developed by Andrews, Badaev, Khoussainov, San Mauro, Schweber, Sorbi, and other authors [2,3,17].

A recurring topic in Selivanov’s research is that of hierarchies. He studied them in such different areas as computability theory, complexity theory, formal language theory, and descriptive set theory.

In his habilitation thesis and in [S-13], Selivanov defined a refinement of the arithmetic hierarchy called the fine hierarchy and proved that it contains many known hierarchies and has some rather strong closure properties with respect to refinements. These results informally mean that the fine hierarchy is in some sense the finest possible. Later, using set-theoretic operations introduced by Wadge, he gave a set-theoretical description of the fine hierarchy. This gives the possibility of defining the hierarchy in very different contexts, e.g., in the context of logic and descriptive set theory. In the last case, he could show that the fine hierarchy is, in an exact sense, the finite version of the Wadge hierarchy of Borel sets [S-13,S-15,S-22,S-25,S-26,S-30,S-31].

He extended the fine hierarchy from the case of sets to the case of k-partitions [S-65]. With heavy use of Priestley duality he showed that the methods of alternating trees and of m-reducibilities developed earlier by Addison, by him, and by others for concrete examples of fine hierarchies apply to a broad class of fine hierarchies.

Another principal result is a complete description of m-degrees of index sets of the predicates first-order definable in the Lindenbaum algebra of statements of nontrivial signature. Note that this classification needs all levels of the fine hierarchy, i.e., it could not be achieved without the invention of the fine hierarchy (see [S-6,S-7,S-8,S-10,S-11,S-12,S-14,S-22,S-24,S-26]).

Turing degrees and the fine hierarchy . In [S-78,S-79,S-86], Selivanov (jointly with Melnikov and Yamaleev) investigated proper levels of the fine hierarchy with respect to Turing equivalence. They obtained some natural, highly non-trivial extensions of the famous Cooper’s theorem on the existence of a properly d.c.e. Turing degree (i.e., a degree which contains a d.c.e. set, but does not contain c.e. sets). In particular, the paper [S-86] proves that there exists a set S belonging to the class Σ ω ω + 2 of the fine hierarchy such that S is not Turing equivalent to a Σ 3 0 -set.

Formal languages . Selivanov also used the fine hierarchy to classify regular ω-languages. It turned out that the resulting classification coincides with the Wagner hierarchy. This result establishes a close relationship between descriptive set theory and the theory of regular ω-languages. It leads to rather different proofs of deep and complicated results of Wagner [S-33]. This investigation seems to have been the first application of modern descriptive set theory to the theory of ω-languages, a line which was also developed by French mathematicians such as Perrin, Carton, Duparc, and Finkel. Selivanov classified the Wadge degrees of ω-languages of deterministic Turing machines [S-39]. This result answers a question raised by Duparc.

In pursuing this research, Selivanov developed a complete analog of the Wagner hierarchy for the class of regular star-free ω-languages [S-52]. He also extended the Wagner hierarchy from the case of sets to the case of k-partitions which, for k > 2 , leads to a much more complicated (but still tractable) structure of degrees [S-c18,S-c28]. Jointly with Wagner, he comprehensively investigated complexity questions related to his hierarchy [S-50].

In [S-96,S-c41,S-c50,S-c51] Selivanov made important contributions to the study of classes of ω-languages (and of k-partitions) recognized by natural classes of automata (part of these results is obtained jointly with Ogawa and Orekhovskii). This research is interesting not only for understanding infinitary behaviours of the corresponding automata, but also for capturing the constructive content of the Wadge hierarchy. The study of Wadge degrees for sets S of infinite words and trees (for S recognizable by various automata models) remains an active research field.

Further on, Selivanov proposed a new, logical approach to the well-known problem of the decidability of the dot-depth hierarchy and of some of its refinements. In this way, he obtained quite different and shorter proofs of important results, as well as new results on analogs of the dot-depth problem. Some of these results were obtained independently and by other methods by Glaßer, Schmitz and Wagner. Using some previous results on the so called leaf languages, he established a deep connection of these automata-theoretic hierarchies with the complexity-theoretic ones mentioned below [S-35,S-37].

In joint work with Wagner [S-45] the above mentioned results were applied to defining and investigating a reducibility on star-free languages which fits perfectly with the dot-depth hierarchy. Both established a close relationship of this reducibility with the leaf-language approach to complexity classes. This research was extended to another important class of regular languages: quasi-aperiodic languages [S-60].

Selivanov and Konovalov characterized, up to isomorphism, several natural Boolean algebras of regular languages [S-67,S-c31,S-c35]. The characterization of the algebra of regular languages was independently obtained by Marini, Simi, Sorbi, and Sorrentino. Some complexity issues related to these hierarchies were studied by Selivanov in a joint work with Glaßer and Schmitz [S-73].

Complexity theory . In the context of structural complexity theory, Selivanov defined and considered analogs of the hierarchies mentioned above. He was able to extend the well-known result of Kadin about the non-collapse of the Boolean hierarchy over NP to a much richer hierarchy, called the plus-hierarchy [S-30,S-34]. Further work in this direction, essentially developed jointly with Glaßer and Reitwiessner [S-64,S-c19], led to the solution of long-standing open problems such as a question by Blass and Gurevich on the status of the shrinking property (also known as the reduction property) for levels of the polynomial hierarchy.

Descriptive set theory . Classical descriptive set theory (DST) is usually developed in Polish spaces, but Selivanov was enthusiastic about extending DST to more general spaces. In [S-41,S-42,S-46], partially based on earlier papers [S-8,S-10,S-11], he developed rather comprehensively the theory of Borel and difference hierarchies in ω-algebraic domains. For instance, in [S-41,S-42] he showed analogues of Hausdorff’s theorem (that the transfinite hierarchy of differences of open sets exhausts all Δ 2 0 sets) and Lavrentyev’s theorem (that the difference hierarchy does not collapse), and in [S-43,S-c9] he initiated the study of Wadge reducibility in ω-algebraic domains. The theory has non-trivial applications to classical ω-ary Boolean operations (see the corresponding paragraph below) and is closely related to the theory of infinitary languages (i.e., languages of (jointly) finite and infinite words). See also the survey paper [S-46]. This extension is very natural and suggests new, interesting ways of extending the classical DST. In [S-55,S-c20], Selivanov further attempts to extend DST to ω-continuous domains and more general topological spaces. Later, the theory was extended by de Brecht, Becher, and Grigorieff to some broader natural classes of spaces, including the so-called quasi-Polish spaces [11].

Selivanov was also keen to effectivize his descriptive set theory for topological spaces. This direction also aims to extend the results about the standard (and other) effective hierarchies of computability theory to as many computable topological spaces as possible. In [S-41,S-42,S-55,S-c20], he attempted to analyze effective ω-algebraic domains, and presented a conjecture on the effective Hausdorff theorem on the difference hierarchy. An extended version of this conjecture was later proposed by Becher and Grigorieff [9]. In [S-c33], Selivanov finally gave an affirmative solution by showing the effective Hausdorff theorem for ω-continuous domains. Other results, such as a partial extension of the Suslin–Kleene theorem, have also been proved. Moreover, in [S-89,S-c46], the fine hierarchy was extended from the discrete space of natural numbers to the computable quasi-Polish spaces; this extension is sometimes named by Selivanov as the effective Wadge hierarchy. Many results on such hierarchies were extended from the case of sets to the case of k-partitions. Furthermore, in [S-89], via a result linking the effective Wadge hierarchies on a represented space and on its name space, he showed the effective Hausdorff theorem for computable quasi-Polish spaces, generalizing several particular such results in the literature. See also the recent survey [S-95] for the contents of this section.

Structure of m -degrees . It is well-known that the Ershov difference hierarchy is closely related to the m-jump operator. It turned out that the generalizations of this operator (also investigated by Selivanov in his habilitation thesis) are connected to the study of structures of m-degrees of index sets of the computably enumerable sets as well as the partial recursive functions. The results led to a simplification and generalization of results by Hay about index sets [S-8,S-11,S-13,S-15].

Q- Wadge degrees . The classical theory of Wadge reducibility or its effective version, many-one reducibility, is aimed at classifying subsets (i.e., two-valued functions), but Selivanov’s enthusiasm was directed toward the theory of Wadge hierarchy for more general codomains. The case of k-partitions (i.e., k-valued functions) of the space of natural numbers was considered by Selivanov in the 1980s, when he introduced and studied the fine hierarchy of arithmetical sets (e.g., [S-13]). Regarding the Wadge theory for general codomains, van Engelen–Miller–Steel [35] showed in the late 1980s that if Q is better-quasi-ordered (bqo), the Wadge degrees of Borel Q-partitions are bqo. Then it is important to analyze the specific shape of this bqo.

In the 1990s, Hertling [20] showed that the structure of the Wadge degrees on the finite level of the trial-and-error hierarchy of k-partitions is isomorphic to the homomorphism quasiorder (h-qo) on finite k-labeled forests. In [S-40], Selivanov also connected the Boolean hierarchy of partitions with the same qo. Moreover, in [S-47], he extended Hertling’s characterization by showing that the structure of the Wadge degrees of Δ 2 0 -measurable k-partitions is isomorphic to the h-qo on countable well-founded k-labeled forests. The idea to go further was born in Selivanov’s research on ω-automata. In [S-c28] he characterized a certain structure on ω-regular k-partitions by using finite forests labeled by finite k-labeled trees. Thus, he recognized that nesting of labeled trees (actually, nesting of h-qo) captures this type of structure. In [S-76], Selivanov suggested that the structure of the Wadge degrees on the finite Borel hierarchy of k-partitions should be isomorphic to the finite levels of the cumulative structure of iterated h-qo on iterated labeled well-founded trees ⊔ Tree ( Tree ( … Tree ( k ) … ) ) , and in [S-c37] he gave a proof for the case of Δ 3 0 -measurable k-partitions.

Kihara and Montalbán [23] noted that what the transfinite cumulative hierarchy of iterated labeled trees exhausts is only the ω-rank of the Borel hierarchy. To break out of this difficulty, by incorporating ω 1 types of different labeling functions (Veblen-like functions), Kihara–Montalbán achieved a complete description of the Wadge degrees of Borel Q-partitions. In [S-87], Selivanov characterized this transfinite cumulative hierarchy of trees with ω 1 types of labelings as a free structure using generators and relators with infinitary ω-ary operations. The paper [S-93,S-c46] also discusses the effective version of the Q-Wadge hierarchy. In the survey [S-84] Selivanov systematically developed his suggestion (in several earlier papers) to use wqo-theory in the study of hierarchies of k-partitions, thus contributing to the general hierarchy theory.

Wadge(-like) hierarchies in quasi-Polish spaces . As already mentioned above, Selivanov studied Wadge degrees on several domains in [S-43,S-c9]. More recently, after the notion of quasi-Polish space was established, he shifted the focus of his research on Wadge degrees there. This direction is also motivated by the desire to extend Wadge degrees from zero-dimensional to non-zero dimensional spaces. This is a non-trivial task because the structure of Wadge degrees in most of non-zero-dimensional spaces contains infinite descending chains and infinite antichains, being thus completely opposite to wqos.

One approach, initiated by Martin, Andretta, and Motto Ros [1,29], employs the so-called Wadge-like reducibilies which use broader classes of reducing functions than continuous functions. The main consideration is reducibility by special Borel functions, e.g., D α -functions (those whose preimage function preserves Σ α 0 ). In [S-71] Selivanov (jointly with Motto Ros and Schlicht) investigated the structure of D α -reducibility degrees in various non-zero dimensional spaces and domain-theoretic spaces. In [S-91] (jointly with Kihara) he extended Kihara–Montalbán’s iterated tree characterization of Wadge degrees to D α -reducibility degrees.

The second approach is to use an intentional Wadge reducibility, which was independently proposed by Pequignot [32] and Selivanov [S-76]. This approach was thoroughly analyzed in [S-92]. In a sense, a represented space is zero-dimensional at the intentional level (as it is represented by Baire space), so the “intentional” Wadge degree has the iterated tree characterization, that corresponds to the infinitary fine hierarchy. In [S-92], Selivanov used the Baire category theorem to show that in a space with a nice representation, such as a quasi-Polish space, the intentional and extensional infinitary fine hierarchies coincide. In this sense, a quasi-Polish space, even if it is not zero-dimensional, always involves a very orderly hierarchical structure.

ω- Boolean operations . In the early days of classical DST, Kantorovich and Livenson studied the notion of ω-ary Boolean operation (also known as quantifier on ω), which generalizes the Suslin operation. Note that any set Q ⊆ P ω yields an ω-ary operation, which transforms a sequence ( U n ) of sets into the set of all x such that x ∈ U n for Q -many n, i.e., { n : x ∈ U n } ∈ Q . Early researchers in the Wadge theory found this notion useful in the analysis of Wadge degrees. In the 1970s, Wadge and his associates [36,37] noticed that each non-selfdual Borel Wadge class Γ corresponds to a single Borel quantifier Q (i.e., an ω-operation obtained from a single Borel set) in the sense that Γ coincides with the collection of all sets definable by applying Q to clopen sets, and vice versa. An important observation was that there is a correspondence between the top Wadge degree in Γ and the Wadge degree of Q . Their classical work focused on the Cantor complexity of Q , but Selivanov [S-30,S-42,S-44] also focused on the complexity of Q in the Scott domain. In [S-c49], he completely characterised the ω-ary Boolean operations which generate (starting with the class of open sets) any given non-selfdual level of the Wadge hierarchy, in terms of the infinitary fine hierarchy in the Scott domain. This result concludes a series of his partial earlier results in this direction.

3. Computability and complexity in countable and represented structures

Definability and complexity issues . In a series of papers (together with Kudinov, Yartseva, and Zhukov), Selivanov developed new methods for the investigation of first-order definability for countable structures. The methods apply to some popular structures consisting of words and labeled trees [S-57,S-58,S-62,S-63]. These works gave several comprehensive definability results for the degree structures, naturally arising in topology and computable analysis (in particular, for many initial segments of the Wadge and Weihrauch degrees of k-partitions). This provided a first step in the development of a degree theory for topological structures (in parallel to the classical degree theory for discrete structures). Independently (and almost simultaneously), a similar research program for definability issues in finite structures was initiated by McKenzie and his research group (see Section 3.4 of the survey [S-84] for some related references).

Selivanov and Hertling [S-68,S-c29] also characterized the complexity of several natural problems in the structures of labeled forests.

Computability and complexity in linear algebra . This direction is highly developed for general computability but much less developed for subrecursive computability (which is in fact more relevant to computer science). The research in this direction is reflected in Selivanov’s joint works with Alaev and Selivanova [S-75,S-77,S-80,S-83,S-88,S-90,S-94,S-c38,S-c39,S-c45,S-c47]. The main attention was paid to primitive recursive (PR) computability (actively developed now by many researchers [7,22]) and polynomial-time computability. Ideologically this direction is closely related to symbolic algorithms of computer algebra.

Alaev and Selivanov [S-80,S-83,S-90,S-c38] studied polynomial-time computability for various familiar algebraic structures. In particular, they showed that three popular (in the literature on computer algebra) presentations of the ordered field of algebraic reals are polynomially equivalent. In [S-c45], Alaev and Selivanov initiated investigations of presentations of algebraic structures in the levels of the Grzegorczyk hierarchy.

These results were used by Selivanova and Selivanov in [S-88,S-c39] to prove polynomial-time computability of spectral decompositions of symmetric matrices under certain natural conditions; see also their previously derived sufficient conditions (in terms of feasible presentability of numbered field of coefficients) of computability of spectral problems in [S-75,S-77], as well as PR analogs of these results in [S-94,S-c47]. These works develop new connections between numerical methods and methods of computer algebra.

Computability and complexity in analysis . This direction was motivated by the intention to develop solid mathematical foundations for numerical algorithms with guaranteed precision. The foundation is based on the approach to computability on the reals initiated by A. Turing and developed by many mathematicians around the world, see, e.g., the books [38] (for computable analysis), [24] (for real complexity theory), and references therein. The research in this direction is reflected in Selivanov’s joint works with Selivanova [S-56,S-59,S-75,S-77,S-88,S-94,S-c39,S-c47].

The main attention was paid to computability and complexity of solution operators of symmetric hyperbolic partial differential equations (PDEs), for which also spectral decomposition results (see previous subsection) were used. The papers [S-56,S-59,S-75,S-77] provide sufficient conditions of computability for initial-value and boundary-value problems. In [S-88,S-c39], complexity upper bounds are established and sufficient conditions for polynomial-time computability are derived. The papers [S-94,S-c47] introduce and study the notion of a primitive recursive metric space. In particular, PR root-finding algorithms in the PR real and algebraic closures of PR fields with a certain property (PR splitting) are obtained, and the corresponding fields are related to the PR reals. It enables the derivation of sufficient conditions for PR computing of normal forms of matrices and solution operators of symmetric hyperbolic systems of PDEs. The methods represent a mix of symbolic and approximate algorithms.

The obtained results correspond well to computational experience with such PDEs in numerical mathematics. Moreover, some of the results have been later used by other authors to obtain more general complexity results, as well as to develop exact real computation methods (see [31] on the exact real computation approach) for broad classes of PDE systems. For details see the survey [33] and references therein.

Computable topology . Computable topology is now a popular topic since its notions are widely used in computable analysis and effective DST. Computability in topology is much less straightforward than computability in algebra, since the first deals mostly with uncountable structures. Accordingly, there are many non-equivalent approaches to computability in topological spaces, even in Polish spaces and algebraic and continuous domains.

As already mentioned in Section 2, in [S-41,S-42,S-46,S-55,S-c33] Selivanov developed effective DST on domain-theoretic spaces. More recently, in [S-85], Selivanov initiated the study of degree spectra of topological spaces and demonstrated the role of different presentations of spaces. This work was the catalyst for the entry of numerous researchers into the study of degree spectra of topological spaces, especially Polish spaces [8,12,19,26,28], though this work itself was mainly done for non-Polish spaces: In [S-85] Selivanov pointed out the correspondence between the degree spectra of (homeomorphism types of) ω-algebraic domains and those of (isomorphism types of) partial orders. The full version of [S-c48] also discusses some degree spectra of ω-continuous domains. In [S-c42] Selivanov (jointly with Hoyrup and Kihara) announced that they have solved various problems on degree spectra of Polish spaces. In the full version, they show, for example, the existence of low 3 -presented compact Polish spaces that are not homeomorphic to any computable Polish space (using some homological idea), and the existence of compact Polish spaces with no easiest presentation with respect to Turing reducibility (using the notion of Z-set in topological dimension theory).

Selivanov’s article [S-c40] (jointly with Hoyrup, Rojas, and Stull) was among the first studying the computability of quasi-Polish spaces. In [S-c48] Selivanov (jointly with de Brecht and Kihara) initiated the investigation of numberings and index sets of natural classes of computable spaces and continued the study of ideal presentations of quasi-Polish spaces by de Brecht–Pauly–Schröder. See also the survey [S-95].

Descriptive complexity of q c b 0 -spaces . An admissibly represented space, a key notion in modern computable analysis, corresponds to a q c b 0 -space (the quotient of a countably based T 0 space); and a countably based space with a total admissible representation corresponds to a quasi-Polish space. In [S-66], Selivanov provided an exhaustive study of spaces with total representation in general. Based on the well-known correspondence between represented spaces and partial equivalence relations (PER) on names, in [S-69,S-70,S-c32], Selivanov (jointly with Schröder) considered classifying admissibly represented spaces according to the descriptive complexity of the PERs. Building on classical studies of Normann and others on higher-type functionals [30], it was shown in [S-69], for example, that the PER-complexity of the Kleene–Kreisel space of type k + 1 functionals is Π k 1 but not Σ k 1 . Using this idea, they showed that the category of q c b 0 -spaces with projective PER-complexity is cartesian closed. In [S-70,S-c32], the approach was extended to the hyperprojective hierarchy. Jointly with de Brecht and Schröder, Selivanov considered a continuous indexing of an open basis, and proposed a classification of spaces based on possible index spaces [S-72,S-c34]. For example, together with the above result, it was shown that continuous indexability by the ( k + 1 ) st Kleene–Kreisel space and by Π k 1 sets of Baire space are equivalent. Again, see the recent survey [S-95].