Weihrauch reducibility (≤W) is a type of reducibility relation that can be used to classify the uniform computational content of various mathematical objects. It is first defined for multivalued functions between spaces X, Y, in which elements of X and Y are represented by functions from N to NN to N in a specified way. Then, via Skolem functions, it can be applied for predicates and theorems in areas like recursive function theory, analysis, and logic.
Of particular interest is the relationship with binary choice (C2), which is defined as follows: for a nonempty set A ⊆ {0,1}, with a representation that yields a recursive enumeration of {0,1} - A, the set of values of C2(A) is A itself. Thus, C2 may be informally described as the problem of choosing a value from a two-element set, where one of the two options may eventually be ruled out. A multivalued function f is discriminative if it satisfies C2 ≤W f; otherwise it is indiscriminative.
The paper under review contains a substantial number of results, some easy and some moderately tricky, which establish the relationship between various properties and theorems under ≤W. It is noted that results in recursive function theory are for the most part indiscriminative. This, in particular, follows whenever they are densely realized, which means that the objects claimed to exist are invariant under finite changes, like sets of a required Turing degree. One consequence is that such results have no direct applications in analysis: in a certain sense, discriminative results cannot be derived from nondiscriminative ones.
The properties classified are “diagonal noncomputability, hyperimmunity, complete consistent extensions of Peano arithmetic, Martin-Löf randomness, 1-genericity, and cohesiveness.” Three classical results from recursive function theory are dealt with, namely “the low basis theorem of Jockusch and Soare, the Kleene-Post theorem [in a relativized form], and Friedberg’s jump inversion theorem.” The latter result, in contrast to many others, is discriminative; this is taken as an explanation for its numerous applications.
