1 Introduction
The Weihrauch lattice has been used as a computability-theoretic framework to analyze the uniform computational content of mathematical problems from many different areas of mathematics, and it can also be seen as a uniform variant of reverse mathematics (a recent survey on Weihrauch complexity can be found in [Reference Brattka, Gherardi, Pauly, Brattka and Hertling9]). The notion of a mathematical problem has a very general definition in this approach.
Definition 1.1 (Problems)
A problem is a multi-valued function
$f:\subseteq X\rightrightarrows Y$
on represented spaces
$X,Y$
that has a realizer.
We recall that by a realizer
$F:\subseteq {\Bbb {N}}^{\Bbb {N}}\to {\Bbb {N}}^{\Bbb {N}}$
of f, we mean a function F that satisfies
$\delta _YF(p)\in f\delta _X(p)$
for all
$p\in {\mathrm {dom}}(f\delta _X)$
, where
$\delta _X:\subseteq {\Bbb {N}}^{\Bbb {N}}\to X$
and
${\delta _Y:\subseteq {\Bbb {N}}^{\Bbb {N}}\to Y}$
are the representations of X and Y, respectively (i.e., partial surjective maps onto X and Y, respectively).
We note that we have added the condition here that a problem has to have a realizer, since we want to prove all our results over the base theory of Zermelo–Fraenkel set theory (
$\mathsf {ZF}$
) together with the axiom of dependent choice (
$\mathsf {DC}$
), if not otherwise mentioned. These axioms suffice to prove most results in Weihrauch complexity. Typically, the full axiom of choice (
$\mathsf {AC}$
) is freely used in Weihrauch complexity, often just to guarantee the existence of some realizer. By
$\langle p,q\rangle $
we denote the usual pairing function on
${\Bbb {N}}^{\Bbb {N}}$
, defined by
$\langle p,q\rangle (2n)=p(n)$
,
$\langle p,q\rangle (2n+1)=q(n)$
for all
$p,q\in {\Bbb {N}}^{\Bbb {N}},n\in {\Bbb {N}}$
. Weihrauch reducibility can now be defined as follows.
Definition 1.2 (Weihrauch reducibility)
Let
$f:\subseteq X\rightrightarrows Y$
and
$g:\subseteq W\rightrightarrows Z$
be problems. Then f is called Weihrauch reducible to g, in symbols
$f\mathop {\leq _{\mathrm {W}}} g$
, if there are computable
$H,K:\subseteq {\Bbb {N}}^{\Bbb {N}}\to {\Bbb {N}}^{\Bbb {N}}$
such that
$H\langle {\mathrm {id}},GK\rangle $
is a realizer of f whenever G is a realizer of g. Analogously, one says that f is strongly Weihrauch reducible to g, in symbols
$f\mathop {\leq _{\mathrm {sW}}} g$
, if the expression
$H\langle {\mathrm {id}},GK\rangle $
can be replaced by
$HGK$
. Both versions of the reducibility have topological counterparts, where one requires
$H,K$
only to be continuous and these reducibilities are denoted by
$\leq _{\mathrm {W}}^*$
and
$\leq _{\mathrm {sW}}^*$
, respectively.
The topological version of Weihrauch reducibility has always been studied alongside the computable version, and all four reducibilities induce a lattice structure (see [Reference Brattka, Gherardi, Pauly, Brattka and Hertling9] for references). Normally, the Weihrauch lattice refers to the lattice induced by
$\mathop {\leq _{\mathrm {W}}}$
, but here we will freely use this term also for the lattice structure induced by
$\leq _{\mathrm {W}}^*$
. If we want to be more precise, we will call the latter the topological Weihrauch lattice. Even though this lattice has been studied for about 30 years, very little is known about the structure of the lattice closer towards the bottom. Indeed Matthias Schröder has asked the following questionFootnote
1
[Reference Brattka, Dzhafarov, Marcone and Pauly6, Question 5.9].
Question 1.3 (Matthias Schröder, 2018)
Does there exist a discontinuous problem f such that
$f\leq _{\mathrm {W}}^*g$
holds for any other discontinuous problem g?
Here a problem is called continuous if it has a continuous realizer and discontinuous otherwise. It is clear that the degree
$0$
of the nowhere defined problems f is the bottom degree of the (continuous) Weihrauch lattice. The second lowest degree, sometimes called
$1$
, is the degree of the identity
${\mathrm {id}}:{\Bbb {N}}^{\Bbb {N}}\to {\Bbb {N}}^{\Bbb {N}}$
that includes all somewhere defined continuous problems.Footnote
2
Essentially Schröder’s question is whether there is a third degree
$2$
such that the topological Weihrauch lattice starts with the linear ordered structure
$0<1<2$
. We will prove that under certain conditions this is indeed so, namely there is such a third degree given by the problem
$$ \begin{align*} \mathsf{DIS}:{\Bbb{N}}^{\Bbb{N}}\rightrightarrows{\Bbb{N}}^{\Bbb{N}},p\mapsto\{q\in{\Bbb{N}}^{\Bbb{N}}:{\mathsf{{U}}}(p)\not=q\} \end{align*} $$
that we call the discontinuity problem (see Definition 3.2). Here
${\mathsf {{U}}}:\subseteq {\Bbb {N}}^{\Bbb {N}}\to {\Bbb {N}}^{\Bbb {N}}$
is a fixed universal computable function.
In Section 3 we prove that the discontinuity problem
$\mathsf {DIS}$
characterizes effectively discontinuous problems in the following sense (see Theorem 3.4).
Theorem 1.4 (Continuity and effective discontinuity)
Let
$f:\subseteq X\rightrightarrows Y$
be a problem. Then we obtain
-
(1)
$f\leq _{\mathrm {W}}^*{\mathrm {id}}\iff f$
is continuous, -
(2)
$\mathsf {DIS}\leq _{\mathrm {W}}^*f\iff f$
is effectively discontinuous.
The diagram in Figure 1 illustrates the situation. Here effective discontinuity of a problem f is defined in a very natural way (see Definition 3.1) using a continuous discontinuity function
$D:{\Bbb {N}}^{\Bbb {N}}\to {\Bbb {N}}^{\Bbb {N}}$
that has to produce an input to every given potential continuous realizer of f on which this realizer fails.
Figure 1 Problems
$f:\subseteq X\rightrightarrows Y$
with respect to
$\leq _{\mathrm {W}}^*$
and
$\leq _{\mathrm {sW}}^*$
.
In some sense the notion of effective discontinuity is reminiscent of the notion of productivity from classical computability theory, which can be regarded as the property of being “effectively not c.e.” Indeed a well-known theorem of Myhill [Reference Myhill18] gives us the analog of Theorem 1.4 for subsets
$A\subseteq {\Bbb {N}}$
and many-one reducibility
$\mathop {\leq _{\mathrm {m}}}$
[Reference Soare25, Theorem 2.4.6], [Reference Weihrauch29, Theorem 2.6.6]. Here the halting problem
${\mathsf {{K}}}\subseteq {\Bbb {N}}$
plays the counterpart of the identity and
${\Bbb {N}}\setminus {\mathsf {{K}}}$
the counterpart of
$\mathsf {DIS}$
.
Theorem 1.5 (Myhill, 1955)
Let
$A\subseteq {\Bbb {N}}$
. Then we obtain
-
(1)
$A\mathop {\leq _{\mathrm {m}}} {\mathsf {{K}}}\iff A$
is c.e., -
(2)
${\Bbb {N}}\setminus {\mathsf {{K}}}\mathop {\leq _{\mathrm {m}}} A\iff A$
is productive.
The diagram in Figure 2 illustrates the situation. In fact, Theorem 1.4 is proved with the help of the recursion theorem, in a similar way as Theorem 1.5. However, somewhat surprisingly, the recursion theorem is used for the implication “
$\Longleftarrow $
” in the proof of Theorem 1.5(2) and for the direction “
$\Longrightarrow $
” in the proof of Theorem 1.4(2).
Figure 2 Sets
$A\subseteq {\Bbb {N}}$
with respect to many-one reducibility
$\leq _{\mathrm {m}}$
.
It is well known that Theorem 1.5 does not express a dichotomy, i.e., there are sets which are neither c.e. nor productive. A set
$A\subseteq {\Bbb {N}}$
is called immune if it is infinite, but does not include an infinite c.e. set [Reference Soare25, Reference Weihrauch29]. By a classical construction of Post immune sets exist [Reference Post23], [Reference Soare25, Theorem 5.2.3], [Reference Weihrauch29, Theorem 2.3.7] and they are clearly neither c.e. nor productive, since any productive set contains an infinite c.e. subset (see Figure 2).
Now a key question for us is whether there is a counterpart of immune sets in our situation, i.e., whether there are problems f that are discontinuous, but not effectively so (see the question mark in Figure 1). In fact, Post’s construction of a simple set has some similarity to the construction of so-called Bernstein sets that can actually be used to construct discontinuous problems that are not effectively discontinuous (see Corollary 3.9). This leads to the following counterexample (see Theorem 3.10).
Theorem 1.6. Assuming
$\mathsf {ZFC}$
there are problems
$f:{\Bbb {N}}^{\Bbb {N}}\rightrightarrows {\Bbb {N}}^{\Bbb {N}}$
that are continuous, but not effectively so.
In Section 4 we prove that the axiom of choice is actually required for such a construction. This can be achieved with the help of a variant of Wadge games for problems
$f:\subseteq X\rightrightarrows Y$
, originally considered by Nobrega and Pauly [Reference Nobrega20, Reference Nobrega and Pauly21]. In fact, we can prove the following result (see Theorem 4.3), part (1) of which is already due to Nobrega and Pauly.
Theorem 1.7 (Wadge games)
We consider the Wadge game of a given problem
${f:\subseteq X\rightrightarrows Y}$
. Then the following hold:
-
(1) f is continuous
$\iff $
Player II has a winning strategy for f, -
(2) f is effectively discontinuous
$\iff $
Player I has a winning strategy for f.
This result implies that under the axiom of determinacy (
$\mathsf {AD}$
), which states that every Gale–Stewart game is determined, i.e., either Player I or Player II has a winning strategy, we really obtain a dichotomy between continuity and effective discontinuity (see Corollary 4.11).
Corollary 1.8. In
$\mathsf {ZF}+\mathsf {DC}+\mathsf {AD}$
every problem
$f:\subseteq X\rightrightarrows Y$
is either continuous or effectively discontinuous.
This can be proved by a suitable reduction of the Wadge game to a Gale–Stewart game. By Weihrauch determinacy we understand the condition that every problem
$f:\subseteq X\rightrightarrows Y$
is either continuous or effectively discontinuous. Then Corollary 1.8 can also be rephrased such that
$\mathsf {AD}$
implies Weihrauch determinacy. On the other hand, it is easy to see that Wadge games for problems
$f:\subseteq X\rightrightarrows Y$
generalize Wadge games for subsets
$A,B\subseteq {\Bbb {N}}^{\Bbb {N}}$
as originally considered by Wadge and hence Weihrauch determinacy implies Wadge determinacy, which means that every Wadge game for subsets
$A,B\subseteq {\Bbb {N}}^{\Bbb {N}}$
is determined (see Figure 3).
Figure 3 Determinacy properties in
$\mathsf {ZF}+\mathsf {DC}$
.
We leave it open how Weihrauch determinacy is exactly related to the other given notions of determinacy. We just mention that it is not known whether Wadge determinacy implies
$\mathsf {AD}$
, and in fact there is the following conjecture attributed to Solovay (by Andretta [Reference Andretta1]Footnote
3
).
Conjecture 1.9 (Solovay)
In
$\mathsf {ZF}+V=L({\Bbb {R}})$
Wadge determinacy is equivalent to the axiom of determinacy
$\mathsf {AD}$
.
We have some partial results (see Proposition 4.15) that suggest that Weihrauch determinacy is actually even closer related to
$\mathsf {AD}$
than Wadge determinacy.
In any case, our results show that the exact situation at the bottom of the topological Weihrauch lattice sensitively depends on the underlying axioms. Using
$\mathsf {AD}$
we obtain the following result (as a consequence of Corollary 1.8).
Theorem 1.10. In
$\mathsf {ZF}+\mathsf {DC}+\mathsf {AD}$
the topological Weihrauch lattice starts with three linearly ordered degrees, represented by
$0\leq _{\mathrm {W}}^*{\mathrm {id}}\leq _{\mathrm {W}}^*\mathsf {DIS}$
.
If we replace
$\mathsf {AD}$
by the axiom of choice
$\mathsf {AC}$
, then the linear part of the order at the bottom is just
$0\leq _{\mathrm {W}}^*{\mathrm {id}}$
and the situation becomes more complicated afterwards (and by Theorem 3.10 this is even true if we move to the coarser parallelized version of the Weihrauch lattice).
We briefly summarize the structure of this article. In Section 2 we provide the version of the recursion theorem that we are going to use for the proof of our characterization of effectively discontinuous problems via the discontinuity problem. We also introduce the universal function
${\mathsf {{U}}}$
and other related concepts. In Section 3 we introduce the discontinuity problem, the notion of effective discontinuity, and we prove related results. In Section 4 we characterize effective discontinuity using Wadge games and we study the relation to determinacy of other games such as Lipschitz games and Gale–Stewart games. In Section 5 we briefly discuss computable discontinuity of characteristic functions and we indicate how this is related to (suitable generalizations of) the notion of productivity. In the conclusions (Section 6) we mention a number of open problems and suggestions for further directions of research.
2 The universal function and the recursion theorem
We recall that a function
$F:\subseteq {\Bbb {N}}^{\Bbb {N}}\to {\Bbb {N}}^{\Bbb {N}}$
is computable, if there is some computable monotone word function
$f:{\Bbb {N}}^*\to {\Bbb {N}}^*$
that approximates F in the sense that
$F(p)=\sup _{w\sqsubseteq p}f(w)$
holds for all
$p\in {\mathrm {dom}}(F)$
. Likewise, F is continuous if and only if an analogous condition holds for an arbitrary monotone word function f. Hence, we can define a representation
$\Phi $
of the set of all continuous functions
$F:\subseteq {\Bbb {N}}^{\Bbb {N}}\to {\Bbb {N}}^{\Bbb {N}}$
(with natural domainsFootnote
4
) by encoding graphs of monotone word functions f into names of F. In other words, if
$\mathsf {w}:{\Bbb {N}}\to {\Bbb {N}}^*$
is a standard bijective numbering of
${\Bbb {N}}^*$
, then
$p=\langle n_0,k_0\rangle \langle n_1,k_1\rangle \ldots $
is a name of an extension
$\Phi _p$
of F if F is approximated by some monotone
$f:{\Bbb {N}}^*\to {\Bbb {N}}^*$
with
$f(\mathsf {w}_{n_i})=\mathsf {w}_{k_i}$
and for each
$p\in {\mathrm {dom}}(F)$
and
$n\in {\Bbb {N}}$
there is some
$i\in {\Bbb {N}}$
with
$\mathsf {w}_{n_i}\sqsubseteq p$
and
$|\mathsf {w}_{n_i}|>n$
. Here
$\langle n,k\rangle :=\frac {1}{2}(n+k)(n+k+1)+k$
denotes the usual Cantor pairing function for
$n,k\in {\Bbb {N}}$
. Intuitively,
$F=\Phi _p$
means that p is a listing of a sufficiently large portion of the graph of a monotone function
$f:{\Bbb {N}}^*\to {\Bbb {N}}^*$
that approximates F. In order to guarantee that
$\Phi $
is a total representation, one still needs to clarify how to deal with inconsistent names p, i.e., names for which there is no suitable word function f. Inconsistency can be recognized (i.e., inconsistent names form an open set) and hence one can just consider those p as names of the nowhere defined function. See [Reference Weihrauch29, Definition 3.2.9] for the technical details of such a construction of
$\Phi $
.
Now we can define a computable universal function
$$ \begin{align*} {\mathsf{{U}}}:\subseteq{\Bbb{N}}^{\Bbb{N}}\to{\Bbb{N}}^{\Bbb{N}},\langle q,p\rangle\mapsto\Phi_q(p), \end{align*} $$
for all
$p,q\in {\Bbb {N}}^{\Bbb {N}}$
[Reference Weihrauch29, Theorem 3.2.16(1)]. Weihrauch [Reference Weihrauch28, Theorems 2.10 and 3.5 and Corollary 2.11] (see also [Reference Weihrauch29, Theorem 3.2.16]) proved the following version of the smn-theorem for the representation
$\Phi $
that comes in a version for computable and a version for continuous functions.
Theorem 2.1 (smn-Theorem)
For every computable (continuous) partial function
$F:\subseteq {\Bbb {N}}^{\Bbb {N}}\to {\Bbb {N}}^{\Bbb {N}}$
there exists a computable (continuous) total function
$S:{\Bbb {N}}^{\Bbb {N}}\to {\Bbb {N}}^{\Bbb {N}}$
such that
$\Phi _{S(q)}(p)=F\langle q,p\rangle $
for all
$p,q\in {\Bbb {N}}^{\Bbb {N}}$
.
Among other things this result implies that
$\Phi $
is precomplete. We recall that in general a representation
$\delta :\subseteq {\Bbb {N}}^{\Bbb {N}}\to X$
of a set X is called precomplete, if for every computable
$F:\subseteq {\Bbb {N}}^{\Bbb {N}}\to {\Bbb {N}}^{\Bbb {N}}$
there exists a total computable
$G:{\Bbb {N}}^{\Bbb {N}}\to {\Bbb {N}}^{\Bbb {N}}$
such that
$\delta F(p)=\delta G(p)$
for all
$p\in {\mathrm {dom}}(F)$
. In other words, precomplete representations are exactly those under which partial computable functions can be extended to total ones.
Using the smn-theorem one can prove the following uniform version of the recursion theorem along the same lines as the classical recursion theorem. It is an immediate corollary of a more general result due to Kreitz and Weihrauch [Reference Kreitz and Weihrauch13, Theorem 3.4] (see also [Reference Weihrauch29, Theorem 3.3.20]), which characterizes precomplete representations following Ershov’s characterization of precomplete numberings.
Theorem 2.2 (Uniform recursion theorem)
There exists a total computable function
$T:{\Bbb {N}}^{\Bbb {N}}\to {\Bbb {N}}^{\Bbb {N}}$
such that
$\Phi _{T(p)}=\Phi _{\Phi _pT(p)}$
for all
$p\in {\Bbb {N}}^{\Bbb {N}}$
such that
$\Phi _p$
is total.
As a corollary of this theorem we obtain the following parameterized version of the recursion theorem that also comes in a version for computable and a version for continuous functions.
Corollary 2.3 (Parameterized recursion theorem)
For every computable (continuous) function
$F:\subseteq {\Bbb {N}}^{\Bbb {N}}\to {\Bbb {N}}^{\Bbb {N}}$
there exists a total computable (continuous) function
$R:{\Bbb {N}}^{\Bbb {N}}\to {\Bbb {N}}^{\Bbb {N}}$
such that
${\mathsf {{U}}} R(q)=F\langle q,R(q)\rangle $
for all
$q\in {\Bbb {N}}^{\Bbb {N}}$
.
Proof. We prove the version of the statement for continuous functions. For computable functions one just has to replace the word “continuous” by “computable” in all occurrences. Let
$F:\subseteq {\Bbb {N}}^{\Bbb {N}}\to {\Bbb {N}}^{\Bbb {N}}$
be continuous. Then by a double application of the smn-theorem (Theorem 2.1) there is a total continuous
$S:{\Bbb {N}}^{\Bbb {N}}\to {\Bbb {N}}^{\Bbb {N}}$
such that
$\Phi _{\Phi _{S(q)}(r)}(p)=F\langle p,\langle r,q\rangle \rangle $
for all
$p,q,r\in {\Bbb {N}}^{\Bbb {N}}$
. Let
$T:{\Bbb {N}}^{\Bbb {N}}\to {\Bbb {N}}^{\Bbb {N}}$
be the computable function from the recursion theorem (Theorem 2.2). Then
$R:{\Bbb {N}}^{\Bbb {N}}\to {\Bbb {N}}^{\Bbb {N}}$
with
$R(q):=\langle TS(q),q\rangle $
for all
$q\in {\Bbb {N}}^{\Bbb {N}}$
is continuous and satisfies
$$ \begin{align*} {\mathsf{{U}}} R(q)=\Phi_{TS(q)}(q)=\Phi_{\Phi_{S(q)}TS(q)}(q)=F\langle q,\langle TS(q),q\rangle\rangle=F\langle q,R(q)\rangle \end{align*} $$
for all
$q\in {\Bbb {N}}^{\Bbb {N}}$
. ⊣
In the next section we will use this parameterized version of the recursion theorem to prove our characterization of effectively discontinuous functions.
3 Effectively discontinuous problems
We now introduce a concept of computable (and effective) discontinuity. These are strengthenings of the concept of discontinuity in the sense that the discontinuity is witnessed by a continuous function
$D:{\Bbb {N}}^{\Bbb {N}}\to {\Bbb {N}}^{\Bbb {N}}$
. A computably discontinuous problem f is supposed to have no continuous realizer
$\Phi _q$
and the computable discontinuity function
$D:{\Bbb {N}}^{\Bbb {N}}\to {\Bbb {N}}^{\Bbb {N}}$
computes for every candidate
$\Phi _q$
a witnessing input
$D(q)$
that shows that the candidate
$\Phi _q$
fails to realize f on that particular input.
Definition 3.1 (Computable discontinuity)
Let
$(X,\delta _X)$
and
$(Y,\delta _Y)$
be represented spaces. A problem
$f:\subseteq X\rightrightarrows Y$
is called computably discontinuous (effectively discontinuous) if there is a computable (continuous)
$D:{\Bbb {N}}^{\Bbb {N}}\to {\Bbb {N}}^{\Bbb {N}}$
such that for all
$q\in {\Bbb {N}}^{\Bbb {N}}$
we obtain
$$ \begin{align*} D(q)\in{\mathrm{dom}}(f\delta_X)\mbox{ and }\delta_Y\Phi_qD(q)\not\in f\delta_XD(q).\end{align*} $$
In this case the function D is called a discontinuity function of f.
We emphasize that we consider the condition
$\delta _Y\Phi _qD(q)\not \in f\delta _XD(q)$
also as satisfied when the left-hand side is undefined. If one does not apply this convention, then one has to write out the condition somewhat more detailed as
$$ \begin{align*} D(q)\in{\mathrm{dom}}(f\delta_X)\mbox{ and }(D(q)\in{\mathrm{dom}}(\delta_Y\Phi_q)\Longrightarrow\delta_Y\Phi_qD(q)\not\in f\delta_XD(q)).\end{align*} $$
Clearly, every computably discontinuous problem f is effectively discontinuous, and every effectively discontinuous problem is discontinuous. The definition of computable (effective) discontinuity is such that a problem
$f:\subseteq X\rightrightarrows Y$
has the respective property if and only if its realizer version
$f^{\mathrm r}:\subseteq {\Bbb {N}}^{\Bbb {N}}\rightrightarrows {\Bbb {N}}^{\Bbb {N}}$
with
$f^{\mathrm r}:=\delta _Y^{-1}\circ f\circ \delta _X$
has the property. This implies that it suffices to study the concepts of computable and effective discontinuity on Baire space
${\Bbb {N}}^{\Bbb {N}}$
. We will prove that effective and computable discontinuity can be both characterized in terms of the following discontinuity problem.
Definition 3.2 (Discontinuity problem)
We define the discontinuity problem by
$\mathsf {DIS}:{\Bbb {N}}^{\Bbb {N}}\rightrightarrows {\Bbb {N}}^{\Bbb {N}},p\mapsto \{q\in {\Bbb {N}}^{\Bbb {N}}:{\mathsf {{U}}}(p)\not =q\}$
.
We note that
$\mathsf {DIS}$
is total, i.e., for instances
$p\not \in {\mathrm {dom}}({\mathsf {{U}}})$
the problem
$\mathsf {DIS}$
can provide arbitrary
$q\in {\Bbb {N}}^{\Bbb {N}}$
as solutions. It is a direct consequence of the parameterized recursion theorem from Corollary 2.3 that
$\mathsf {DIS}$
is computably discontinuous.
Proposition 3.3.
$\mathsf {DIS}$
is computably discontinuous.
Proof. By Corollary 2.3 there is a computable function
$D:{\Bbb {N}}^{\Bbb {N}}\to {\Bbb {N}}^{\Bbb {N}}$
such that
${\mathsf {{U}}} D(p)={\mathsf {{U}}}\langle p,D(p)\rangle =\Phi _pD(p)$
for all
$p\in {\Bbb {N}}^{\Bbb {N}}$
. This function D is hence a computable discontinuity function for
$\mathsf {DIS}$
.⊣
We generalize this observation with the following result that is illustrated in the diagram in Figure 1.
Theorem 3.4 (Effective discontinuity)
Let
$f:\subseteq X\rightrightarrows Y$
be a problem. Then:
-
(1)
$\mathsf {DIS}\mathop {\leq _{\mathrm {W}}} f\iff f$
is computably discontinuous, -
(2)
$\mathsf {DIS}\leq _{\mathrm {W}}^* f\iff f$
is effectively discontinuous.
In both cases one can replace
$\mathrm {W}$
by its strong counterpart
$\mathrm {sW}$
.
Proof. Since
$f\mathop {\equiv _{\mathrm {sW}}} f^{\mathrm r}$
and f is computably (effectively) discontinuous if and only if
$f^{\mathrm {r}}$
is, it suffices to prove both statements for problems of type
$f:\subseteq {\Bbb {N}}^{\Bbb {N}}\rightrightarrows {\Bbb {N}}^{\Bbb {N}}$
.
(1) “
$\Longrightarrow $
” Let
$\mathsf {DIS}\mathop {\leq _{\mathrm {W}}} f$
hold via computable
$H,K:\subseteq {\Bbb {N}}^{\Bbb {N}}\to {\Bbb {N}}^{\Bbb {N}}$
, i.e.,
$H\langle p,FK(p)\rangle \not ={\mathsf {{U}}}(p)$
and
$H\langle p,FK(p)\rangle $
defined for all
$p\in {\Bbb {N}}^{\Bbb {N}}$
and every realizer F of f. In particular, K is total and
$K(p)\in {\mathrm {dom}}(f)$
for every
$p\in {\Bbb {N}}^{\Bbb {N}}$
. By the parameterized recursion theorem from Corollary 2.3 there is some computable
$R:{\Bbb {N}}^{\Bbb {N}}\to {\Bbb {N}}^{\Bbb {N}}$
such that
$$ \begin{align*} H\langle R(q),{\mathsf{{U}}}\langle q,KR(q)\rangle\rangle={\mathsf{{U}}} R(q),\end{align*} $$
for all
$q\in {\Bbb {N}}^{\Bbb {N}}$
. Then
$KR$
is a total computable function and
$KR(q)\in {\mathrm {dom}}(f)$
for all
$q\in {\Bbb {N}}^{\Bbb {N}}$
. Let
$q\in {\Bbb {N}}^{\Bbb {N}}$
be such that
$KR(q)\in {\mathrm {dom}}(\Phi _q)$
and let us assume that
${\mathsf {{U}}}\langle q,KR(q)\rangle =\Phi _qKR(q)\in fKR(q)$
. Since f is realizable, there is a realizer F of f with
$FKR(q)={\mathsf {{U}}}\langle q,KR(q)\rangle $
and hence
$$ \begin{align*} H\langle R(q),{\mathsf{{U}}}\langle q,KR(q)\rangle\rangle=H\langle R(q),FKR(q)\rangle\not={\mathsf{{U}}} R(q)\end{align*} $$
follows by the choice of
$H,K$
in contradiction to the choice of R. Hence the assumption was wrong, i.e.,
$\Phi _qKR(q)\not \in fKR(q)$
and
$D:=KR$
is a total computable discontinuity function for f. “
$\Longleftarrow $
” Let f be computably discontinuous with a corresponding computable discontinuity function
$D:{\Bbb {N}}^{\Bbb {N}}\to {\Bbb {N}}^{\Bbb {N}}$
. By the smn-theorem (Theorem 2.1) there is a total computable
$R:{\Bbb {N}}^{\Bbb {N}}\to {\Bbb {N}}^{\Bbb {N}}$
such that
${\mathsf {{U}}}\langle R(p),q\rangle ={\mathsf {{U}}}(p)$
for all
$p,q\in {\Bbb {N}}^{\Bbb {N}}$
. Now for every realizer F of f and
$p\in {\Bbb {N}}^{\Bbb {N}}$
we obtain
$DR(p)\in {\mathrm {dom}}(f)$
and
$FDR(p)\in fDR(p)$
and hence
$$ \begin{align*} {\mathsf{{U}}}(p)={\mathsf{{U}}}\langle R(p),DR(p)\rangle=\Phi_{R(p)}DR(p)\not=FDR(p),\end{align*} $$
since D is a discontinuity function. Hence,
$DR$
is a computable function that witnesses
$\mathsf {DIS}\mathop {\leq _{\mathrm {sW}}} f$
.
(2) The proof is literally the same as above, except that
$H,K,R$
, and D are supposed to be continuous instead of computable.⊣
We note that the proof of “
$\Longleftarrow $
” shows that we could replace the strong versions of Weihrauch reducibility by an even stronger form of reducibility that only uses the inner reduction function K and no outer reduction function H.
Now we can ask the question whether every discontinuous problem is automatically computably discontinuous, i.e., whether the discontinuity problem
$\mathsf {DIS}$
is the smallest discontinuous problem with respect to the computable version of Weihrauch reducibility. This is clearly not the case, as the following example shows. In fact, we can infer this from the existence of immune sets. We recall that a set
$A\subseteq {\Bbb {N}}$
is called immune if it is infinite but does not contain any infinite c.e. subset.
Example 3.5. Let
$A\subseteq {\Bbb {N}}$
and let
$f_A:\subseteq [0,1]\to {\Bbb {R}}$
be defined by
${\mathrm {dom}}(f_A):=\{2^{-n}:n\in A\}\cup \{0\}$
and
$$ \begin{align*} f_A(x):=\left\{\begin{array}{ll} 1 & \mbox{if } x=0,\\ 0 & \mbox{otherwise.} \end{array}\right. \end{align*} $$
Then we obtain:
-
(1)
$f_A$
discontinuous
$\iff \ A$
infinite. -
(2)
$f_A$
computably discontinuous
$\iff \ A$
contains an infinite c.e. subset. -
(3)
$f_A$
discontinuous and not computably discontinuous
$\iff \ A$
is immune.
Proof. (1) is obvious and (3) follows from (1) and (2). For the proof of (2), we note that given a computable discontinuity function
$D:{\Bbb {N}}^{\Bbb {N}}\to {\Bbb {N}}^{\Bbb {N}}$
for
$f_A$
, we get an infinite c.e. subset of A as follows. Given
$n\in {\Bbb {N}}$
and
$A_n=\{0,1,2,\ldots ,n\}$
we can compute a name q of a realizer
$\Phi _q$
of the continuous function
$f_{A_n}$
, and
$D(q)$
has to provide a name of an input
$2^{-k}\in [0,1]$
to
$f_{A}$
on which the realizer
$\Phi _q$
fails. But this means that
$k\in A\setminus A_n$
. The collection of all those k for
$n=0,1,2,\ldots $
forms an infinite c.e. subset of A. On the other hand, given an infinite c.e. subset
$B\subseteq A$
and a potential realizer
$\Phi _q$
of
$f_A$
, we can evaluate
$\Phi _q$
successively on partial names of inputs that correspond to the compact interval
$[0,2^{-k}]$
with
$k=0,1,2,\ldots $
. Then either
$\Phi _q$
eventually produces an output that excludes
$0$
or that excludes
$1$
or neither of this ever happens. In the first case, we can find some
$m\in B$
with
$m>k$
and produce a name of
$2^{-m}$
as output of
$D(q)$
, since this is a value on which
$\Phi _q$
fails to realize
$f_A(2^{-m})=0$
. In the second case, we produce a name of
$0$
as output of
$D(q)$
, since this is then a value on which
$\Phi _q$
fails to realize
$f_A(0)=1$
. As long as neither the first nor the second case occurs, we produce the open interval
$(-2^{-k},2^{-k+1})$
as approximation of an output of
$D(q)$
. If the first and the second case never occurs, then this produces a name of
$0$
as output of
$D(q)$
, which is then not in the domain of
$\Phi _q$
. Altogether, D is a computable discontinuity function for
$f_A$
.⊣
The following result shows that with respect to the computable version of Weihrauch reducibility we can even get an infinite descending chain of discontinuous problems that are not computably discontinuous. If we restrict the discontinuity problem to the Turing cone
$[p]:=\{q\in {\Bbb {N}}^{\Bbb {N}}:p\mathop {\leq _{\mathrm {T}}} q\}$
, we obtain an effectively discontinuous problem
$\mathsf {DIS}|_{[p]}$
. With increasing complexity of p these problems get weaker. By
$p^{(n)}$
we denote the n-th Turing jump of
$p\in {\Bbb {N}}^{\Bbb {N}}$
.
Proposition 3.6.
$\mathsf {DIS}|_{[p^{(n+1)}]}\mathop {<_{\mathrm {W}}}\mathsf {DIS}|_{[p^{(n)}]}$
and
$\mathsf {DIS}|_{[p^{(n)}]}$
is effectively discontinuous for all
$p\in {\Bbb {N}}^{\Bbb {N}}$
and
$n\in {\Bbb {N}}$
, but not computably so for
$n\geq 1$
.
Proof. It is clear that
$\mathsf {DIS}|_{[p^{(n+1)}]}\mathop {\leq _{\mathrm {sW}}}\mathsf {DIS}|_{[p^{(n)}]}$
holds for all
$n\in {\Bbb {N}}$
, as the former problem is a restriction of the latter one. We have
$\mathsf {DIS}|_{[p^{(n)}]}\not \leq _{\mathrm {W}}\mathsf {DIS}|_{[p^{(n+1)}]}$
, as an instance
$q\mathop {\equiv _{\mathrm {T}}} p^{(n)}$
of
$\mathsf {DIS}|_{[p^{(n)}]}$
cannot be computably mapped to an instance of
$\mathsf {DIS}|_{[p^{(n+1)}]}$
. Hence,
$\mathsf {DIS}|_{[p^{(n)}]}$
is not computably discontinuous for all
$p\in {\Bbb {N}}^{\Bbb {N}}$
and
$n\geq 1$
by Theorem 3.4.
On the other hand, every function
$\Phi _q$
has names of Turing degree above any
$p\in {\Bbb {N}}^{\Bbb {N}}$
, and we can even continuously determine such names by adding redundant information in the code q that encodes p (for instance by repeating the n-th entry of q exactly
$p(n)$
times). In other words, for every
$p\in {\Bbb {N}}^{\Bbb {N}}$
there is a continuous function
$R_p:{\Bbb {N}}^{\Bbb {N}}\to {\Bbb {N}}^{\Bbb {N}}$
such that
$\Phi _q=\Phi _{R_p(q)}$
and
$p\mathop {\leq _{\mathrm {T}}} R_p(q)$
. Hence
$\mathsf {DIS}\leq _{\mathrm {W}}^*\mathsf {DIS}|_{[p]}$
holds for every
$p\in {\Bbb {N}}^{\Bbb {N}}$
. That is,
$\mathsf {DIS}|_{[p]}$
is effectively discontinuous by Theorem 3.4.⊣
Hence, we even have an infinite descending chain of effectively discontinuous problems below
$\mathsf {DIS}$
with respect to the computable version of Weihrauch reducibility. In particular, an effectively discontinuous problem does not need to be computably discontinuous. The next question is whether there are discontinuous problems, which are not even effectively discontinuous. The following proposition provides a sufficient condition for such an example.
Proposition 3.7. Let
$\iota :{\Bbb {N}}^{\Bbb {N}}\to {\Bbb {N}}^{\Bbb {N}}$
be injective and
$B:={\mathrm {range}}(\iota )$
. We consider the problem
$f:\subseteq {\Bbb {N}}^{\Bbb {N}}\rightrightarrows {\Bbb {N}}^{\Bbb {N}}$
with the domain
${\mathrm {dom}}(f):=B$
and
$$ \begin{align*} f(p):=\left\{\begin{array}{ll} {\Bbb{N}}^{\Bbb{N}}\setminus\{\Phi_{\iota^{-1}(p)}(p)\} & \mbox{if } p\in{\mathrm{dom}}(\Phi_{\iota^{-1}(p)}),\\ {\Bbb{N}}^{\Bbb{N}} & \mbox{otherwise,} \end{array}\right.\end{align*} $$
for all
$p\in B$
. Then f is discontinuous. Moreover, if f is effectively discontinuous, then there is a continuous embedding
$g:2^{\Bbb {N}}\hookrightarrow B$
.
Proof. A function
$D:{\Bbb {N}}^{\Bbb {N}}\to {\Bbb {N}}^{\Bbb {N}}$
is a discontinuity function for f if and only if
${\mathrm {range}}(D)\subseteq B$
and
$$ \begin{align*} D(q)\in{\mathrm{dom}}(\Phi_q)\Longrightarrow\Phi_qD(q)=\Phi_{\iota^{-1}D(q)}D(q)\end{align*} $$
holds for all
$q\in {\Bbb {N}}^{\Bbb {N}}$
. Clearly,
$D=\iota $
is a discontinuity function for f, albeit not necessarily a continuous one. Nevertheless, this shows that f is discontinuous.
Let us now assume that
$D:{\Bbb {N}}^{\Bbb {N}}\to {\Bbb {N}}^{\Bbb {N}}$
is a continuous function with the above property. By the smn-theorem (Theorem 2.1) there exists a computable total function
$R:{\Bbb {N}}^{\Bbb {N}}\to {\Bbb {N}}^{\Bbb {N}}$
such that
$\Phi _{R(q)}(p)=q$
for all
$p,q\in {\Bbb {N}}^{\Bbb {N}}$
. Then we obtain
$$ \begin{align*} q=\Phi_{R(q)}DR(q)=\Phi_{\iota^{-1}DR(q)}DR(q),\end{align*} $$
for all
$q\in {\Bbb {N}}^{\Bbb {N}}$
, which is only possible if
$DR:{\Bbb {N}}^{\Bbb {N}}\to {\Bbb {N}}^{\Bbb {N}}$
is injective. In particular,
$DR|_{2^{\Bbb {N}}}:2^{\Bbb {N}}\to B$
is a continuous embedding of Cantor space into B.⊣
Hence, the existence of an injective map
$\iota :{\Bbb {N}}^{\Bbb {N}}\to {\Bbb {N}}^{\Bbb {N}}$
with a range
$B={\mathrm {range}}(\iota )$
into which Cantor space cannot be continuously embedded is sufficient to guarantee the existence of a problem f that is discontinuous, but not effectively discontinuous.
For this purpose it is sufficient to show that there exists a set
$B\subseteq {\Bbb {N}}^{\Bbb {N}}$
of continuum cardinality, which violates the perfect subset property. A set B satisfies the perfect subset property if it is either countable or it contains a non-empty perfect subset, which is a subset that is closed and has no isolated points. We recall that every
$A\subseteq {\Bbb {N}}^{\Bbb {N}}$
into which Cantor space can be continuously embedded contains a perfect subset. It is a well-known fact that there are so-called Bernstein sets [Reference Bernstein3], which violate the perfect subset property, at least if we assume the axiom of choice [Reference Kechris12, Exercise 8.24].
Fact 3.8 (Bernstein set)
Assuming
$\mathsf {AC}$
there exists a Bernstein set
$B\subseteq {\Bbb {N}}^{\Bbb {N}}$
, which is a set B such that B as well as its complement
${\Bbb {N}}^{\Bbb {N}}\setminus B$
has non-empty intersection with every uncountable closed set
$A\subseteq {\Bbb {N}}^{\Bbb {N}}$
.
The construction of a Bernstein set
$B\subseteq {\Bbb {R}}$
provided in [Reference Kechris12, Exercise 8.24] works equally well for
$B\subseteq {\Bbb {N}}^{\Bbb {N}}$
and is by transfinite recursion. This construction necessarily requires the axiom of choice. Indeed, if we assume
$\mathsf {BP}$
, i.e., that every subset
$B\subseteq {\Bbb {N}}^{\Bbb {N}}$
has the Baire property, then no Bernstein set can exist [Reference Kechris12] (see also Question 4.19). From the point of view of computability theory Bernstein sets play a similar rôle as immune sets. Actually, together with Proposition 3.7 and Fact 3.8 we directly obtain the following conclusion.
Corollary 3.9. If we assume
$\mathsf {AC}$
, then there exists a problem
$f:\subseteq {\Bbb {N}}^{\Bbb {N}}\rightrightarrows {\Bbb {N}}^{\Bbb {N}}$
that is discontinuous, but not effectively discontinuous.
Similarly as in the case of Proposition 3.6, one could object that the problem f constructed here is not genuinely less discontinuous than
$\mathsf {DIS}$
, but only “simpler” as instances are artificially made harder. In other words, the problem f considered here has a very complicated domain, which in the case of our proof of Corollary 3.9 is a Bernstein set.
With the next result we dispel this objection by constructing a total problem
$f:{\Bbb {N}}^{\Bbb {N}}\rightrightarrows {\Bbb {N}}^{\Bbb {N}}$
that is discontinuous, but not effectively so. Again, the construction is based on the axiom of choice, and we directly perform a transfinite recursion. We can arrange this construction even such that f is parallelizable. We recall that
$f:\subseteq {\Bbb {N}}^{\Bbb {N}}\rightrightarrows {\Bbb {N}}^{\Bbb {N}}$
is parallelizable if and only if
$f\mathop {\equiv _{\mathrm {W}}}\langle f\rangle $
, where
$\langle f\rangle $
is defined by
$\langle f\rangle :\subseteq {\Bbb {N}}^{\Bbb {N}}\rightrightarrows {\Bbb {N}}^{\Bbb {N}},\langle p_0,p_1,\ldots \rangle \mapsto \langle f(p_0),f(p_1),\ldots \rangle $
. By
$|X|$
we denote the cardinality of a set X.
Theorem 3.10. Assuming
$\mathsf {AC}$
, there exists a total parallelizable
$f:{\Bbb {N}}^{\Bbb {N}}\rightrightarrows {\Bbb {N}}^{\Bbb {N}}$
that is discontinuous, but not effectively discontinuous.
Proof. It suffices to construct a total
$f:{\Bbb {N}}^{\Bbb {N}}\rightrightarrows {\Bbb {N}}^{\Bbb {N}}$
that is discontinuous and such that
$\langle f\rangle :{\Bbb {N}}^{\Bbb {N}}\rightrightarrows {\Bbb {N}}^{\Bbb {N}},\langle p_0,p_1,\ldots \rangle \mapsto \langle f(p_0),f(p_1),\ldots \rangle $
is not effectively discontinuous. Then
$\langle f\rangle $
has the desired properties, since it is discontinuous and parallelizable. We note that the set
$\mathsf {C}({\Bbb {N}}^{\Bbb {N}},{\Bbb {N}}^{\Bbb {N}})$
of total continuous functions
$g:{\Bbb {N}}^{\Bbb {N}}\to {\Bbb {N}}^{\Bbb {N}}$
has continuum cardinality. Hence, by the axiom of choice there is a transfinite enumeration
$(r_\xi )_{\xi <2^{\aleph _0}}$
of
$r_\xi \in {\Bbb {N}}^{\Bbb {N}}$
such that
$\mathsf {C}({\Bbb {N}}^{\Bbb {N}},{\Bbb {N}}^{\Bbb {N}})=\{\Phi _{r_\xi }:\xi <2^{\aleph _0}\}$
. A problem
$f:{\Bbb {N}}^{\Bbb {N}}\rightrightarrows {\Bbb {N}}^{\Bbb {N}}$
is discontinuous and
$\langle f\rangle $
is not effectively discontinuous if the following two requirements are satisfied:
-
(1)
$(\forall \xi <2^{\aleph _0})(\exists q\in {\Bbb {N}}^{\Bbb {N}}) (\Phi _q\Phi _{r_\xi }(q)\in \langle f\rangle (\Phi _{r_\xi }(q))\mbox { and }\Phi _q\mbox { total} )$
, -
(2)
$(\forall \xi <2^{\aleph _0})(\exists p\in {\Bbb {N}}^{\Bbb {N}})\;\Phi _{r_\xi }(p)\not \in f(p)$
.
The second condition guarantees that f has no continuous realizer
$\Phi _{r_\xi }$
, and the first condition guarantees that no
$\Phi _{r_\xi }$
is a discontinuity function for
$\langle f\rangle $
. We build f by transfinite recursion. For this purpose we construct two increasing sequences
$(N_\xi )_{\xi <2^{\aleph _0}}$
and
$(P_\xi )_{\xi <2^{\aleph _0}}$
of sets
$N_\xi ,P_\xi \subseteq {\Bbb {N}}^{\Bbb {N}}\times {\Bbb {N}}^{\Bbb {N}}$
. The “negative list”
$N_\xi $
ensures that f is discontinuous and the “positive list”
$P_\xi $
ensures that
$\langle f\rangle $
is not effectively discontinuous. The construction will be such that
$|N_\xi |=|\xi |$
and
$|P_\xi |\leq |\xi |\cdot \aleph _0$
. During the construction we frequently use the axiom of choice without further mention. The transfinite recursion goes as follows. We start with
$N_0:=P_0:=\emptyset $
. For each
$0<\xi <2^{\aleph _0}$
we first choose some
$p\in {\Bbb {N}}^{\Bbb {N}}$
that does not appear as a first component in
$M:=\bigcup _{\lambda <\xi }(P_\lambda \cup N_\lambda )$
and we define
$N_\xi :=\{(p,\Phi _{r_\xi }(p))\}\cup \bigcup _{\lambda <\xi }N_\lambda $
. Such a choice is possible, as
$|M|\leq |\xi |+|\xi |\cdot \aleph _0=\max (|\xi |,\aleph _0)<2^{\aleph _0}$
using the usual rules of cardinal arithmetic [Reference Devlin11, Corollary 3.7.8]. Secondly, we also choose some
$q\in {\Bbb {N}}^{\Bbb {N}}$
such that
$\Phi _q$
is total and such that no
$\pi _i\Phi _q\Phi _{r_\xi }(q)$
with
$i\in {\Bbb {N}}$
appears in any second component of
$N_\xi $
. Here
$\pi _i:{\Bbb {N}}^{\Bbb {N}}\to {\Bbb {N}}^{\Bbb {N}},\langle p_0,p_1,\ldots \rangle \mapsto p_i$
denotes the projection on the i-th component. Such a choice is possible, as
$|N_\xi |\leq |\xi |<2^{\aleph _0}$
and
$\Phi _q$
for
$q\in {\Bbb {N}}^{\Bbb {N}}$
includes all the constant total functions. We define
$P_\xi :=\{(\pi _i\Phi _{r_\xi }(q),\pi _i\Phi _q\Phi _{r_\xi }(q)):i\in {\Bbb {N}}\}\cup \bigcup _{\lambda <\xi }P_\lambda $
. The construction guarantees that
$|N_\xi |=|\xi |$
and
$|P_\xi |\leq |\xi |\cdot \aleph _0$
. This ends the transfinite recursion. We now define
$P:=\bigcup _{\xi <2^{\aleph _0}}P_\xi $
and
$N:=\bigcup _{\xi <2^{\aleph _0}}N_\xi $
. The construction guarantees that P is the graph of a partial problem
$f:\subseteq {\Bbb {N}}^{\Bbb {N}}\rightrightarrows {\Bbb {N}}^{\Bbb {N}}$
and N is the graph of a single-valued function
$g:\subseteq {\Bbb {N}}^{\Bbb {N}}\to {\Bbb {N}}^{\Bbb {N}}$
with
$N\cap P=\emptyset $
. Actually, P guarantees that f satisfies condition (1) and N guarantees that f satisfies condition (2). We still need to extend P to the graph of a total problem
$f:{\Bbb {N}}^{\Bbb {N}}\rightrightarrows {\Bbb {N}}^{\Bbb {N}}$
without affecting the conditions (1) and (2). For this purpose, we choose for every
$p\in {\Bbb {N}}^{\Bbb {N}}$
that does not yet appear in a first component of P, some
$s\in {\Bbb {N}}^{\Bbb {N}}$
such that
$(p,s)\not \in N$
and we add
$(p,s)$
to P. This is possible since N is the graph of a single-valued function g. Now P is the graph of a suitable total problem
$f:{\Bbb {N}}^{\Bbb {N}}\rightrightarrows {\Bbb {N}}^{\Bbb {N}}$
.⊣
In Corollary 4.11 we will see that without the axiom of choice (
$\mathsf {AC}$
) we cannot construct discontinuous problems that are not effectively discontinuous. We close with mentioning that the example in Theorem 3.10 cannot be strengthened to a single-valued function.
Proposition 3.11 (Discontinuous functions)
Every single-valued
${f:\subseteq {\Bbb {N}}^{\Bbb {N}}\to {\Bbb {N}}^{\Bbb {N}}}$
is either continuous or effectively discontinuous.
Proof. By
$\mathsf {LPO}:{\Bbb {N}}^{\Bbb {N}}\to \{0,1\}$
we denote the characteristic function of
$\{000\ldots \}$
. It is well-known that every discontinuous
$f:\subseteq {\Bbb {N}}^{\Bbb {N}}\to {\Bbb {N}}^{\Bbb {N}}$
satisfies
$\mathsf {LPO}\leq _{\mathrm {W}}^*f$
[Reference Weihrauch30, Lemma 8.2.6]. It is easy to see that
$\mathsf {DIS}\mathop {\leq _{\mathrm {sW}}}\mathsf {LPO}$
holds (given an input
$p\in {\Bbb {N}}^{\Bbb {N}}$
for the universal function
${\mathsf {{U}}}$
, use
$\mathsf {LPO}$
to determine whether
${\mathsf {{U}}}(p)=000\ldots $
or not). The statement now follows with Theorem 3.4.⊣
This result can be extended to functions
$f:X\to Y$
on admissibly represented spaces
$X,Y$
(which can be proved similarly as [Reference Pauly22, Theorem 4.13]).
4 A game characterization
In this section we want to characterize continuity and effective discontinuity using games. It is common in descriptive set theory and computability theory to use games to characterize reducibilities and other properties [Reference Kechris12, Reference Moschovakis14, Reference Soare25] (see [Reference Mycielski16, Reference Telgársky26] for historical surveys).
Wadge [Reference Wadge27] introduced games on subsets
$A,B\subseteq {\Bbb {N}}^{\Bbb {N}}$
to characterize the reducibility that is named after him. Nobrega and Pauly [Reference Nobrega20, Reference Nobrega and Pauly21] have used a modification of Wadge games for problems
$f:\subseteq X\rightrightarrows Y$
in order to characterize lower cones in the Weihrauch lattice. We consider similar generalizedFootnote
5
versions of Wadge and Lipschitz games, defined as follows. We recall that by
$f^{{\mathrm {r}}}:\subseteq {\Bbb {N}}^{{\Bbb {N}}}\rightrightarrows {\Bbb {N}}^{{\Bbb {N}}}$
we denote the realizer version of a problem
$f:\subseteq X\rightrightarrows Y$
(see Section 3).
Definition 4.1 (Wadge game of problems)
Let
$f:\subseteq {\Bbb {N}}^{\Bbb {N}}\rightrightarrows {\Bbb {N}}^{\Bbb {N}}$
be a problem. In a Wadge game f two players I and II consecutively play words, with Player I starting:
-
• Player I:
$x_0\quad x_1\quad x_2 \quad \ldots \quad =:x$
, -
• Player II:
$\quad y_0\quad y_1\quad y_2 \quad \ldots \quad =:y$
,
with
$x_i,y_i\in {\Bbb {N}}^*$
. The concatenated sequences
$(x,y)\in ({\Bbb {N}}^{\Bbb {N}}\cup {\Bbb {N}}^*)^2$
are called a run of the game f. We say that Player II wins the run
$(x,y)$
of f, if
$(x,y)\in {\mathrm {graph}}(f)$
or
$x\not \in {\mathrm {dom}}(f)$
. Otherwise Player I wins. A Wadge game is called a Lipschitz game if
$x_i,y_i\in {\Bbb {N}}$
. A Wadge or Lipschitz game of a general problem
$f:\subseteq X\rightrightarrows Y$
is understood to be the corresponding game of the realizer version
$f^{{\mathrm {r}}}:\subseteq {\Bbb {N}}^{\Bbb {N}}\rightrightarrows {\Bbb {N}}^{\Bbb {N}}$
.
We allow both players to play arbitrary words, including the empty word. One can see that Player I does not take any advantage of playing words and he could be restricted to natural numbers in a Wadge game, without loss of generality. Likewise, Player II does not take any advantage of playing arbitrary words, it would suffice to allow numbers and the empty word, where the empty word essentially corresponds to skipping the corresponding move. This shows that our notion of a Wadge game for problems corresponds to the one of Nobrega and Pauly [Reference Nobrega20, Reference Nobrega and Pauly21]. For simplicity we have allowed arbitrary words for both players. This does not only lead to a more symmetric definition, but it also simplifies the proof of Theorem 4.3 below. As usual we define winning strategies for games to be word functions that determine moves for one player depending on the moves of the other player.
Definition 4.2 (Winning strategy)
Let
$f:\subseteq X\rightrightarrows Y$
be a problem and let
${\sigma :{\Bbb {N}}^{**}\to {\Bbb {N}}^*}$
be a function. We consider the Wadge game f.
-
(1)
$\sigma $
is called a winning strategy for Player II in the game f, if Player II wins every run of f with her moves being determined by while Player I plays
$$ \begin{align*} y_i:=\sigma(x_0,\ldots ,x_i),\end{align*} $$
$x_0,x_1,\ldots \in {\Bbb {N}}^*$
.
-
(2)
$\sigma $
is called a winning strategy for Player I in the game f, if Player I wins every run of f with his moves being determined by while Player II plays
$$ \begin{align*} x_i:=\sigma(y_0,\ldots ,y_{i-1}),\end{align*} $$
$y_0,y_1,\ldots \in {\Bbb {N}}^*$
.
Winning strategies for Lipschitz games are defined analogously with functions of type
$\sigma :{\Bbb {N}}^*\to {\Bbb {N}}$
.
Now our main observation on Wadge games is that winning of Player II characterizes continuity of the problem and winning of Player I effective discontinuity. Nobrega and Pauly have proved a general version of the first observation for lower cones in the Weihrauch lattice [Reference Nobrega and Pauly21, Theorem 3.3]. We use some bijective standard numbering
$\mathsf {w}:{\Bbb {N}}\to {\Bbb {N}}^*$
and we use the notation
$\overline {v}:=\mathsf {w}^{-1}(v)$
for all
$v\in {\Bbb {N}}^*$
.
Theorem 4.3 (Wadge games)
We consider the Wadge game of a given problem
${f:\subseteq X\rightrightarrows Y}$
. Then the following hold:
-
(1) f is continuous
$\iff $
Player II has a winning strategy for f, -
(2) f is effectively discontinuous
$\iff $
Player I has a winning strategy for f.
Proof. Since the Wadge game of f is the Wadge game of
$f^{{\mathrm {r}}}$
and
$f^{{\mathrm {r}}}\mathop {\equiv _{\mathrm {sW}}} f$
, it suffices by Theorem 1.4 to consider problems of type
$f:\subseteq {\Bbb {N}}^{\Bbb {N}}\rightrightarrows {\Bbb {N}}^{\Bbb {N}}$
.
(1) If f is continuous, then f has a continuous realizer
$F:\subseteq {\Bbb {N}}^{\Bbb {N}}\to {\Bbb {N}}^{\Bbb {N}}$
, which is approximated by a monotone function
$h:{\Bbb {N}}^*\to {\Bbb {N}}^*$
in the sense that
$F(p)=\sup _{w\sqsubseteq p}h(w)$
for all
$p\in {\mathrm {dom}}(F)\supseteq {\mathrm {dom}}(f)$
. Given the moves
$w_0,w_1,\ldots \in {\Bbb {N}}^*$
of Player I, we can inductively define the moves
$v_i\in {\Bbb {N}}^*$
by
$v_0\ldots v_i:=h(w_0\ldots w_i)$
for all
$i\in {\Bbb {N}}$
, since h is monotone. Then
$\sigma (\varepsilon ):=\varepsilon $
and
$\sigma (w_0,\ldots ,w_i):=v_i$
provides a winning strategy
$\sigma :{\Bbb {N}}^{**}\to {\Bbb {N}}^*$
for Player II. This is because if
$r:=w_0w_1\ldots \in {\mathrm {dom}}(f)$
, then
$F(r)=v_0v_1\ldots \in f(r)$
.
Vice versa, let
$\sigma :{\Bbb {N}}^{**}\to {\Bbb {N}}^*$
be a winning strategy for Player II. Then we can define
$h:{\Bbb {N}}^*\to {\Bbb {N}}^*$
by
$h(\varepsilon ):=\varepsilon $
and
$h(a_0\ldots a_i):=v_0\ldots v_i$
for all
$a_0,a_1,\ldots \in {\Bbb {N}}$
, where we inductively choose
$v_i:=\sigma (a_0,\ldots ,a_i)$
. Let
$F:\subseteq {\Bbb {N}}^{\Bbb {N}}\to {\Bbb {N}}^{\Bbb {N}}$
be given by
$F(p):=\sup _{w\sqsubseteq p}h(w)$
. Given an input
$r:=a_0a_1\ldots \in {\mathrm {dom}}(f)$
, we obtain
$F(r)=v_0v_1\ldots $
such that
$(r,F(r))\in {\mathrm {graph}}(f)$
, since
$\sigma $
is a winning strategy for Player II. Hence F is a continuous realizer for f.
(2) If f is effectively discontinuous, then there is a continuous
$D:{\Bbb {N}}^{\Bbb {N}}\to {\Bbb {N}}^{\Bbb {N}}$
that witnesses the discontinuity of f in the sense that
$D(p)\in {\mathrm {dom}}(f)$
and
$\Phi _pD(p)\not \in fD(p)$
for all
$p\in {\Bbb {N}}^{\Bbb {N}}$
. Let
$h:{\Bbb {N}}^*\to {\Bbb {N}}^*$
be a monotone function that approximates D, in the sense that
$D(p)=\sup _{w\sqsubseteq p}h(w)$
for all
$p\in {\Bbb {N}}^{\Bbb {N}}$
. Given the moves
$v_0,v_1,\ldots \in {\Bbb {N}}^*$
of Player II, we can inductively define the moves
$w_i$
by
$w_0:=h(\varepsilon )$
and
$w_0\ldots w_i:=h(\langle \overline {w_0},\overline {v_0}\rangle \ldots \langle \overline {w_0\ldots w_{i-1}},\overline {v_0\ldots v_{i-1}}\rangle )$
. We note that
$r:=w_0w_1\ldots $
is an infinite sequence
$r\in {\mathrm {dom}}(f)$
, since D is total and
${\mathrm {range}}(D)\subseteq {\mathrm {dom}}(f)$
. And
$p:=\langle \overline {w_0},\overline {v_0}\rangle \langle \overline {w_0w_{1}},\overline {v_0v_{1}}\rangle \ldots \in {\Bbb {N}}^{\Bbb {N}}$
is the name of a function
$\Phi _p$
with
$D(p)=r$
. If
$q:=v_0v_1\ldots $
is finite, then clearly
$(r,q)\not \in {\mathrm {graph}}(f)$
. Otherwise,
$q=\Phi _p(r)=\Phi _pD(p)\not \in fD(p)=f(r)$
and hence also
$(r,q)\not \in {\mathrm {graph}}(f)$
. This means that
$\sigma :{\Bbb {N}}^{**}\to {\Bbb {N}}^*$
with
$\sigma (v_0,\ldots ,v_{i-1}):=w_i$
is a winning strategy for Player I.
Vice versa let
$\sigma :{\Bbb {N}}^{**}\to {\Bbb {N}}^*$
be a winning strategy for Player I. We need to define a continuous discontinuity function
$D:{\Bbb {N}}^{\Bbb {N}}\to {\Bbb {N}}^{\Bbb {N}}$
for f. Given
$p\in {\Bbb {N}}^{\Bbb {N}}$
, we can determine a monotone
$h:{\Bbb {N}}^*\to {\Bbb {N}}^*$
that approximates
$\Phi _p$
, i.e., such that
$\Phi _p(q)=\sup _{w\sqsubseteq q}h(w)$
for all
$q\in {\mathrm {dom}}(\Phi _p)$
. We let
$D(p):=w_0w_1\ldots $
where the
$w_i$
are inductively given by
$w_i:=\sigma (v_0,\ldots ,v_{i-1})$
and
$v_0\ldots v_i:=h(w_0\ldots w_i)$
. Since
$\sigma $
is a winning strategy for Player I, we have
$D(p)\in {\mathrm {dom}}(f)$
. In particular, D is total and continuous. Moreover, with
$q:=v_0v_1\ldots $
we have
$(D(p),q)\not \in {\mathrm {graph}}(f)$
. This could mean that q is finite and hence
$D(p)\not \in {\mathrm {dom}}(\Phi _p)$
or otherwise
$\Phi _pD(p)=q$
. In any case,
$\Phi _pD(p)\not \in fD(p)$
holds and D is a discontinuity function for f.⊣
In passing, we note that the proof is fully constructive in the sense that computable winning strategies translate into computable functions and vice versa, as stated in the following.
Corollary 4.4 (Wadge games)
We consider the Wadge game of a given problem
${f:\subseteq X\rightrightarrows Y}$
. Then the following hold:
-
(1) f is computable
$\iff $
Player II has a computable winning strategy for f, -
(2) f is computably discontinuous
$\iff $
Player I has a computable winning strategy for f.
One reason why it is useful to have characterizations of continuity and effective discontinuity in game form is that for certain games determinacy conditions are known and well understood. The axiom of determinacy (
$\mathsf {AD}$
), which was introduced by Mycielski and Steinhaus [Reference Mycielski15, Reference Mycielski and Steinhaus17] states that every Gale–Stewart game is determined. We note that this axiom is inconsistent with the axiom of choice. We recall the definition of Gale–Stewart games [Reference Soare25].Footnote
6
Definition 4.5 (Gale–Stewart game)
Let
$A\subseteq {\Bbb {N}}^{\Bbb {N}}$
. Then in a Gale–Stewart game A two players I and II consecutively play numbers
-
• Player I:
$x_0\quad x_1\quad x_2 \quad \ldots \quad =:x$
, -
• Player II:
$\quad y_0\quad y_1\quad y_2 \quad \ldots \quad =:y$
,
with
$x_i,y_i\in {\Bbb {N}}$
. The concatenated sequence
$r=\langle x,y\rangle \in {\Bbb {N}}^{\Bbb {N}}$
is called a run of the game A. We say that Player II wins the run r of A, if
$r\in A$
. Otherwise Player I wins.
What we have described as the Gale–Stewart game of A is usually considered as the Gale–Stewart game of the complement
${\Bbb {N}}^{\Bbb {N}}\setminus A$
. We prefer the complementary version as it fits better to our definition of Wadge games.
Winning strategies for Gale–Stewart games can be defined analogously to Lipschitz games. In fact, Lipschitz games of problems f are essentially Gale–Stewart games on
${\mathrm {graph}}(f)$
, at least for total problems on Baire space. For general problems, the difference can be expressed using totalizations of problems, a concept that was studied in [Reference Brattka and Gherardi8, Reference Neumann and Pauly19].
Definition 4.6 (Totalization)
Let
$f:\subseteq X\rightrightarrows Y$
be a problem. Then the totalization
${\mathsf {{T}}} f:X\rightrightarrows Y$
is defined by
$$ \begin{align*} {\mathsf{{T}}} f(x):=\left\{\begin{array}{ll} f(x) & \mbox{if } x\in{\mathrm{dom}}(f),\\ Y & \mbox{otherwise}. \end{array}\right.\end{align*} $$
For a subset
$A\subseteq {\Bbb {N}}^{\Bbb {N}}\times {\Bbb {N}}^{\Bbb {N}}$
we use the notation
$\langle A\rangle :=\{\langle p,q\rangle :(p,q)\in A\}$
. Now we can express the relation between Lipschitz games and Gale–Stewart games on graphs as follows.
Proposition 4.7 (Lipschitz games and Gale–Stewart games)
Let
$f:\subseteq {\Bbb {N}}^{\Bbb {N}}\rightrightarrows {\Bbb {N}}^{\Bbb {N}}$
be a problem. Then the winning strategies for either player in the Lipschitz game f are identical to the winning strategies of the corresponding player for the Gale–Stewart game
$\langle {\mathrm {graph}}({\mathsf {{T}}} f)\rangle $
.
Proof. The proof follows from the easy observation that
$$ \begin{align*} {\mathrm{graph}}({\mathsf{{T}}} f)={\mathrm{graph}}(f)\cup\left(({\Bbb{N}}^{\Bbb{N}}\setminus{\mathrm{dom}}(f))\times{\Bbb{N}}^{\Bbb{N}}\right),\end{align*} $$
and this is exactly the payoff set for Player II in the Lipschitz game f.⊣
We note that
$f\mathop {\leq _{\mathrm {W}}}{\mathsf {{T}}} f$
, but in general
${\mathsf {{T}}} f$
is not Weihrauch equivalent to f [Reference Brattka and Gherardi8].
For general Wadge games the situation is somewhat more subtle as players can play empty words. We can, however, bridge the step between Wadge and Lipschitz games by coding words in numbers. We consider a canonical bijective standard numbering
$\mathsf {w}:{\Bbb {N}}\to {\Bbb {N}}^*,i\mapsto \mathsf {w}_i$
of words over natural numbers, which we lift to a partial function
$$ \begin{align*} \mathsf{w}:\subseteq{\Bbb{N}}^{\Bbb{N}}\to{\Bbb{N}}^{\Bbb{N}},p\mapsto\mathsf{w}_{p(0)}\mathsf{w}_{p(1)}\mathsf{w}_{p(2)}\ldots \end{align*} $$
that we also denote by
$\mathsf {w}$
. Here
${\mathrm {dom}}(\mathsf {w})=\{p\in {\Bbb {N}}^{\Bbb {N}}:\mathsf {w}_{p(0)}\mathsf {w}_{p(1)}\mathsf {w}_{p(2)}\ldots $
is infinite
$\}$
and hence
$\mathsf {w}$
is not total (since there is a number n that encodes the empty word). Now we can consider the problem
$f^{\mathsf {w}}:=\mathsf {w}^{-1}\circ f\circ \mathsf {w}$
, which is f lifted to numbers (that encode words). We note that
$f^{\mathsf {w}}$
is not total, even if f is total, since
$\mathsf {w}$
is not total. We mention that
$\mathsf {w}:\subseteq {\Bbb {N}}^{\Bbb {N}}\to {\Bbb {N}}^{\Bbb {N}}$
can be seen as a precomplete representation of
${\Bbb {N}}^{\Bbb {N}}$
(in fact, as an alternative way to define the precompletion of
${\mathrm {id}}:{\Bbb {N}}^{\Bbb {N}}\to {\Bbb {N}}^{\Bbb {N}}$
, as studied in [Reference Brattka and Gherardi7, Reference Brattka and Gherardi8]). Since
$\mathsf {w}$
is computably equivalent to
${\mathrm {id}}$
as a representation, we obtain
$f\mathop {\equiv _{\mathrm {sW}}} f^{\mathsf {w}}$
. Now we can express our observation as follows.
Proposition 4.8 (Wadge games and Lipschitz games)
Let
$f:\subseteq {\Bbb {N}}^{\Bbb {N}}\rightrightarrows {\Bbb {N}}^{\Bbb {N}}$
be a problem and let
$P\in \{\mathrm {I, II}\}$
. Then the following are equivalent.
-
(1) Player P has a winning strategy for the Wadge game f.
-
(2) Player P has a winning strategy for the Lipschitz game
$f^{\mathsf {w}}$
.
Proof. Given a winning strategy
$\sigma :{\Bbb {N}}^{**}\to {\Bbb {N}}^*$
for Player P of the Wadge game f, we have to convert this strategy into a strategy
$\lambda :{\Bbb {N}}^*\to {\Bbb {N}}$
for Player P of the Lipschitz game
$f^{\mathsf {w}}$
. For this purpose we just have to define
$\lambda $
such that
$\lambda (n_0,\ldots ,n_k):=\mathsf {w}^{-1}\sigma (\mathsf {w}_{n_0},\ldots ,\mathsf {w}_{n_k})$
. Vice versa, if
$\lambda :{\Bbb {N}}^*\to {\Bbb {N}}$
is a winning strategy for Player P of the Lipschitz game
$f^{\mathsf {w}}$
, then
$\sigma (w_0,\ldots ,w_k):=\mathsf {w}_{\lambda (\mathsf {w}^{-1}(w_0),\ldots ,\mathsf {w}^{-1}(w_k))}$
defines a winning strategy
$\sigma :{\Bbb {N}}^{**}\to {\Bbb {N}}^*$
for Player P of the Wadge game f.⊣
If we combine Propositions 4.7 and 4.8 then we obtain the following result.
Corollary 4.9 (Wadge games and Gale–Stewart games)
Let
$f:\subseteq X\rightrightarrows Y$
be a problem and let
$P\in \{\mathrm {I, II}\}$
. Then the following are equivalent.
-
(1) Player P has a winning strategy for the Wadge game f.
-
(2) Player P has a winning strategy for the Lipschitz game
$f^{\mathrm {rw}}$
. -
(3) Player P has a winning strategy for the Gale–Stewart game
$\langle {\mathrm {graph}}({\mathsf {{T}}}(f^{\mathrm {rw}}))\rangle $
.
We note that
${\mathsf {{T}}}(f^{\mathrm {rw}})\mathop {\equiv _{\mathrm {sW}}}\overline {f}$
, where
$\overline {f}$
denotes the so-called completion of f (see [Reference Brattka and Gherardi8, Lemma 4.9]). Hence, the operation of precompletion moves us from Wadge games to Lipschitz games and the operation of completion to Gale–Stewart games.
In order to have some simple terminology at hand, we introduce the following notions of determinacy.
Definition 4.10 (Determinacy)
We call a problem
$f:\subseteq X\rightrightarrows Y$
determined, if it is either continuous or effectively discontinuous. By Weihrauch determinacy we understand the property that every problem f is determined.
Hence, by Theorem 3.4 f is determined if either
$f\leq _{\mathrm {W}}^*{\mathrm {id}}$
or
$\mathsf {DIS}\leq _{\mathrm {W}}^* f$
holds and by Theorem 4.3 this is the case if and only if the Wadge game f is determined in the sense that either Player I or Player II has a winning strategy. Weihrauch determinacy means that every f satisfies the above dichotomies.
Since the axiom of determinacy
$\mathsf {AD}$
states that every Gale–Stewart game is determined, i.e., either Player I or Player II has a winning strategy, we immediately get the following conclusion of Corollary 4.9 with the help of Theorem 3.4 (see also [Reference Nobrega and Pauly21, Corollary 3.7].
Corollary 4.11 (Determinacy)
$\mathsf {ZF}+\mathsf {DC}+\mathsf {AD}$
implies Weihrauch determinacy.
We can conclude more from Corollary 4.9. Namely, in
$\mathsf {ZF}+\mathsf {AC}$
it is known by a Theorem of Martin [Reference Kechris12, Theorem 20.5] that every Borel set
$A\subseteq {\Bbb {N}}^{\Bbb {N}}$
is determined, i.e., either Player I or Player II has a winning strategy (see also [Reference Nobrega and Pauly21, Corollary 3.6]).
Proposition 4.12 (Borel determinacy)
In
$\mathsf {ZFC}$
every problem
$f:\subseteq X\rightrightarrows Y$
, such that
${\mathrm {graph}}(f^{{\mathrm {r}}})\subseteq {\Bbb {N}}^{\Bbb {N}}\times {\Bbb {N}}^{\Bbb {N}}$
and
${\mathrm {dom}}(f^{{\mathrm {r}}})\subseteq {\Bbb {N}}^{\Bbb {N}}$
are Borel sets, is determined.
Proof. Firstly, for a problem
$f:\subseteq {\Bbb {N}}^{\Bbb {N}}\rightrightarrows {\Bbb {N}}^{\Bbb {N}}$
we note that
$$ \begin{align*} {\mathrm{graph}}(f^{\mathsf{w}})={\mathrm{graph}}(\mathsf{w}^{-1}\circ f\circ \mathsf{w})=(\mathsf{w}\times\mathsf{w})^{-1}({\mathrm{graph}}(f))\end{align*} $$
and
${\mathrm {dom}}(f^{\mathsf {w}})={\mathrm {dom}}(f\circ \mathsf {w})=\mathsf {w}^{-1}({\mathrm {dom}}(f))$
. Since
$\mathsf {w}$
is continuous with a
${{\boldsymbol \Pi }^0_{2}}$
-domain
${\mathrm {dom}}(\mathsf {w})$
, it follows that
${\mathrm {graph}}(f^{\mathsf {w}})$
and
${\mathrm {dom}}(f^{\mathsf {w}})$
are Borel measurable, if
${\mathrm {graph}}(f)$
and
${\mathrm {dom}}(f)$
are so. Hence,
$\langle {\mathrm {graph}}({\mathsf {{T}}} f^{\mathsf {w}})\rangle $
is Borel measurable in this situation. For a general problem
$f:\subseteq X\rightrightarrows Y$
, we can apply the previous considerations to
$f^{{\mathrm {r}}}:\subseteq {\Bbb {N}}^{\Bbb {N}}\rightrightarrows {\Bbb {N}}^{\Bbb {N}}$
and we obtain the claim using Borel determinacy and Corollary 4.9.⊣
That is even under the axiom of choice
$\mathsf {AC}$
examples of problems that are discontinuous but not effectively so have to be rather complicated. As Polish spaces admit continuous and total versions of the Cauchy representation (see, e.g., [Reference Brattka4, Corollary 4.4.12]), we also obtain the following version of the previous corollary.
Corollary 4.13 (Borel determinacy on Polish spaces)
Let
$X,Y$
be Polish spaces. In
$\mathsf {ZFC}$
every problem
${f:\subseteq X\rightrightarrows Y}$
, such that
${\mathrm {graph}}(f)\subseteq X\times Y$
and
${\mathrm {dom}}(f)\subseteq X$
are Borel sets, is determined.
Proof. For Polish spaces X and Y we can assume that the Cauchy representations
$\delta _X:{\Bbb {N}}^{\Bbb {N}}\to X$
and
$\delta _Y:{\Bbb {N}}^{\Bbb {N}}\to Y$
are total [Reference Brattka4, Corollary 4.4.12]. They are also continuous maps. Since
$f^{{\mathrm {r}}}=\delta _Y^{-1}\circ f\circ \delta _X$
, this implies that
${\mathrm {graph}}(f^{{\mathrm {r}}})=(\delta _X\times \delta _Y)^{-1}({\mathrm {graph}}(f))$
and
${\mathrm {dom}}(f^{{\mathrm {r}}})=\delta _X^{-1}({\mathrm {dom}}(f))$
are Borel sets, if
${\mathrm {graph}}(f)$
and
${\mathrm {dom}}(f)$
are Borel sets. Now the claim follows with Proposition 4.12.⊣
It is an interesting questions whether we get the inverse implication in Corollary 4.11 in the following sense.
Question 4.14. Does
$\mathsf {AD}$
follow from Weihrauch determinacy in
$\mathsf {ZF}+\mathsf {DC}$
?
We note that a similar question, namely whether Wadge determinacy (in the usual sense of Wadge games for sets
$A,B\subseteq {\Bbb {N}}^{\Bbb {N}}$
) implies
$\mathsf {AD}$
is non-trivial and the answer is not known [Reference Andretta1, Reference Andretta2]. For our generalized Wadge games the situation seems to be simpler and we can easily obtain
$\mathsf {AD}$
from Lipschitz determinacy of problems (with a non-constructive proof).
Proposition 4.15. In
$\mathsf {ZF}+\mathsf {DC}$
the following are equivalent:
-
(1) The axiom of determinacy
$\mathsf {AD}$
. -
(2) Every Lipschitz game
$f:\subseteq X\rightrightarrows Y$
is determined, i.e., either Player I or Player II has a winning strategy.
Proof. That (1) implies (2) was proved in Proposition 4.7. We still need to prove that (2) implies (1). For every set
$G\subseteq {\Bbb {N}}^{\Bbb {N}}$
we define the problem
$f_G:\subseteq {\Bbb {N}}^{\Bbb {N}}\rightrightarrows {\Bbb {N}}^{\Bbb {N}}$
with
$f_G(p):=\{q\in {\Bbb {N}}^{\Bbb {N}}:\langle p,q\rangle \in G\}$
and
${\mathrm {dom}}(f_G):=\{p\in {\Bbb {N}}^{\Bbb {N}}: (\exists q\in {\Bbb {N}}^{\Bbb {N}})\;\langle p,q\rangle \in G\}$
. We call G total, if
${\mathrm {dom}}(f_G)={\Bbb {N}}^{\Bbb {N}}$
. It is clear that for non-total G Player I in the Gale–Stewart game G always has a winning strategy, and he just needs to play some
$p\not \in {\mathrm {dom}}(f_G)$
. For total G we obtain
$\langle {\mathrm {graph}}({\mathsf {{T}}} f_G)\rangle =\langle {\mathrm {graph}}(f_G)\rangle =G$
. Hence, by Proposition 4.7 G is determined if the Lipschitz game
$f_G$
is so. This proves determinacy of G for every
$G\subseteq {\Bbb {N}}^{\Bbb {N}}$
.⊣
In order to answer Question 4.14 positively one still needs to bridge the gap between Lipschitz determinacy and Wadge determinacy for problems f (possibly using the techniques from [Reference Andretta1, Reference Andretta2] or a simpler argument).
We prove that Weihrauch determinacy implies at least Wadge determinacy, in the original sense of Wadge games for sets
$A,B\subseteq {\Bbb {N}}^{\Bbb {N}}$
. We can simulate Wadge games for sets
$A,B$
using a particular problem
$\frac {B}{A}$
(which was introduced in [Reference Nobrega and Pauly21]).
Definition 4.16 (Wadge game for sets)
Let
$A,B\subseteq {\Bbb {N}}^{\Bbb {N}}$
. Then the Wadge game
$(A,B)$
is the Wadge game of the problem
$\frac {B}{A}:{\Bbb {N}}^{\Bbb {N}}\rightrightarrows {\Bbb {N}}^{\Bbb {N}}$
with
$$ \begin{align*} {\mathrm{graph}}\left(\frac{B}{A}\right):=(A\times B)\cup\left(({\Bbb{N}}^{\Bbb{N}}\setminus A)\times({\Bbb{N}}^{\Bbb{N}}\setminus B)\right).\end{align*} $$
In the Wadge game
$\frac {B}{A}$
Player II wins if the corresponding run
$(x,y)$
satisfies
$x\in A\iff y\in B$
and otherwise Player I wins. This shows that the Wadge game
$(A,B)$
is the usual one and as usually, by Wadge determinacy we understand the property that every Wadge game
$(A,B)$
is determined, i.e., either Player I or Player II has a winning strategy. This immediately yields the following.
Corollary 4.17 (Wadge determinacy)
In
$\mathsf {ZF}+\mathsf {DC}$
Weihrauch determinacy implies Wadge determinacy.
Another conclusion that we can either directly draw from Proposition 3.7 without further ado or from Corollary 4.17 with the help of [Reference Wadge27, Theorem II.C.2] is the following.
Corollary 4.18 (Perfect subset property)
In
$\mathsf {ZF}+\mathsf {DC}$
Weihrauch determinacy implies that every set
$A\subseteq {\Bbb {N}}^{\Bbb {N}}$
satisfies the perfect subset property.
If Question 4.14 has a negative answer or cannot be answered easily, then one could ask other questions such as the following.
Question 4.19. Does the Baire property
$\mathsf {BP}$
follow from Weihrauch determinacy in
$\mathsf {ZF}+\mathsf {DC}$
?
By the Baire property
$\mathsf {BP}$
we mean that statement that every subset
$A\subseteq {\Bbb {N}}^{\Bbb {N}}$
can be written as symmetric difference
$A=U\Delta M$
with an open set
$U\subseteq {\Bbb {N}}^{\Bbb {N}}$
and a meager set
$M\subseteq {\Bbb {N}}^{\Bbb {N}}$
. If the answer to this question is also negative, then one can ask the following modified version of Question 4.14.
Question 4.20. Does
$\mathsf {AD}$
follow from Weihrauch determinacy in
$\mathsf {ZF}+\mathsf {DC}+\mathsf {BP}$
?
A positive answer to this question is not completely unlikely in light of Proposition 4.15, given that Wadge determinacy and Lipschitz determinacy (both in the usual sense of games for sets
$A,B\subseteq {\Bbb {N}}^{\Bbb {N}}$
) have been proven to be equivalent in
$\mathsf {ZF}+\mathsf {DC}+\mathsf {BP}$
by Andretta [Reference Andretta1, Reference Andretta2].
5 Computable discontinuity and productivity
In this section we briefly want to discuss the question what computable discontinuity means for subsets and how the notion is linked to the notion of productivity. Here, for every subset
$A\subseteq X$
of some fixed space X, we denote by
$$ \begin{align*} \chi_A:X\to{\Bbb{S}},x\mapsto\left\{\begin{array}{ll} 1 & \mbox{if } x\in A,\\ 0 & \mbox{otherwise} \end{array}\right. \end{align*} $$
the characteristic function of A. The codomain
${\Bbb {S}}=\{0,1\}$
is Sierpiński space that is equipped with the total representation
$\delta _{\Bbb {S}}$
with
$\delta _{\Bbb {S}}(p)=0:\iff p=000\ldots $
. It is well-known that for any represented space X and
$A\subseteq X$
the characteristic function
$\chi _A$
is continuous if and only if A is open.
As a side remark we mention that the characteristic function in this form can also nicely be used to embed Wadge reducibility and many-one reducibility into the strong version of Weihrauch reducibility for non-trivial sets. We recall that for
$A,B\subseteq {\Bbb {N}}^{\Bbb {N}}$
the set A is called Wadge reducible to B, in symbols
$A\mathop {\leq _{\mathrm {W}}} B$
, if there is a continuous
$f:{\Bbb {N}}^{\Bbb {N}}\to {\Bbb {N}}^{\Bbb {N}}$
with
$A=f^{-1}(B)$
. Likewise, we say for
$A,B\subseteq {\Bbb {N}}$
that A is many-one reducible to B, in symbols
$A\mathop {\leq _{\mathrm {m}}} B$
, if there is a computable
$f:{\Bbb {N}}\to {\Bbb {N}}$
such that
$A=f^{-1}(B)$
. Since the only continuous functions
$f:{\Bbb {S}}\to {\Bbb {S}}$
are the identity and the two constant functions, we directly get the following characterization of Wadge and many-one reducibility in terms of the topological version of strong Weihrauch reducibility.
Proposition 5.1 (Reducibilities)
We obtain
-
(1)
$\chi _A\mathop {\leq _{\mathrm {sW}}}\chi _B\iff A\mathop {\leq _{\mathrm {m}}} B$
for
$A,B\subseteq {\Bbb {N}}$
with
$B\not \in \{\emptyset ,{\Bbb {N}}\}$
. -
(2)
$\chi _A\leq _{\mathrm {sW}}^*\chi _B\iff A\mathop {\leq _{\mathrm {W}}} B\iff \frac {B}{A}\leq _{\mathrm {W}}^*{\mathrm {id}}$
for
$A,B\subseteq {\Bbb {N}}^{\Bbb {N}}$
with
$B\not \in \{\emptyset ,{\Bbb {N}}^{\Bbb {N}}\}$
.
Hence, the corresponding reducibility structures can be embedded into the corresponding strong versions of the Weihrauch lattice for non-trivial sets. By
${\mathcal O}(X)$
we denote the set of open subsets of X equipped with the representation
$\delta _{{\mathcal O}(X)}$
, defined by
$\delta _{{\mathcal O}(X)}(p)=U:\iff \Phi _p$
is a realizer of
$\chi _U$
. Now one can ask what it means for
$\chi _A$
to be computably discontinuous. The following result answers this question for Baire space
$X={\Bbb {N}}^{\Bbb {N}}$
using the symmetric difference problem
$\Delta _A:\subseteq {\mathcal O}(X)\rightrightarrows X,U\mapsto A\Delta U$
. Here
$A\Delta U:=(A\setminus U)\cup (U\setminus A)$
denotes the symmetric difference of
$A, U\subseteq X$
. The problem
$\Delta _A$
is total for non-open
$A\subseteq X$
.
Proposition 5.2 (Symmetric difference)
Let
$A\subseteq {\Bbb {N}}^{\Bbb {N}}$
not be open. Then the problem
$\Delta _A$
is computable if and only if
$\chi _A$
is computably discontinuous.
Proof. If
$\chi _A:{\Bbb {N}}^{\Bbb {N}}\to {\Bbb {S}}$
is computably discontinuous, then there is a computable discontinuity function
$D:{\Bbb {N}}^{\Bbb {N}}\to {\Bbb {N}}^{\Bbb {N}}$
for
$\chi _A$
. Given a name q of a realizer
$\Phi _q$
of the continuous function
$\chi _U:{\Bbb {N}}^{\Bbb {N}}\to {\Bbb {S}}$
for any given
$U\in {\mathcal O}({\Bbb {N}}^{\Bbb {N}})$
, the value
$D(q)$
is a name for some point
$x\in X$
with
$\chi _U(x)\not =\chi _A(x)$
, i.e.,
$x\in A\Delta U$
. That is,
$\Delta _A$
is realized by D and hence computable. On the other hand, let
$\Delta _A$
be computable and
$A\subseteq {\Bbb {N}}^{\Bbb {N}}$
not open. Given a name q of some potential realizer
$\Phi _q$
of
$\chi _A$
, we can convert q computably into a name
$r=G(q)$
of some total function
$\Phi _r$
with
$\delta _{\Bbb {S}}\Phi _r=\delta _{\Bbb {S}}\Phi _q$
, because
$\delta _{\Bbb {S}}$
is precomplete (the idea is that
$\Phi _r$
produces zero output as long as
$\Phi _q$
makes no other information available). Let us denote by
$G:{\Bbb {N}}^{\Bbb {N}}\to {\Bbb {N}}^{\Bbb {N}}$
the corresponding computable function. Now there is some open
$U\subseteq {\Bbb {N}}^{\Bbb {N}}$
such that
$\Phi _r$
is a realizer of
$\chi _U$
, namely
$U:=\Phi _r^{-1}({\Bbb {N}}^{\Bbb {N}}\setminus \{000\ldots \})=\Phi _r^{-1}\delta _{\Bbb {S}}^{-1}(\{1\})$
. Since A is not open,
$\Delta _A(U)$
is defined and non-empty. Let F be a computable realizer of
$\Delta _A$
and
$D:=FG$
. Then
$F(r)\in \Delta _A(U)=(A\setminus U)\cup (U\setminus A)$
, i.e.,
$\chi _UD(q)\not =\chi _AD(q)$
. This implies
$\delta _{\Bbb {S}}\Phi _qD(q)\not =\chi _AD(q)$
, since either
$D(q)\not \in {\mathrm {dom}}(\Phi _q)$
or otherwise
$\delta _{\Bbb {S}}\Phi _qD(q)=\delta _{\Bbb {S}}\Phi _rD(q)=\chi _UD(q)$
. That is D is a computable discontinuity function of
$\chi _A$
.⊣
An analogous statement holds if we replace computable by continuous in both occurrences. However, in this case the statement is void as any
$\chi _A$
for non-open A is effectively discontinuous by (a suitable extension of) Proposition 3.11 or by observing that
$\Delta _A$
for non-open A is always continuous. We can also summarize Proposition 5.2 as follows.
Corollary 5.3 (Symmetric difference)
$\Delta _A\mathop {\leq _{\mathrm {W}}}{\mathrm {id}}\iff \mathsf {DIS}\mathop {\leq _{\mathrm {W}}}\chi _A$
for non-open
$A\subseteq {\Bbb {N}}^{\Bbb {N}}$
.
Proposition 5.2 shows that the notion of computable discontinuity is also formally related to the notion of productivity. Weihrauch has introduced a topological and a computability-theoretic notion of productivity for subsets
$A\subseteq {\Bbb {N}}^{\Bbb {N}}$
[Reference Weihrauch28, Definition 4.4], [Reference Weihrauch29, Definition 3.2.24]. If, in a similar way, we transfer the definition of completely productive sets, as originally defined by Dekker [Reference Dekker10], then we could say that non-open
$A\subseteq {\Bbb {N}}^{\Bbb {N}}$
is completely productive if
$\Delta _A$
is computable. Using this terminology, non-open
$A\subseteq {\Bbb {N}}^{\Bbb {N}}$
is completely productive if and only if
$\chi _A$
is computably discontinuous by Proposition 5.2. Myhill [Reference Myhill18] proved that a set
$A\subseteq {\Bbb {N}}$
is productive if and only if A is completely productive (see also the proofs in [Reference Rogers24, Theorem VII, Section 11.3], [Reference Weihrauch29, Corollary 2.6.8]). It is clear that complete productivity for
$A\subseteq {\Bbb {N}}^{\Bbb {N}}$
implies productivity. We leave it as a task to the reader to study whether productivity also implies complete productivity for Baire space
${\Bbb {N}}^{\Bbb {N}}$
(or even more general spaces).
6 Conclusions
We have introduced the discontinuity problem
$\mathsf {DIS}$
and we have provided some evidence that one can consider it as the simplest natural unsolvable problem with respect to the topological version of Weihrauch reducibility. At least in
$\mathsf {ZF}+\mathsf {DC}+\mathsf {AD}$
it turns out that it actually induces the minimal discontinuous Weihrauch degree.
More results on the discontinuity problem will be provided in a forthcoming article [Reference Brattka5]. While the original definition of
$\mathsf {DIS}$
is in terms of a universal function
${\mathsf {{U}}}$
, it is useful to have a characterization in purely set-theoretic terms. In [Reference Brattka5] we prove that the discontinuity problem is equivalent to the range non-equality problem defined by
$\mathsf {NRNG}:{\Bbb {N}}^{\Bbb {N}}\rightrightarrows 2^{\Bbb {N}},p\mapsto \{A\in 2^{\Bbb {N}}:A\not ={\mathrm {range}}(p-1)\}$
. Here for
$p\in {\Bbb {N}}^{\Bbb {N}}$
the finite or infinite sequence
$p-1\in {\Bbb {N}}^{\Bbb {N}}\cup {\Bbb {N}}^*$
is the sequence that is obtained as concatenation of
$p(0)-1, p(1)-1, p(2)-1,\ldots $
, where
$-1$
is identified with the empty word
$\varepsilon $
.
Proposition 6.1.
$\mathsf {DIS}\mathop {\equiv _{\mathrm {sW}}}\mathsf {NRNG}$
.
In [Reference Brattka5] we also discuss algebraic properties of the discontinuity problem
$\mathsf {DIS}$
and one important property is that the parallelization
$\widehat {\mathsf {DIS}}$
of the discontinuity problem is equivalent to the non-computability problem
$\mathsf {NON}$
.
Theorem 6.2 (Non-computability is parallelized discontinuity)
$\mathsf {NON}\mathop {\equiv _{\mathrm {sW}}}\widehat {\mathsf {DIS}}$
.
The non-computability problem is defined with the help of Turing reducibility
$\mathop {\leq _{\mathrm {T}}}$
by
$\mathsf {NON}:{\Bbb {N}}^{\Bbb {N}}\rightrightarrows {\Bbb {N}}^{\Bbb {N}},p\mapsto \{q\in {\Bbb {N}}^{\Bbb {N}}:q\not \leq _{\mathrm {T}} p\}$
. This result supports the slogan that “non-computability is the parallelization of discontinuity” and underlines that the discontinuity problem is a natural one. The discontinuity problem can itself be obtained by stashing (a dual operation to parallelization introduced in [Reference Brattka5]) starting from other natural problems such as
$\mathsf {LPO},\mathsf {LLPO}$
, etc. Hence, it is nicely related in an algebraic way to other natural problems in the Weihrauch lattice.
Acknowledgments
We would like to thank Matthias Schröder for a discussion on the relevance of the axiom of determinacy and different forms of the axiom of choice for computable analysis. Likewise, we would like to thank Arno Pauly for a discussion on Wadge games for problems that has helped to improve the corresponding results. This work has been supported by the National Research Foundation of South Africa (Grant Number 115269).
Open access
