Matthias Schröder has asked the question whether there is a weakest discontinuous problem in the topological version of the Weihrauch lattice. Such a problem can be considered as the weakest unsolvable problem. We introduce the discontinuity problem, and we show that it is reducible exactly to the effectively discontinuous problems, defined in a suitable way. However, in which sense this answers Schröder’s question sensitively depends on the axiomatic framework that is chosen, and it is a positive answer if we work (...) in Zermelo–Fraenkel set theory with dependent choice and the axiom of determinacy $\mathsf {AD}$. On the other hand, using the full axiom of choice, one can construct problems which are discontinuous, but not effectively so. Hence, the exact situation at the bottom of the Weihrauch lattice sensitively depends on the axiomatic setting that we choose. We prove our result using a variant of Wadge games for mathematical problems. While the existence of a winning strategy for Player II characterizes continuity of the problem (as already shown by Nobrega and Pauly), the existence of a winning strategy for Player I characterizes effective discontinuity of the problem. By Weihrauch determinacy we understand the condition that every problem is either continuous or effectively discontinuous. This notion of determinacy is a fairly strong notion, as it is not only implied by the axiom of determinacy $\mathsf {AD}$, but it also implies Wadge determinacy. We close with a brief discussion of generalized notions of productivity. (shrink)

We obtain several game characterizations of Baire 1 functions between Polish spaces _X_, _Y_ which extends the recent result of V. Kiss. Then we propose similar characterizations for equi-Bare 1 families of functions. Also, using related ideas, we give game characterizations of Baire measurable and Lebesgue measurable functions.

Assuming AD + DC, we characterize the self-dual boldface pointclasses which are strictly larger than the pointclasses contained in them: these are exactly the clopen sets, the collections of all sets of Wadge rank [Formula: see text], and those of Wadge rank [Formula: see text] when ξ is limit.

If is a Polish metric space of dimension 0, then by Wadge’s lemma, no more than two Borel subsets of X are incomparable with respect to continuous reducibility. In contrast, our main result shows that for any metric space of positive dimension, there are uncountably many Borel subsets of that are pairwise incomparable with respect to continuous reducibility. In general, the reducibility that is given by the collection of continuous functions on a topological space \\) is called the Wadge quasi-order (...) for \\). As an application of the main result, we show that this quasi-order, restricted to the Borel subsets of a Polish space \\), is a well-quasiorder if and only if \\) has dimension 0. Moreover, we give further examples of applications of the construction of graph colorings that is used in the proofs. (shrink)

We present a general way of defining various reduction games on ω which “represent” corresponding topologically defined classes of functions. In particular, we will show how to construct games for piecewise defined functions, for functions which are pointwise limit of certain sequences of functions and for Γ-measurable functions. These games turn out to be useful as a combinatorial tool for the study of general reducibilities for subsets of the Baire space [10].

In [9] we have considered a wide class of "well-behaved" reducibilities for sets of reals. In this paper we continue with the study of Borel reducibilities by proving a dichotomy theorem for the degree-structures induced by good Borel reducibilities. This extends and improves the results of [9] allowing to deal with a larger class of notions of reduction (including, among others, the Baire class ξ functions).

We show that if Ƒ is any "well-behaved" subset of the Borei functions and we assume the Axiom of Determinacy then the hierarchy of degrees on $P(^\omega \omega )$ induced by Ƒ turns out to look like the Wadge hierarchy (which is the special case where Ƒ is the set of continuous functions).

Duparc introduced a two-player game for a function f between zero-dimensional Polish spaces in which Player II has a winning strategy iff f is of Baire class 1. We generalize this result by defining a game for an arbitrary function f : X → Y between arbitrary Polish spaces such that Player II has a winning strategy in this game iff f is of Baire class 1. Using the strategy of Player II, we reprove a result concerning first return recoverable (...) functions. (shrink)

Every computable function has to be continuous. To develop computability theory of discontinuous functions, we study low levels of the arithmetical hierarchy of nonuniformly computable functions on Baire space. First, we classify nonuniformly computable functions on Baire space from the viewpoint of learning theory and piecewise computability. For instance, we show that mind-change-bounded learnability is equivalent to finite View the MathML source2-piecewise computability 2 denotes the difference of two View the MathML sourceΠ10 sets), error-bounded learnability is equivalent to finite View (...) the MathML sourceΔ20-piecewise computability, and learnability is equivalent to countable View the MathML sourceΠ10-piecewise computability . Second, we introduce disjunction-like operations such as the coproduct based on BHK-like interpretations, and then, we see that these operations induce Galois connections between the Medvedev degree structure and associated Medvedev/ Muchnik-like degree structures. Finally, we interpret these results in the context of the Weihrauch degrees and Wadge-like games. (shrink)