Computability

We introduce and study the notion of overt choice for countably-based spaces and for CoPolish spaces. Overt choice is the task of producing a point in a closed set specified by what open sets intersect it. We show that the question of whether overt choice is continuous for a given space is related to topological completeness notions such as the Choquet-property; and to whether variants of Michael’s selection theorem hold for that space. For spaces where overt choice is discontinuous it is interesting to explore the resulting Weihrauch degrees, which in turn are related to whether or not the space is Fréchet–Urysohn.

The SRT 2 2 vs. COH problem is a central problem in computable combinatorics and reverse mathematics, asking whether every Turing ideal that satisfies the principle SRT 2 2 also satisfies the principle COH . This paper is a contribution towards further developing some of the main techniques involved in attacking this problem. We study several principles related to each of SRT 2 2 and COH , and prove results that highlight the limits of our current understanding, but also point to new directions ripe for further exploration.

We consider two combinatorial principles, ERT and ECT . Both are easily proved in RCA 0 plus Σ 2 0 induction. We give two proofs of ERT in RCA 0 , using different methods to eliminate the use of Σ 2 0 induction. Working in the weakened base system RCA 0 ∗ , we prove that ERT is equivalent to Σ 1 0 induction and ECT is equivalent to Σ 2 0 induction. We conclude with a Weihrauch analysis of the principles, showing ERT ≡ W LPO ∗ < W TC N ∗ ≡ W ECT .

In reverse mathematics, one sometimes encounters proofs which invoke some theorem multiple times in series, or invoke different theorems in series. One example is the standard proof that Ramsey’s theorem for 2 colors implies Ramsey’s theorem for 3 colors. A natural question is whether such repeated applications are necessary. Questions like this can be studied under the framework of Weihrauch reducibility. For example, one can attempt to capture the notion of one multivalued function being uniformly reducible to multiple instances of another multivalued function in series. There are three known ways to formalize this notion: the compositional product, the reduction game, and the step product. We clarify the relationships between them by giving sufficient conditions for them to be equivalent. We also show that they are not equivalent in general.

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.

Finding the set of leaves for an unbounded tree is a nontrivial process in both the Weihrauch and reverse mathematics settings. Despite this, many combinatorial principles for trees are equivalent to their restrictions to trees with leaf sets. For example, let WF ˆ denote the problem of choosing which trees in a sequence are well-founded, and let PK denote the problem of finding the perfect kernel of a tree. Let WF ˆ L and PK L denote the restrictions of these principles to trees with leaf sets. Then WF ˆ , WF ˆ L , PK , and PK L are all equivalent to Π 1 1 – CA 0 over RCA 0 , and all strongly Weihrauch equivalent.

In this paper, we show that the dense existence of nowhere-differentiable continuous functions in C [ 0 , 1 ] is provable, using a version of the Baire category theorem, in an intuitionistic subsystem of elementary analysis whose induction is restricted to Σ 1 0 formulae.

A natural extension of the Wadge hierarchy is obtained if we consider k-partitions (or even Q-partitions for a countable better quasiorder Q) of the Baire space instead of sets (i.e., 2-partitions). Natural initial segments of the Q-Wadge hierarchy were recently characterised in terms of the so called h-quasiorder on suitably iterated Q-labeled countable well founded forests. Though these characterisations are natural and constructive, their definitions are rather long and technical. In this paper, we find clear shorter characterizations as (reducts of) a kind of free structures satisfying some natural axioms. Informally, we provide short and clear axiomatisations of the initial segments.