Forests describing Wadge degrees and topological Weihrauch degrees of certain classes of functions and relations

Abstract

We introduce notions of continuous strong Weihrauch reducibility and of continuous Weihrauch reducibility for functions with range in a preordered set. Then we associate with such functions certain labeled forests and trees and show that Wadge reducibility, continuous strong Weihrauch reducibility and continuous Weihrauch reducibility between such functions can be characterized by suitable reducibility relations between the associated forests when they are defined. This leads to a combinatorial description of the initial segments of these three hierarchies for those functions defined on the Baire space that have countable range in a bqo set and that are $Σ_{2}^{0}$ -measurable with respect to the reverse Alexandroff topology on the bqo set. Furthermore, we show that the characterization of the topological reducibility relations for bqo-valued functions can be used in order to obtain a similar characterization for the usual Wadge reducibility relation, the continuous strong Weihrauch reducibility relation, and the continuous Weihrauch reducibility relation for multi-valued functions with finite range.

Keywords

Relations Wadge reducibility continuous strong Weihrauch reducibility continuous Weihrauch reducibility labeled forests better-quasi-orders

Get full access to this article

View all access options for this article.

References

Brattka, Computability over topological structures, in: Computability and Models,

S.B.

Cooper and

S.S.

Goncharov, eds, Kluwer Academic Publishers, New York, 2003, pp. 93–136. doi:10.1007/978-1-4615-0755-0_5.

Brattka,

Gherardi and

Pauly, Weihrauch complexity in computable analysis, arXiv.orgarXiv:1707.03202v4 (2018).

K.J.

Devlin, Fundamentals of Contemporary Set Theory, Springer, Berlin, 1979. doi:10.1007/978-1-4684-0084-7.

Gherardi and

Marcone, How incomputable is the separable Hahn–Banach theorem?, Notre Dame Journal of Formal Logic50(4) (2009), 393–425. doi:10.1215/00294527-2009-018.

Goubault-Larrecq, Non-Hausdorff Topology and Domain Theory, Cambridge University Press, Cambridge, 2013. doi:10.1017/CBO9781139524438.

Hertling, A topological complexity hierarchy of functions with finite range, Technical report, 223, Centre de recerca matematica, Institut d’estudis catalans, Barcelona, 1993, Workshop on Continuous Algorithms and Complexity.

Hertling, Topologische Komplexitätsgrade von Funktionen mit endlichem Bild, Informatik Berichte, 152, FernUniversität Hagen, Hagen, 1993.

Hertling, Unstetigkeitsgrade von Funktionen in der effektiven Analysis, PhD thesis, Fachbereich Informatik, FernUniversität Hagen, 1996.

Hertling and

Selivanov, Complexity issues for preorders on finite labeled forests, in: Logic, Computation, Hierarchies,

Brattka,

Diener and

Spreen, eds, Ontos Mathematical Logic, Walter de Gruyter, Boston, 2014, pp. 165–190.

10.

M.D.

Hirsch, Applications of topology to lower bound estimates in computer science, in: From Topology to Computation: Proceedings of the Smalefest, Springer-Verlag, New York, 1993, pp. 395–418, Papers presented at the conference “From topology to computation: Unity and diversity in the mathematical sciences” held at the University of California at Berkeley, USA, August 5-9, 1990 in honor of Stephen Smale’s 60th birthday. doi:10.1007/978-1-4612-2740-3_37.

11.

A.S.

Kechris, Classical Descriptive Set Theory, Graduate Texts in Mathematics, Vol. 156, Springer-Verlag, 1995. doi:10.1007/978-1-4612-4190-4.

12.

Kihara and

Montalbán, On the structure of the Wadge degrees of bqo-valued Borel functions, Trans. Am. Math. Soc.371(11) (2019), 7885–7923. doi:10.1090/tran/7621.

13.

Kreitz and

Weihrauch, Theory of representations, Theoretical Computer Science38 (1985), 35–53. doi:10.1016/0304-3975(85)90208-7.

14.

Laver, Better-quasi-orderings and a class of trees, in: Studies in Foundations and Combinatorics, Adv. Math., Suppl. Stud., Vol. 1, 1978, pp. 31–48.

15.

C.S.J.A.

Nash-Williams, On well-quasi-ordering infinite trees, Proc. Camb. Philos. Soc.61 (1965), 697–720. doi:10.1017/S0305004100039062.

16.

Schröder, Admissible representations for continuous computations, PhD thesis, Fachbereich Informatik, FernUniversität Hagen, 2002.

17.

Schröder, Extended admissibility, Theoretical Computer Science284(2) (2002), 519–538. doi:10.1016/S0304-3975(01)00109-8.

18.

V.L.

Selivanov, Hierarchies of

Δ_{2}^{0}

-measurable k-partitions, Mathematical Logic Quarterly53(4–5) (2007), 446–461. doi:10.1002/malq.200710011.

19.

V.L.

Selivanov, Extending Wadge theory to k-partitions, in: Unveiling Dynamics and Complexity,

Kari,

Manea and

Petre, eds, Lecture Notes in Computer Science, Vol. 10307, Springer, Cham, 2017, pp. 387–399, 13th Conference on Computability in Europe, CiE 2017, Turku, Finland, June 12–16, 2017. doi:10.1007/978-3-319-58741-7_36.

20.

V.L.

Selivanov, Towards a descriptive theory of

{cb}_{0}

-spaces, Math. Structures Comput. Sci.27(8) (2017), 1553–1580. doi:10.1017/S0960129516000177.

21.

S.G.

Simpson, BQO theory and Fraissés conjecture, in: R. Mansfield and G. Weitkamp: Recursive Aspects of Descriptive Set Theory. With a Chapter by Stephen Simpson, Oxford University Press, Oxford, 1985, pp. 124–138.

22.

van Engelen,

A.W.

Miller and

Steel, Rigid Borel sets and better quasiorder theory, in: Logic and Combinatorics, Contemp. Math., Vol. 65, 1987, pp. 199–222, Proc. AMS-IMS-SIAM Conf., Arcata/Calif. 1985.

23.

von Stein, Vergleich nicht konstruktiv lösbarer Probleme in der Analysis, 1989, Diplomarbeit, Fakultät für Informatik, FernUniversität Hagen.

24.

W.W.

Wadge, Reducibility and determinateness on the Baire space, PhD thesis, University of California, Berkeley, 1984.

25.

Weihrauch, The degrees of discontinuity of some translators between representations of the real numbers, Informatik Berichte, 129, FernUniversität Hagen, Hagen, 1992.

26.

Weihrauch, The TTE-interpretation of three hierarchies of omniscience principles, Informatik Berichte, 130, FernUniversität Hagen, Hagen, 1992.